【Algorithms公开课学习笔记5】排序算法part2——归并排序

Merge Sort 归并排序

0.前言

前面的文章已经分析了选择排序、插入排序、希尔排序等基础排序算法，本文将分析一个性能极高的排序算法——归并排序。在Java编程的时候，我们经常会使用到一个API：Arrays.sort(o),如果括号中的o是对象的话，那么该API就是调用归并排序算法（结合了插入排序）来完成排序的。顺带一提，如果括号里的o是java基本类型，那么该API就会调用快速排序算法。关于快速排序分析，将会在下一篇文章。

1.归并排序

原理

归并排序运用了递归的思想：

input:数组s

sort(数组s):
    1.将输入的数组s对半分成两部分
    2.对左右两部分（递归地）调用sort()
    3.对左右两部分调用merge()进行合并

merge():
    1.确定需要合并的两部分数组有序，否则不能合并
    2.复制一个辅助数组aux，存放原数组
    3.合并数组的操作就是将这两部分数组按序摆放后存入原数组，辅助数组提供原位置参考（这里可以使用插入排序算法来排序）

代码实现

public class Merge{
    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi){
        //保证需要合并的两部分是有序的
        assert isSorted(a, lo, mid);
        assert isSorted(a, mid+1, hi);
        //赋值辅助数组
        for (int k = lo; k <= hi; k++){
            aux[k] = a[k];
        }
        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++];
        }
        assert isSorted(a, 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);
    }

    //外部排序算法
    public static void sort(Comparable[] a){
        //定义辅助数组，千万不要在递归算法内定义
        aux = new Comparable[a.length];
        sort(a, aux, 0, a.length - 1);
    }
}

注意事项：

• 1.assert语句是用来测试程序中的假设条件的，如果假设条件不满足true的话就会抛出异常exception。运行时是默认关闭的，可以通过设置打开。
• 2.辅助数组千万不能在递归算法内定义，否则会极大的浪费空间

时间性能

归并排序中最多有NlgN次比较和6NlgN次数组访问。以下通过数学来分析一下NlgN次比较值的由来：

将比较compare的次数记D(N), D(N)<=D(N/2)+D(N/2)+N, 假设N是2的指数
那么D(N)<=2D(N/2)+N

D(N) /N = 2D(N/2) /N + 1
= D(N/2) /(N/2) + 1
= D(N/4) /(N/4) + 1 + 1
= D(N/8) /(N/8) + 1 + 1 + 1
. . .
= D(N/N) /(N/N) + 1 + 1 + ... + 1
= lgN

D(N) = NlgN

另外，通过树结构来分析也可以得出此结论：

空间占用率

归并排序将要利用额外的辅助数组来实现合并，而辅助数组大小需要为N

优化

优化一：当数组被分割到很小的时候（临界值），改用插入排序算法来对其进行排序。这个临界值可以根据实际情况来确定。

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi){
    //临界值命名为CUTOFF
    if (hi <= lo + CUTOFF - 1){
        Insertion.sort(a, lo, hi);
        return;
    }
    int mid = lo + (hi - lo) / 2;
    sort (a, aux, lo, mid);
    sort (a, aux, mid+1, hi);
    merge(a, aux, lo, mid, 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);
    //判断合并前是否已经全有序
    if (!less(a[mid+1], a[mid])) return;
    merge(a, aux, lo, mid, hi);
}

优化三：去掉对辅助数组复制赋值的代码，这并不能节约空间，但可以节省时间。（比较难理解）

2.自底向上的归并排序

原理

自底向上的归并排序没有使用递归，而是根据一个从小到大（通常从个开始）序列来不断合并数组：

input:数组s

sort(数组s):
    1.初始合并规模sz=1
    2.合并sz的子数组，形成sz*2的数组
    3.sz=sz*2
    4.loop

merge():
    1.确定需要合并的两部分数组有序，否则不能合并
    2.复制一个辅助数组aux，存放原数组
    3.合并数组的操作就是将这两部分数组按序摆放后存入原数组，辅助数组提供原位置参考（这里可以使用插入排序算法来排序）

代码实现

public class MergeBU{
    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi){
        //保证需要合并的两部分是有序的
        assert isSorted(a, lo, mid);
        assert isSorted(a, mid+1, hi);
        //赋值辅助数组
        for (int k = lo; k <= hi; k++){
            aux[k] = a[k];
        }
        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++];
        }
        assert isSorted(a, lo, hi);
    }

    public static void sort(Comparable[] a){
        int N = a.length;
        Comparable[] aux = new Comparable[N];
        //初始sz=1
        for (int sz = 1; sz < N; sz = sz+sz)
            for (int lo = 0; lo < N-sz; lo += sz+sz)
                merge(a, aux, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
    }
}

时间性能

归并排序中最多有NlgN次比较和6NlgN次数组访问。但实际实验测试的时间比传统的归并排序算法多10%。

空间占用率

归并排序将要利用额外的辅助数组来实现合并，而辅助数组大小需要为N

3.Comparator inteface

上一篇文章提到了Comparable接口，以及实现该接口必须重写的compareTo()方法。传送门
实现Comparable接口的类对象可以在compareTo()方法内自定义比较规则；
而实现Comparator接口的类对象则可以在重写的compare()方法内自定义排序规则，具体如下:

//定义的时候
private class SlopComparator implements Comparator<Point> {
    @Override
    public int compare(Point o1, Point o2) {
        double slop1 = slopeTo(o1);
        double slop2 = slopeTo(o2);
        if (slop1 > slop2) {
            return 1;
        } else if (slop1 < slop2) {
            return -1;
        } else {
            return 0;
        }
    }
}

// 实现的时候
// 对数组p，按照对p[0]的斜率排序
Arrays.sort(p, p[0].slopeOrder());

4.稳定性stability

稳定性stability是排序算法在实践中的一个重要指标。所谓的稳定性是指数组的相同值在排序的过程中会保持其位置的相对性。下图所示就是具有相对性排序结果：

判断相对性的一个重要依据就是：值在一次交换的过程中是否会跨过与其相同的值，即是否存在长距离的交换。
在插入排序中，每次交换都是相邻的值之间的交换，所以不会跨过与其相同的值，因此是稳定的排序算法。
在选择排序中，值交换都是直接放在其最终位置上的，所以很可能会跨过与其相同的值，因此不是稳定的排序算法。

在目前已经学习过的算法中，
稳定的排序算法：插入排序，归并排序
不稳定的排序算法：选择排序，希尔排序，快速排序

5.第3周作业答案

Collinear