归并排序

简介

归并这个操作的意思是将两个有序的数组归并成一个更大的有序数组。而这种递归排序算法就叫做：归并排序。要将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。

原地归并的抽象方法

该方法先将所有元素复制到aux[]中，然后再归并回a[]中。方法在归并时（第二个for循环）进行了4个条件判断：左半边用尽（取右半边的元素）、右半边用尽（取左半边的元素）、右半边的当前元素小于左半边的当前元素（取右半边的元素）以及右半边的当前元素大于等于左半边的当前元素（取左半边的元素）。其中less()方法是一个辅助方法，作用是比较大小，可查看这篇文档。下面给出代码：

// 将a[lo..mid]和a[mid+1..hi]合并
public static void merge(Comparable[] a, int lo, int mid, int hi) {
    int i = lo, j = mid + 1;

    // 将a[lo..hi]复制到aux[lo..hi]
    for (int k = lo; k <= hi; k++) {
        aux[k] = a[k];
    }

    // 归并回到a[lo..hi]
    for (int k = lo; 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++];
        }
    }
}

自顶向下的归并排序

代码如下：

public class Merge {
    private static Comparable[] aux;        // 归并所需的辅助数组

    public static void sort(Comparable[] a) {
        aux = new Comparable[a.length];        // 一次性分配空间
        sort(a, 0, a.length - 1);
    }

    // 将数组a[lo..hi]排序
    private 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);    // 归并结果（代码见“原地归并的抽象方法”）
    }
}

自底向上的归并排序

代码如下：

public class MergeBU {
    private static Comparable[] aux;        // 归并所需的辅助数组

    // merge()方法的代码请见“原地归并的抽象方法”
    // 进行lgN次两两归并
    public static void sort(Comparable[] a) {
        int N = a.length;
        aux = new Comparable[N];

        // sz子数组大小
        for (int sz = 1; sz < N; sz = sz + sz) {
            // lo:子数组索引
            for (int lo = 0; lo < N - sz; lo += sz + sz) {
                merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
            }
        }
    }
}