Algorithms, Part I 5-Mergesort

Algorithms, Part I 5-Mergesort

HC_Plantern 61 2022-02-06

5-Mergesort

插入排序

基本做法

  1. 将数组分成两半
  2. 递归地对这两部分排序
  3. 将已排好序的两部分合并

合并的代码实现

    // stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
        // precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
        assert isSorted(a, lo, mid);
        assert isSorted(a, mid+1, 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++];
        }

        // postcondition: a[lo .. hi] is sorted
        assert isSorted(a, lo, hi);
    }

排序过程中的状态如下图

image.png

完整代码实现

public class Merge {

    private static void merge(...) {
        // as before
    }

    // mergesort a[lo..hi] using auxiliary array aux[lo..hi]
    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);
    }

    /**
     * Rearranges the array in ascending order, using the natural order.
     * @param a the array to be sorted
     */
    public static void sort(Comparable[] a) {
        Comparable[] aux = new Comparable[a.length];
        sort(a, aux, 0, a.length-1);
        assert isSorted(a);
    }
}

大致排序过程如下图

image.png

复杂度分析

空间:

一个长度为$n$的数组

时间:

  1. 对于两个长度为$n$的数组进行合并需要$\leq6n$次操作
  2. 递归树一共有$log_2n+1$层
  3. 对于第$j$层(从0开始计数),一共有$2j$个需要递归的数组,其中两个一组。每组数组的长度为$\frac{2j}$
  4. 因此,每一层所需要的操作数$\leq2j*6(\frac{2j})=6n$,总计$6n(log_2n+1)$次操作

以下是证明相关图片

注意这里的每一个圈圈代表的是两个数组merge的过程

image.png

image.png

image.png

改进方案

  • 对于小数组采用插入排序:规模较小时插入排序相较于归并排序的效率更高,开销更少。

  • 如果已经排好序,就取消合并的操作:检查左半部分最大的元素是否比右半部分最小的元素要小

  • 避免辅助数组的复制操作:每次归并时交换原数组与辅助数组的参数位置,以此规避了每次合并时都要将元素复制到辅助数组的操作,节省时间。

    • image.png

迭代的插入排序

将递归改成迭代

image.png

代码如下:

public class MergeBU {


    // stably merge a[lo..mid] with a[mid+1..hi] using aux[lo..hi]
    private static void merge(...) {
        // as before
    }

    /**
     * Rearranges the array in ascending order, using the natural order.
     * @param a the array to be sorted
     */
    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);
            }
        }
        assert isSorted(a);
    }

排序复杂度

排序决策树

以三个元素的排序为例,将所有的排序情况列出来画成树

image.png

命题:任何通过比较的排序方法至少需要 $lg(N!)$ ~ $NlgN$次比较

证明:

image.png

image.png

特殊情况下复杂度可能降低

  1. 部分有序数组
  2. 有重复元素
  3. 利用数字和字符比较

内部静态比较类 comparators

假如一个类拥有多个数据,如果要按照不同的数据对这个对象进行排序,就需要用到comparators

具体做法:

  1. 通过内部静态类的方式创建comparators
  2. 比较时将comparators通过参数传递进sort方法

image.png

插入排序修改成使用comparator,即将特定的对象类型从Comparable改写成Object

稳定性

假如一个对象有两组数据,我们希望对这两组数据排序而不影响元素的相对顺序,那么就要求排序算法是稳定的

image.png

  • 稳定:插入排序、归并排序、冒泡排序
  • 不稳定:选择排序、Shell排序、快速排序、堆排序