java中的归并排序

为什么使用归并排序？
java中的Arrays.sort(Object[] o)是对数组进行排序，它使用的是归并排序的方式，
快速排序要比归并排序更快一些，但为什么使用归并排序了？原因是归并排序是一种稳定的排序
方式，即归并排序不交换相同的元素，这就意味着，在按一种方式排序后同时可以按另外一种
方式进行排序。比如员工可以首先按工资排序，然后按名字排序，一种排序不会打乱另一种排序
的顺序。
下面分析下sort方法的简化版：

    /**
     * 归并排序 (递归实现)
     * 前提： 每个元素要有可比性，这里元素必须实现Comparable接口。
     * 基本原理为：1.拆分 假设有N个元素的列表，首先把它拆分成2个或2个
     * 以上的元素组成的新的列表(这里我的新列表长度不超过3)，分别对对它们进行排序。
     * 2.归并。把所有的排好序的子类表两两归并，如此重复，直到归并成一个含N个
     * 元素的有序列表为止
     * 图解：(大于3就继续分解)
     *  大于3          8    7    6    5     4     3     2     1
     *                                分|解
     *                                  |
     *  大于3            8  7  6  5            4   3   2   1 
     *                     分|解                  分|解
     *                       |                      | 
     *  小于 3            8 7   6 5             4  3    2 1
     *  排序              7 8   5 6             3  4    1 2 
     *  归并                 |                       | 
     *                  7   8  5  6            3  4    1  2 
     *                       |                       |
     *  顺序保存        5   6  7  8            1  2    3  4
     *                                   |
     *  归并           5    6    7    8   1    2    3     4
     *  				 |
     *  顺序保存       1    2    3    4   5    6    7     8
     * @param src 临时中间数组，它是目标数组的拷贝
     * @param target 目标排序数组
     * @param low 需排序的起始索引
     * @param high 需排序的结束索引
     * 
     */
    public static void mergeSort(Object[] src,Object[] dest,int low,int high){
    	int length = high - low;
    	if(length < 3 ){	//对长度小于3的列表排序
    		//排序方法一：起泡排序(大数沉底)
//    		for(int i=low;i<high-1;i++){
//    			for(int j=low;j<high-1-i+low;j++){
//    				if(((Comparable) dest[j]).compareTo(dest[j+1]) > 0){
//        				swap(dest, j, j+1); 
//        			}
//    			}
//    		}
    		//排序方法二：这是起泡排序的一种变体（小数上浮）
    		for (int i = low; i < high; i++){
    			for (int j = i; j > low ; j--){
    				if(((Comparable) dest[j - 1]).compareTo(dest[j]) > 0){
    					swap(dest, j-1, j); 
    				}
    			}
    		}
    		return;
    	}
    	
    	int mid = (high + low)/2;	//拆分
    	mergeSort(dest, src, low, mid);	 //递归，可能会继续拆分(那么必然继续合并)
    	mergeSort(dest, src, mid, high);
    	
    	//开始归并,方法一
//    	for(int i=low,p=low,q=mid;i<high;i++){
//    		//第一个条件时为了添加剩余的值
//			if(q >= high || (p < mid &&((Comparable) src[p]).compareTo(src[q]) <= 0)){
//				dest[i] = src[p++];
//			}else{
//				dest[i] = src[q++];
//			}
//    	}
    	
    	//开始归并，方法二
    	int i = low;
    	int p = low;	//第一个列表指针
    	int q = mid;    //第二个列表指针
    	while(p < mid && q <high){
    		if(((Comparable) src[p]).compareTo(src[q]) <= 0){
    			dest[i++] = src[p++];
    		}else{
    			dest[i++] = src[q++];
    		}
    	}
    	//添加剩余的值
    	while(p < mid && i<high){
    		dest[i++] = src[p++];
    	}
    	while(q < high && i<high){
    		dest[i++] = src[q++];
    	}

    private static void swap(Object[] x, int a, int b) {
    	Object t = x[a];
    	x[a] = x[b];
    	x[b] = t;
    }
}

递归形式的算法在形式上比较简洁，但实用性不够好。
下面讲讲归并排序的非递归实现

public class MergeDemo{
	public static void main(String[] args) {
		String[] a= {"9","8","7","6","5","4","3","2","1"};
		Object[] aux = (Object[])a.clone();
		mergeSort(aux, a);
		for(int i=0;i<a.length;i++){
			System.out.println(a[i]);
		}
	}

    //每个拆分的列表元素个数<=3
    private static final int INSERTIONSORT_THRESHOLD = 3;
    /**
     * 
     * 归并排序(非递归实现)
     */
    public static void mergeSort(Object[] src,Object[] dest){
    	int spreCount = INSERTIONSORT_THRESHOLD;	 
    	int low,mid,high;
    	int len = src.length;
		if(len <= INSERTIONSORT_THRESHOLD*2){		//如果只能划分为两组，直接排序
			sort(dest,0,len);
			return;
		}
    	while(spreCount < len){
	    	for(int i=0;i<len;i=high){	//依次排序归并相邻两个列表
	    		low = i;	
	    		high = low + spreCount * 2 ;
	    		mid = low + spreCount;
	    		if(high >= len){
	    			high = len;
	    		}
	    		int l = high - low;
	    		if(l <= INSERTIONSORT_THRESHOLD){
	    			sort(src,low,high);
	    			break;
	    		}

	    		if(spreCount == 3){		//所有拆分的列表只进行一次排序
	    			sort(dest,low,mid);
	    			sort(dest,mid,high);
	    		}
	    		if(l == len)	//最后一次归并把src有次序的赋给dest
	    			Merge(src,dest,low,mid,high);
	    		else
	    			Merge(dest,src,low,mid,high);

	    	}
	    	spreCount *= 2;
    	}
    	
    }
    //对拆分的每个列表进行排序
    private static void sort(Object[] dest,int low,int high){
		for (int i = low; i < high; i++){
			for (int j = i; j > low ; j--){
				if(((Comparable) dest[j - 1]).compareTo(dest[j]) > 0){
					swap(dest, j-1, j); 
				}
			}
		}
    }
    
    //归并相邻两个列表并保存在dest中
	private static void Merge(Object[] src, Object[] dest, int low, int mid,
			int high) {
    	int i = low;
    	int p = low;	//第一个列表指针
    	int q = mid;    //第二个列表指针
    	while(p < mid && q <high){
    		if(((Comparable) src[p]).compareTo(src[q]) <= 0){
    			dest[i++] = src[p++];
    		}else{
    			dest[i++] = src[q++];
    		}
    	}
    	//添加剩余的值
    	while(p < mid && i<high){
    		dest[i++] = src[p++];
    	}
    	while(q < high && i<high){
    		dest[i++] = src[q++];
    	}
		
	}
	
    private static void swap(Object[] x, int a, int b) {
    	Object t = x[a];
    	x[a] = x[b];
    	x[b] = t;
    }
 

}