归并排序

归并排序也是用到递归的一种排序方式，他比简单排序效率要快很多，冒泡，选择，插入等要O(n*n)的时间复杂度，而归并只需要O(N*logN)的时间。他也比较好实现，但是有个缺点就是需要用到是原数组双倍的空间，因为他要在内存中有另外一个和原数组一样大的数组来做中间数组。

归并数组的特点是用空间换时间

归并算法的核心是合并两个有序的数组，先从两个元素开始合并成一个有序数组，然后是两个容量为二的有序数组合并为一个有序数组 ........... 直到合并成了和原数组一样大下的有序数组，排序完成。所以这也是要用到递归的原因。

package sort;

public class MergerSort {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 1000000;
		MergerSort o = new MergerSort();
		int [] srcArr = new int[n],tempArr = new int[n];
		for (int i = n; i > 0; i--) {
			srcArr[i - 1] = i;
		}
		long begin = System.currentTimeMillis();
		o.mergerSort(srcArr, tempArr, 0, n-1);
		long end = System.currentTimeMillis();
		System.out.println("time="+(end - begin));
		//o.display(srcArr);
	}
	private void display(int[] a) {
		// TODO Auto-generated method stub
		for (int i = 0; i < a.length; i++) {
			System.out.println(a[i]);
		}
	}
	
	/**归并排序
	 * @param srcArr 原数组
	 * @param tempArr 临时数组
	 * @param left 最左边数据的索引
	 * @param right 最右边数据的索引
	 */
	public void mergerSort(int[] srcArr,int[] tempArr,int left,int right){
		if(left < right){
			//获取分界线
			int middle = (left + right)/2;
			//给左边数组排序
			mergerSort(srcArr,tempArr,left,middle);
			//给右边数组排序
			mergerSort(srcArr,tempArr,middle+1,right);
			//合并两个数组
			merger(srcArr,tempArr,left,middle,right);
		}
	}

	/** 将两个有序数组合并为一个有序数组
	 * @param srcArr  原数组
	 * @param tempArr 临时数组（用来交换数据）
	 * @param left    在原数组左边边界开始处的索引            left - middle 为数组1
	 * @param middle  在原数组用来隔开两个数组的中间索引    middle+1 - right 为数组2
	 * @param right   在原数组右边边界结束的索引
	 */
	private void merger(int[] srcArr, int[] tempArr, int left, int middle, int right) {
		int n = right - left + 1;//总数组长度
		for (int i = 0,l = left,r = middle + 1; i < n; i++) {
			//如果右边数组已经没有数据了，或者说左边数组当前数据小于等于右边数组数据，就将左边数组数据放到临时数组
			if(r > right ||( l <= middle && srcArr[l] <= srcArr[r])){
				tempArr[i] = srcArr[l++];
			}else{
				//放右边数组数据到临时数组
				tempArr[i] = srcArr[r++];
			}
		}
		//将排好序的数组返回给原数组
		for (int i = 0; i < n; i++) {
			srcArr[left++] = tempArr[i];
		}
	}
}

在我机器逆序 排100w数据需要130 - 160 毫秒 ，还可以啦。比简单排序快了不是一点点。java的Arrays.sort()也是用了这个方法来排序的，不知道是什么原因不用更高级的排序方法呢。