算法-排序（二） 归并排序

• 归并的概念
  将两个有序的数组合并成一个更大的有序数组的操作叫归并。
  根据归并这个而产生的一种排序叫做归并排序
• Java实现
  通过一个辅助数组来实现原地归并（在原数组上进行两个小数组归并操作），通过辅助数组的方法可以避免每次归并操作时都创建一个数组来放小数组合并后的新数组

public static void merge(Comparable[] a, int low, int mid, int hi){
        int i = low, j = mid+1;
        for(int k = low; k <= hi; k++){
            aux[k] = a[k];
        }
        for (int k = low; k <= hi; k++){
            if ((i > mid))  // 当左半边用尽
                a[k] = aux[j++];
            else if (j > hi) // 当右半边用尽
                a[k] = aux[i++];
            else if (less(aux[j], aux[i])) // 左边当前元素大于右边当前元素
                a[k] = aux[j++];
            else //  左边当前元素小于右边当前元素
                a[k] = aux[i++];

        }
    }

数组排序通过将其分为两个小数组，然后对两个小数组分别排序，然后在合并两个小数组。小数组然后分为两个更小的数组，然后在排序合并…

• 从大到小，化整为零

private static Comparable[] aux; //辅助空间数组

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

    }
    private static void sort(Comparable[] a, int low, int hi){
        if (hi <= low)
            return;
        int mid = (low+hi)/2;
        sort(a, low, mid);  //左半边排序
        sort(a, mid+1, hi); // 右半边排序
        if (less(a[mid], a[mid+1]))
            return;
        merge(a, low, mid, hi); // 归并
    }

• 优化方法
  当子数组规模比较小时，可以使用插入排序来替代归并排序

和自顶向下的方法相反，首先进行的是每两个元素进行归并（两个大小为1的数组），然后每四个元素进行一个归并，每八个元素，、、、、直到最后一次归并，最后一次归并时，第二个子数组可能比第一个子数组要小，如果不是的话，那么两个子数组是一样大。

• 从小到大，循序渐进
• 实现

public static void sort(Comparable[] a){
        int N = a.length;
        aux = new Comparable[a.length];
        for (int size = 1; size < N; size *= 2){  // size为每次归并的小数组大小
            for (int low = 0; low < N-size; low += 2*size){
                merge(a, low, low+size-1, Math.min(low+size+size-1, N-1));
            }
        }
    }

根据子数组大小进行两两归并，一开始子数组大小size为1，然后每次都加倍。最后一个子数组的大小只有在数组大小是size的偶数倍的时候才等于size，否则就比size小。