算法回顾之七：归并排序

算法回顾系列第七篇：归并排序

------------------------------------

归并排序

 

基本原理：

利用递归和分而治之的技术将数据序列划分成为越来越小的半子表，再对半子表排序，最后通过递归步骤将排好序的半子表合并成为越来越大的有序序列。

归并排序包括两个步骤，分别为：1、划分子表。2、合并半子表。

该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

 

程序实现：

public void sort(int[] data){
        int[] temp = new int[data.length];
        mergeSort(data,temp,0,data.length-1);
    }
    
    /**
     * @param 待排序数组
     * @param 辅助排序数组
     * @param 起始位置
     * @param 结束位置
     */
    private void mergeSort(int[] data,int[] temp,int l,int r){
        int mid=(l+r)/2;
        if(l==r) return ;
        //分治:递归划分左半个子表
        mergeSort(data,temp,l,mid);
        //分治:递归划分右半个子表
        mergeSort(data,temp,mid+1,r);
        System.out.println("begin merge ...");
        /**
         * 合并子表：
         * 左半个子表和右半个子表标记(mid为中间位置)两个指针各指向头元素，
         * 选择相对小的元素放入到合并空间，并移动指针到下一位置。
         * 重复步骤上面步骤直到左(或右)某一指针达到序列尾，
         * 将右(或左)剩下的所有元素直接复制到合并序列尾。
         */
        System.out.println("data:"+Arrays.toString(data)+" temp:"+Arrays.toString(temp));
    	System.out.println("l:"+l+" r:"+r+" mid:"+mid);
    	//复制data中l到r内区域的数到temp的对应位置.
        for(int i=l;i<=r;i++){
            temp[i]=data[i];
        }
        System.out.println("copy data:"+Arrays.toString(data)+" copy temp:"+Arrays.toString(temp));
        //声明2个指针:i1左子表头,i2右子表头,指针作用于temp,合并后的值写入data.
        int i1=l;//指针:mid左边元素坐标位置(起始为l).
        int i2=mid+1;//指针:mid右边元素坐标位置(起始为mid右边第一个元素).
        //遍历l到r区域之间的数据(从l的最左边元素向右遍历直到r).
        for(int cur=l;cur<=r;cur++){
            if(i1==mid+1){//如果i1已经遍历到mid以右(mid为边界).
            	System.out.println("i1==mid+1");
                data[cur]=temp[i2];//将tmp的mid以右坐标位置的元素写入data当前位置.
                i2++;//mid右子表指针移动(mid右边元素坐标+1)
            }else if(i2>r){//如果mid以右元素已经遍历超过r(r为边界).
            	System.out.println("i2>r");
            	data[cur]=temp[i1];//将tmp的mid以左坐标位置的元素写入data当前位置.
            	i1++;//mid左子表指针移动(mid左边元素坐标+1)
            }else if(temp[i1]<temp[i2]){//如果tmp的mid以左坐标位置元素值小于tmp的mid以右的坐标位置元素值.
            	System.out.println("temp[i1]<temp[i2]");
            	data[cur]=temp[i1];//将较小的元素值写入data当前位置.
            	i1++;//mid左子表指针移动(mid左边元素坐标+1)
            }else{//mid以左大于mid以右.
            	System.out.println("else");
            	data[cur]=temp[i2];//将tmp的mid以右坐标位置的元素值写入data当前位置.
            	i2++;//mid右子表指针移动(mid右边元素坐标+1)
            }
            System.out.println("swap data:"+Arrays.toString(data)+" swap temp:"+Arrays.toString(temp));
        }
        //System.out.println("last data:"+Arrays.toString(data)+" last temp:"+Arrays.toString(temp));
        //System.out.println("l:"+l+" r:"+r);
    }
    
    public static void main(String[] args){
    	//int[] arrays = new int[]{10,2,4,8,5,1,6,3,7,9};
    	int[] arrays = new int[]{10,9,8,7,6,5,4,3,2,1};
    	new MergeSort().sort(arrays);
    	System.out.println(Arrays.toString(arrays));
    }

上面程序中：

1、首先通过递归将待排序数组data划分为若干个子序列，

2、合并某个data子序列时将该子序列内元素的复制到temp对应位置。

每个子序列有l,r,mid三个位置，分别对应它的：起始位置、结束位置、中间位置。

从l到mid(包含)为左子表，从mid+1到r(包含)为右子表。

声明两个指针(或标记)分别指向temp的：i1左子表头(l)位置、i2右子表头(mid+1)位置。

比较这两个位置的元素值，如果：

(1)左子表元素值小于右子表元素值，将左子表元素写入data当前位置。左子表指针右移，data当前位置右移。

(2)右子表元素值小于左子表元素值，将右子表元素写入data当前位置。右子表指针右移，data当前位置右移。

(3)左子表遍历完，即i1到达mid+1的位置。将右子表元素写入data当前位置。右子表指针右移，data当前位置右移，相当于把右子表内的剩余元素直接写入data中。

(4)右子表遍历完，即i2到达r+1的位置。将左子表元素写入data当前位置。左子表指针右移，data当前位置右移，相当于把做子表内的剩余元素直接写入到data中。

3、重复以上步骤合并每个子序列，最后通过递归步骤将排好序的子序列合并成为越来越大的有序序列。

 

性能分析：

平均时间复杂度是O(nlogn) 。

速度仅次于快速排序(且为稳定排序算法)。

 

空间复杂度：O(n)。

稳定性：稳定。

 

PS：另外有改进算法如下，有时间研究一下：

http://www.cnblogs.com/zhanglanyun/archive/2012/09/03/2669416.html

In-place Merge Sort (原地归并排序)

即时间复杂度还是O(nlogn)，但空间复杂度为O(1)的归并排序算法。