博客

一、原理介绍


归并排序是以

归并

这个简单的操作为基础的，归并指的是将两个不同的有序数组合并为一个有序数组。因此我们在对数组进行排序时有了新的思路：先将数组分成两个子组，再对左子组和右子组分别进行排序，最后将这两个有序子组进行归并即可，这便是归并排序的基本思想。

另外，在对每一个子组进行排序时，同样可以使用归并排序，这便用到了递归的思想。

因此归并排序的核心就是递归+归并

。下图是归并排序的示意图：




二、代码实现


在归并排序的实现中，最重要的是实现归并操作，也是最难的，下图说明了实现归并操作的一种方式，并给出了相应的实现代码：

public class Merge {
    //测试
    public static void main(String[] args) {
        Integer[] I = {5,3,1,4,2,10,6,7};
        sort(I);
        for (int i = 0; i < I.length; i++) {
            System.out.println(I[i]);
        }
    }

    //实现归并操作
    public static void merge(Comparable[] a, int lo, int mid, int hi){
        //定义三个指针
        int p1= lo; //p1指向左子组的第一个元素
        int p2= mid+1;  //p2指向右子组的第一个元素
        int i = lo;     //i指向辅助数组的第一个元素
        //定义辅助数组
        Comparable[] aux = new Comparable[a.length];

        //实现归并
        while(p1<=mid || p2<=hi) {
            if (p1 > mid) aux[i++] = a[p2++];
            else if (p2 > hi) aux[i++] = a[p1++];
            else if (a[p1].compareTo(a[p2]) < 0) aux[i++] = a[p1++];
            else aux[i++] = a[p2++];
        }
        //将排序之后的aux数组复制给原来的数组a，这样a中对应的元素便是有序的
        for (int k = lo; k <= hi; k++) {
            a[k]=aux[k];
        }
    }
    public static void sort(Comparable[] a){
        sort(a,0,a.length-1);
    }
    public static 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);
    }
}