从零开始的算法之路03——排序

游戏规则

我们关注的是重新排列数组元素的算法，其中每个元素都有一个主键。排序算法的目标就是将所有元素的主键按照某种方式排列。排序后索引较大的主键大小大于等于索引较小的主键。在 java 中，元素通常是对象，对主键的抽象描述则是通过实现 Comparable 接口实现的。以下则是“排序类算法模板”：

public class Example {
    // 排序算法的实现
    public static void sort(Comparable[] a) {
        //todo
    }
    
    // 比较前者是否小于后者
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }
    
    // 交换数组中两个位置的元素
    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    
    // 打印数组
    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
    
    // 测试数组是否有序
    public static boolean isSorted(Comparable[] a) {
        for (int i = 1; i < a.length; i++) {
            if (less(a[i], a[i-1]))
                return false;
        }
        return true;
    }
}

选择排序

一种最简单的排序算法：首先找到数组中最小的元素，其次将它和数组中第一个元素交换位置。再次在剩下元素中找到最小元素，将它与数组第二个元素交换位置……若此反复，直到排序完成。

// 排序算法的实现
    public static void sort(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            int min = i; // 最小元素索引
            for (int j = i + 1; j < a.length; j++) {
                if (less(a[j], a[min]))
                    min = j; // 最小元素索引更新
            }
            exch(a, min, i); // 与最小元素交换位置
        }
    }

选择排序两大特点：

运行时间和输入无关

数据移动是最少的（数组长度）

插入排序

与选择排序一样，当前索引左边的元素都是有序的，但他们的最终位置还不确定，为了给更小的元素腾出空间，他们可能会被移动。

// 排序算法的实现
    public static void sort(Comparable[] a) {
        for (int i = 1; i < a.length; i++) {
            // 从当前索引逆向循环比较，若比前一位小，则说明需要交换位置，继续循环
            for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
                exch(a, j, j-1);
            }
        } 
    }

和选择排序不同，插入排序所需的时间取决于输入中元素的初始顺序，若数组已经有序（或接近有序）速度会快得多。

希尔排序

希尔排序是基于插入排序的改良算法。其思想是使数组中任意间隔为 h 的元素都是有序的。这样的数组被称为 h 有序数组。一个 h 有序数组就是 h 个互相独立的有序数组编织在一起组成的一个数组。

实现希尔排序的一种方法是对于每个 h ，用插入排序将 h 个子数组独立排序。但因为子数组之间是独立的，一个更简单的方法是在 h 子数组中将每个元素交换到比它大的元素之前去（也就是说将比它大的元素都往右移动一格），换言之，插入排序算法是每次都往前1格进行交换，希尔排序只需要改为 h 即可。

// 排序算法的实现
    public static void sort(Comparable[] a) {
        int N = a.length; // 数组长度
        int h = 1;
        while (h < N/3) {
            h = 3 * h + 1; // h 初始分组确定
        }
        
        while (h >= 1) {
            // 将数组变为h有序
            for (int i = h; i < N; i++) {
                for (int j = i; j >= h && less(a[j], a[j-h]); j -= h)
                    exch(a, j, j-h);
            }
            // 缩小h，进行更小的h组排序 （当h=1时就是插入排序，但此时数组已接近有序）
            h = h/3;
        }
    }

归并排序

要将一个数组排序，可以先（递归地）将它分成两半分别排序，然后把结果归并起来。归并排序最吸引人的性质是它能够保证将任意长度为 N 的数组排序所需时间和 NlogN 成正比，主要缺点则是它需要的额外空间与 N 成正比。

原地归并

实现归并最直截了当的方法是将两个不同的有序数组归并到第三个数组中，但多次归并意味着不停创建新的数组。我们更希望有一种原地归并的方法，在归并的过程中不用使用额外的空间。这里有个利用辅助数组复制原数组的实现：

private static Comparable[] aux; // 归并所需辅助数组

// 归并数组a[lo, mid]、a[mid+1, hi]
private static void merge(Comparable[] a, int lo, int mid, int hi) {
    int i = lo, j = mid+1; // 先用i, j 两个指针保存一下两个数组的起始位置

    // 复制原数组到aux进行备份, aux不做移动操作，仅用来比较大小和取数据
    for (int k = lo; k <= hi; k++)
        aux[k] = a[k];

    // 进行归并
    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++]; // 若i、j指针均未超过上限，进行数值比较，取值小的那一个
        else
            a[k] = aux[i++]; // 若i、j指针均未超过上限，进行数值比较，取值小的那一个
    }
}

自顶向下归并

基于原地归并的实现，可以用分治思想来实现排序：想将一个大数组排序，可以先把数组切分为两个子数组，依次排序。

// 排序算法的实现
    public static void sort(Comparable[] a) {
        aux = new Comparable[a.length];
        sort(a, 0, a.length-1);
    }
    
    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); // 归并结果
    }

自底向上归并

另一种反过来的分治思想，可以先把长度为1的数组两两合并，再以长度为2的数组进行两两合并，直至最终成为一个大的有序数组。

// 排序算法的实现
    public static void sort(Comparable[] a) {
        int N = a.length;
        aux = new Comparable[N];
        for (int sz = 1; sz < N; sz = 2*sz) // sz 子数组大小
            for (int lo = 0; lo + sz < N; lo += 2*sz)
                merge(a, lo, lo + sz -1, Math.min(lo+2*sz-1, N-1)); 
    }

快速排序

快排也是基于分治思想的一种算法，和归并排序类似，也是将一个数组分成2个子数组，各自独立排序。不同点在于，归并排序中递归发生在处理数组之前，而在快排中递归发生在处理数组之后。归并排序是将数组等分为两半，但快排切分（partition）位置则取决于数组的内容。

// 排序算法的实现
public static void sort(Comparable[] a) {
    sort(a, 0, a.length-1);
}

private static void sort(Comparable[] a, int lo, int hi) {
    if (hi <= lo)
        return; // 递归出口，上下限交接时退出
    int j = partition(a, lo, hi); // 找出切分索引j;
    sort(a, lo, j-1); // 递归排序j左边的数组
    sort(a, j+1, hi); // 递归排序j右边的数组
}

从代码可以看出，快排的核心算法在于切分如何实现，我们希望切分后，j 所在的元素正好处于正确位置，即 j 的左边元素均比它小，而右边元素均比它大。

private static int partition(Comparable[] a, int lo, int hi) {
    // 选取标志位数值，这里选取左起第0位
    Comparable flag = a[lo];
    // 定义左右指针，分别是标志位和右上限+1，两边都预留了1位冗余，因为下面要做前置自增减运算
    int i = lo, j = hi + 1; 
    while (true) {
        // 左指针自增，当元素值大于标志时停止
        // 这里统一采用前置自增减，为的是先计算后使用，保证比较的数值和后面交换的索引是及时对应的
        while (less(a[++i], flag))
            // 检测左指针是否到达右上限，若到达也停止
            if (i == hi)
                break;
        // 右指针自减，当元素值小于标志时停止
        while (less(flag, a[--j]))
            // 检测右指针是否到达左下限，若到达也停止
            if (j == lo)
                break;
        // 检测左右指针是否相交，若相交退出循环
        if (i >= j)
            break;
        // 交换左右指针所在的元素，即可保证左边区域一直比标志小，右边区域一直比标志大
        exch(a, i, j);
    }
    // 循环结束时j所指元素肯定是小于标志的，所以交换它俩，保证标志左侧元素始终小于标志
    // 如果标志位定的右起第0位hi 这里就要交换i
    exch(a, lo, j);
    // 返回最终标志所在索引，即正确的位置，也就是切分点
    return j;
}

但快排有个缺点，切分不平衡时会非常低效，设想一下如果第一次从最小的元素切分，第二次从第二小的元素切分，如此这般，每次调用只会移除一个元素。这会导致一个大子数组需要切分很多次。

我们当然可以采用数组小于一个阈值时切换成插入排序，对于小数组，插入排序要快于快排。

也可以使用三取样切分，也就说标志位取3个并用大小居中的元素来切分。

三向切分的快速排序

还有一种简单的想法，来应对实际应用中出现含有大量重复元素时：将数组切分为三部分，分别对应小于、等于、大于切分元素的数组元素。

具体实现：从左到右遍历数组一次。维护一个指针 lt 使得 a[lo..lt-1] 的元素都小于 flag，一个指针 gt 是的 a[gt..hi] 中元素都大于 flag，a[i..gt] 中的元素都还未确定。一开始 i 和 lo + 1 相等：

• a[i] 小于 flag， 将 a[lt] 和 a[i] 交换，将 lt 和 i 加一；
• a[i] 大于 flag， 将 a[gt] 和 a[i] 交换，将 gt 减少一；
• a[i] 等于 flag， 将 i 加一；
• 将 i 和 gt 重合时结束。

// 排序算法的实现
public static void sort(Comparable[] a) {
    sort(a, 0, a.length-1);
}

private static void sort(Comparable[] a, int lo, int hi) {
    if (hi <= lo)
        return; // 递归出口，上下限交接时退出
    int lt = lo, i = lo + 1, gt = hi;
    Comparable flag = a[lo];
    while (i <= gt) {
        if (less(a[i], flag))
            exch(a, lt++, i++);
        else if (less(flag, a[i]))
            exch(a, gt--, i);
        else
            i++;
    }

    sort(a, lo, lt-1); // 递归排序左边的数组
    sort(a, gt+1, hi); // 递归排序右边的数组
}

堆排序

关于堆排序相关的概念在下一篇讲优先队列的博文中进行了详细描述。

我们可以把任意优先队列变成一种排序方法。将所有元素插入一个查找最小元素的优先队列，然后重复调用删除最小元素的操作来将他们按顺序删去。用无序数组实现的优先队列这么做相当于进行一次选择排序，而基于堆的优先队列这么做就是一种经典而优雅的排序算法——堆排序。

堆排序分两个阶段：先构造堆后删除元素排序。

构造堆我们可以跳过大小为1的子堆，因为它们并无子结点，他们占总数的一半。而对他们的父节点从下至上调用sink() 函数最终就能得到一个堆。

而排序阶段我们可以将根结点和末尾元素交换，长度减一，再将新的根结点下沉，如此重复即可有序。

这里要注意的是二叉堆数组是基1的，在 less 和 exch 函数中我们要将索引-1（将 a[0] 至 a[N-1] 排序）。

public class Heap {
    // 排序算法的实现
    public static void sort(Comparable[] a) {
        int N = a.length;
        // 构造堆
        for (int k = N/2; k >= 1; k--) {
            sink(a, k, N);
        }
        // 排序
        while (N > 1) {
            exch(a, N--, 1);
            sink(a, 1, N);
        }
    }

    private static void sink(Comparable[] a, int k, int N) {
        while (k <= N/2) {
            int j = 2*k;
            if (j < N && less(a, j, j+1))
                j++;
            if (less(a, k, j)) {
                exch(a, k, j);
                k = j;
            } else {
                break;
            }
        }
    }

    // 比较前者是否小于后者
    private static boolean less(Comparable[] a, int i, int j) {
        i--; j--; // 构造二叉堆的数组是基1的，这里要减去（对a[0]至a[N-1]操作）
        return a[i].compareTo(a[j]) < 0;
    }

    // 交换数组中两个位置的元素
    private static void exch(Comparable[] a, int i, int j) {
        i--; j--; // 构造二叉堆的数组是基1的，这里要减去（对a[0]至a[N-1]操作）
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    // 打印数组
    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Comparable[] arr = {45, 2, 17, 0, 1, 85, 3, 51, 20};
        Heap.sort(arr);
        Heap.show(arr);
    }
}

各种排序算法的性能特点