前言

排序算法的成本模型计算的是比较和交换的次数。less()方法对元素进行比较，exch()方法将元素交换位置。

1
2
3
4
5
6
7
8
9
private static boolean less(Comparable v, Comparable w) {
   return (v.compareTo(w) < 0);
}

private static void exch(Comparable[] a, int i, int j) {
   Comparable swap = a[i];
   a[i] = a[j];
   a[j] = swap;
}

原地归并方法

该方法将两个不同的有序数组归并到第三个数组中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
    // copy to aux[]
    for (int k = lo; k <= hi; k++) {
        aux[k] = a[k]; 
    }

    // merge back to a[]
    int i = lo, j = mid+1;
    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++];
    }
}

自顶向下的归并排序

自顶向下的归并排序应用了分治的思想，要对子数组a[lo..hi]进行排序，先将它分为a[lo..mid]和a[mid+1..hi]两部分，分别通过递归调用将它们单独排序，最后将有序的子数组归并为最终的排序结果。

自顶向下的归并排序

图为自顶向下的归并排序中归并结果的轨迹

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Merge {
    public static void sort(Comparable[] a) {
        Comparable[] aux = new Comparable[a.length];
        sort(a, aux, 0, a.length-1);
    }

    private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid + 1, hi);
        merge(a, aux, lo, mid, hi);
    }
}

自底向上的归并排序

实现归并排序的另一种方法是先归并那些微型数组，然后再成对归并得到子数组，如此这般地多次遍历整个数组，直到我们将整个数组归并到一起。

自底向上的归并排序

图为自底向上的归并排序中归并结果的轨迹

1
2
3
4
5
6
7
8
9
10
11
12
13
public class MergeBU {
    public static void sort(Comparable[] a) {
        int n = a.length;
        Comparable[] aux = new Comparable[n];
        for (int len = 1; len < n; len *= 2) {
            for (int lo = 0; lo < n-len; lo += len+len) {
                int mid  = lo+len-1;
                int hi = Math.min(lo+len+len-1, n-1);
                merge(a, aux, lo, mid, hi);
            }
        }
    }
}

特点

  • 归并排序的空间复杂度不是最优的
  • 和选择排序一样，排序的性能不受输入数据的影响，但表现比选择排序好的多

复杂度分析

  • 最坏情况时间复杂度 O(nlogn)
  • 最好情况时间复杂度 O(nlogn)
  • 平均情况时间复杂度 O(nlogn)
  • 空间复杂度 O(n)
  • 稳定

参考资料