《Java数据结构和算法》学习笔记(5)——递归 归并排序

每篇笔记都会附上随书的Applet演示程序，有算法看不明白的，可以下载Applet运行起来（直接打开html文件即可），可以很容易地看清楚算法的每一步。
方法调用自身，就构成了递归调用，通常递归都有个终止条件，否则程序无法停止运行。

归并排序

归并排序的原理（升序排序）是将两个有序数组合并成一个有序数组，先对比两个数组的第1项，如果数组a的第1项大于数组b的第1项，那么将数组b的第1项复制到新数组中。接着对比数组a的第1项和数组b的第2项，再把更小的一项放到新数组的第2个位置上……直到合并完成。
递归的过程是一个不断分割数组的过程，把原数组不断的分割成两半，直到不能再分割（长度为1），则返回，然后开始合并。
代码如下：

	@SuppressWarnings("unchecked")
	public static <T extends Comparable<? super T>> void mergeSort(T[] array){
		T[] workspace = (T[])new Comparable[array.length];
		recallMergeSort(array, workspace, 0, array.length - 1);
	}
	
	private static <T extends Comparable<? super T>> void recallMergeSort
	(T[] array, T[] workspace, int lowerBound, int upperBound){
		if(upperBound == lowerBound){
			return;
		}else{
			int midIndex = (upperBound + lowerBound) / 2;
			recallMergeSort(array, workspace, lowerBound, midIndex);
			recallMergeSort(array, workspace, midIndex + 1, upperBound);
			merge(array, workspace, lowerBound, midIndex + 1, upperBound);
		}
	}
	
	private static <T extends Comparable<? super T>> void merge
	(T[] array, T[] workspace, int lowerIndex, int higherIndex, int upperBound){
		int i = 0;
		int midIndex = higherIndex - 1;
		int lowerBound = lowerIndex;
		while(lowerIndex <= midIndex && higherIndex <= upperBound){
			if(array[lowerIndex].compareTo(array[higherIndex]) < 0)
				workspace[i++] = array[lowerIndex++];
			else
				workspace[i++] = array[higherIndex++];
		}
		
		while(lowerIndex <= midIndex)
			workspace[i++] = array[lowerIndex++];
		
		while(higherIndex <= upperBound)
			workspace[i++] = array[higherIndex++];
		
		for(i=lowerBound; i<=upperBound; i++)
			array[i] = workspace[i - lowerBound];
	}

归并排序的时间复杂度是O(N*logN)，比表插入排序法快得多，但需要多1倍的内存空间。对长度为1万的数组排序，时间几乎算不出来（几乎为0），因为我把数组扩大10倍，经测试，对随机数组进行排序需要0.094秒，逆序排序需要0.11秒。