4、归并排序

4.1算法思想——

将数组分为两半，对每部分递归地应用归并排序，直到最后的子数组只包含一个元素。在每部分都排好序后，对它们进行合并。

4.2时间复杂度——

假如用T（n）表示使用归并排序对n个元素构成的数组进行排序而使用的时间，用mergeTime来表示将两个子分组合并起来而花费的时间。那么

T（n） = T(n/2)+T(n/2) + mergetime

而megeTime就是归并两个子数组所耗费的时间，以最大时间来算，最多需要n-1次来比较两个子数组的元素，然后n次移动到临时数组中。那么mergetime就是2n -1 。

因此 T（n） = T(n/2)+ T(n/2) +2n -1 。

使用数学知识可以求解到 T(n)= O(nlogn)。

明显，归并排序优异于前面的选择，插入和冒泡算法。

应该注意到一点，就是我们平常用的工具类java.util.Array中sort方法就是使用归并排序的。

4.3实现程序——

package lin.algo;

public class Main {


	public static void main(String[] args) {
		int[] list = {255555553,1,-12222222,34,0,-101777770,991221299,235645452,047777745,145555000,-235551234,
				255555553,1,-12222222,34,0,-101777770,991221299,235645452,047777745,145555000,-235551234,
				255555553,1,-12222222,34,0,-101777770,991221299,235645452,047777745,145555000,-235551234,
				255555553,1,-12222222,34,0,-101777770,991221299,235645452,047777745,145555000,-235551234,
				255555553,1,-12222222,34,0,-101777770,991221299,235645452,047777745,145555000,-235551234,
				255555553,1,-12222222,34,0,-101777770,991221299,235645452,047777745,145555000,-235551234};
		long time = System.currentTimeMillis();
		mergeSort(list);
		for (int i : list) {
			System.out.print(i+" ");
		}
		System.out.println();
		System.out.println("归并排序所用时间是："+(System.currentTimeMillis() - time));
	}
	
	/*
	 * 归并排序，分两步，一是分组，二是合并
	 */
	private static void mergeSort(int[] list){
		if (list.length<=1) {
			return;
		}else {
			//第一组，先排序
			int[] firstList = new int[list.length/2];
			//把前面一半的数据复制过去
			System.arraycopy(list, 0,firstList,0, firstList.length);
			//递归地分组然后排序
			mergeSort(firstList);
			
			//第二组，另一半
			int[] secondList = new int[list.length-firstList.length];
			//把前面一半的数据复制过去
			System.arraycopy(list, firstList.length,secondList,0, secondList.length);
			//递归地分组然后排序
			mergeSort(secondList);
			
			//将排好序的两个小组合并成一个有序的大组
			int[] result =  merge(firstList, secondList);
			//将最后结果复制到list中
			System.arraycopy(result, 0, list, 0, result.length);
			
		}
	}
	/*
	 * 归并排序第二步，合并
	 */
	private static int[] merge(int[] firstList,int[] secondList){
		int[] resultList = new int[firstList.length+secondList.length];
		
		//定义三个变量来作为索引变量
		int firstIndex = 0;
		int secondIndex = 0;
		int resultIndex = 0;
		
		//如果两组长度不一，先把一组合并完。
		while (firstIndex<firstList.length && secondIndex<secondList.length) {
			if (firstList[firstIndex]<secondList[secondIndex]) {
				resultList[resultIndex++] = firstList[firstIndex++]; //小的先入
			}else {
				resultList[resultIndex++] = secondList[secondIndex++]; 
			}
		}
		
		//有可能某一组比另外一组多，因此上述循环并没完全将元素添加到resultList中
		while(firstIndex<firstList.length){
			resultList[resultIndex++] = firstList[firstIndex++]; 
		}
		
		while(secondIndex<secondList.length){
			resultList[resultIndex++] = secondList[secondIndex++]; 
		}
		return resultList;
	}
	
	
	
}