排序算法之归并排序

归并排序是分治思想的一个很好的例子。它比希尔排序在时间复杂度上更优，为NlogN，并且属于稳定排序方法（稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的）。

自上而下的归并排序思想是，依赖于递归，逐级将待排序对象分割为较小的集合，直到这个集合只剩下一个元素，最后再归并每两个集合，排序的动作就发生在这个归并（merge）的时候。一分一合之间，集合就被排序了。

public class MergeSort {
	
	private Comparable[] aux;
	
	public void sort(Comparable[] a){
		aux = new Comparable[a.length];
		sort(a,0,a.length-1);
	}
	

	private void sort(Comparable[] a,int lo,int hi) {
		if(hi<=lo) return;
		int mid = lo + (hi - lo)/2;//将数组一分为二
		sort(a,lo,mid);//分别对这两个子数组进行排序
		sort(a,mid + 1,hi);
		merge(a,lo,mid,hi);//合并两个已经排序的数组
	}
	
	private void merge(Comparable[] a,int lo,int mid,int hi){
		int i = lo;
		int j = mid + 1;
		for(int k = lo;k<=hi;k++){//将待排序数组全部复制到临时数组中
			aux[k] = a[k];
		}
		for(int k = lo;k<=hi;k++){//从临时数组中拿回到排序数组中
			if(i>mid) a[k] = aux[j++];//左边数组已经没有元素可拿了，拿右边数组元素
			else if(j>hi) a[k] = aux[i++];//右边数组已经没有元素可拿了，拿左边边数组元素
			else if(less(aux[i],aux[j])) a[k] = aux[i++];//谁小拿谁
			else a[k] = aux[j++];
		}
	}

	private boolean less(Comparable a, Comparable b) {
		return a.compareTo(b)<0;
	}

	public static void main(String[] args) {
		int size = 3000000;
		Integer[] a = RandomFactory.randomInt(size,40000);
		
		MergeSort sort = new MergeSort();
		//sort.show(a);
		long t = System.currentTimeMillis();
		sort.sort(a);
		t = System.currentTimeMillis() -t;
		//sort.show(a);
		
		System.out.println("Insert sort");
		System.out.println("time:" + t);
		System.out.println("random data size : " + size);
	}


	private void show(Comparable[] a) {
		int i = 0;
		for(Comparable c : a){
			System.out.print(c+" ");
			i++;
			if(i%20==0){
				System.out.println();
			}
		}
		System.out.println();
	}
	
}

测试结果显示，同样是对300万测试数据进行排序，归并排序较希尔排序时间上有明显的优势：

Merge sort
time:2068
random data size : 3000000

Shell sort
time:7075
random data size : 3000000