Ch2 排序

在本章中, 我们将学习数种经典的排序算法, 并实现 优先队列 这一基础数据类型, 讨论比较排序算法的理论基础并最后总结若干排序算法和优先队列的应用.

2.1 初级排序算法

我们首先研究两种 初级的排序算法 和其中一种的一个变体. 在此, 我们关注的主要对象是 重新排列数组元素 的算法, 其中 每个元素都有一个主键. 排序算法的目的就是将 所有元素的主键 按照某种方式排列, 在经过排序后索引较大的主键大于等于索引较小的.

下面, 我们规定排序代码的结构和模板:

我们会将排序代码放在类的 sort() 方法中, 该类还包含辅助函数 less(), exch() 和示例用例 main(), 其中 less() 方法对元素进行比较, 而 exch() 方法将元素交换位置. 为了区分不同的算法, 我们还可以为相应的类取不同的名字, 用例可以按照名字调用不同的实现.

为了确保数组的初始状态是不影响排序算法的成功与否的, 我们会在测试代码 main() 中添加语句 assert isSorted(a) 来确认经过排序后的数组元素都是有序的.

在确认算法的有效性后, 我们还需要对其性能进行评估. 首先, 我们需要计算各个排序算法在 不同的随机输入下的基本操作的次数 (包括比较和交换的数量. 对于不交换元素的算法, 我们需要计算访问数组的次数). 随后, 我们用这些数据来估计算法的性能.

除此以外, 我们也需要关注排序算法的 额外内存开销. 原地排序算法 是 除了函数调用所需的栈和固定数目的实例变量之外无需额外内存 的算法, 而需要额外内存空间来存储一份数组副本的则被列为 其他排序算法.

public class Example {
    public static void sort(Comparable[] a) {
        // see each sorting algorithms
    }

    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++) {
            StdOut.print(a[i] + " ");
        }
        StdOut.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 main(String[] args) {
        String[] a = In.readStrings();
        sort(a);
        assert isSorted(a);
        show(a);
    }
}

选择排序

选择排序是最简单的排序算法之一. 它的工作原理如下:

首先在数组的 $n$ 个元素中找到 最小的元素, 将其和 数组的第一个元素 交换位置, 无论数组的第一个元素是否为数组中最小的元素.

随后, 在剩下的 $n-1$ 个元素中再找到最小的, 并和整个数组中的第二位交换位置, 如此往复直到只剩下 $1$ 个待排序元素, 此时整个数组显然已经被完全排序. 我们称这种排序方法为 选择排序, 因为它 不断地在选择剩余元素中的最小者.

选择排序的内循环仅仅在比较 当前元素 和 目前已知的最小元素, 而交换元素的代码在内循环之外. 由于每次交换必能排定一个元素, 故交换的总次数为 $N$, 算法的时间效率取决于 比较的次数.

public class Selection {
    public static void sort(Comparable[] a) {
        int N = a.length;   // length of the array a
        // then we exchange a[i] with the smallest elem in a[i+1, ..., N]
        for (int i=0; i<N; i++) {   
            int min=i;  // index of the min element
            for (int j=i+1; j<N; j++) {
                if (less(a[j], a[min])) {
                    min = j;
                }
            }
            exch(a, i, min);
        }
    }
}

命题 2.1

对于长度为 $N$ 的数组, 选择排序大约需要 $\frac{N^2}{2}$ 次比较和 $N$ 次交换.

证明

基于算法的 排序轨迹 和 工作原理 可知, 由于每次交换只会对 $1$ 个元素进行排序, 因此对于长度为 $N$ 的数组总共交换次数也为 $N$.
由于数组索引 $i \in [N-1]$ 的元素都会进行 $N-1-i$ 次比较, 因此将整个数组进行排列共需要
\[\sum_{i=1}^{N-1}i = \frac{N(N-1)}{2} \sim \frac{N^2}{2}\]
次比较. $\blacksquare$

总结:

选择排序是一种简单的排序算法, 其具备两个显著特征:

运行时间和输入无关:
选择排序无法利用输入数组的 初始状态, 它对一个已经有序或者元素全部相等的数组进行排序所耗费的时间和对一个乱序数组而言是 完全相同的, 因为它在对任何一个元素进行排序时执行的每一次全数组扫描都不能为下一次排序提供任何有效信息, 这一性质在某些情况下是制约运行速度的缺点.
数据移动最少:
由于每次交换均会改变 两个数组元素的值, 因此选择排序对数组的交换次数和数组大小是 线性关系, 而我们即将讨论的其他任何算法都不具备该特征.

插入排序

要理解插入排序的原理, 我们可以从扑克牌的整理方式中获得启发. 和理牌时我们需要将一张牌插入到其他 已经有序 的牌中的适当位置一样, 在插入排序的实现中, 为了给要插入的元素腾出空间, 需要将 其余所有元素 在插入之前都 右移一位.

与选择排序相同, 当前索引左侧的所有元素都是有序的, 只不过它们的最终位置还不确定, 但当 索引到达数组右端 时, 数组排序就完成了. 不同于选择排序, 插入排序的耗时受输入中元素初始顺序的影响.

命题 2.2

对于随机排列的长为 $N$ 且 主键不重复 的数组, 平均情况下插入排序需要约 $\frac{N^2}{4}$ 次比较和交换. 最坏情况下需要约 $\frac{N^2}{2}$ 次比较和交换, 最好情况下需要 $N-1$ 次比较和 $0$ 次交换.

证明

通过一个 $N \times N$ 的 排序轨迹表 可以很容易地得到交换和比较的次数. 最坏情况下, 轨迹表 对角线之下 的所有元素都需要移动位置, 而最好情况下都不需要; 对于 随机排列 的数组, 在平均情况下每个元素都可能向后移动 半个数组的长度, 故交换总数总是对角线之下元素总数的 $\frac{1}{2}$.

比较的总次数为交换的次数 减去一个额外项 再加上 $N$. 这个额外项是, 在所有的插入操作中, 将被插入的元素恰好是数组中位于索引前的那部分中的最小元素这种情况总共出现的次数. 在最坏情况下, 这一项相比交换总数可以 忽略不计, 而在最好情况下, 这一项等于 $1$. $\blacksquare$

(注: 为了方便理解此处的额外项恰好是原书描述的额外项取 相反数再加 $N$, 原文为 “an additional term equal to N minus the number of times the item inserted is the smallest so far”.)

对于实际应用中常见的某些类型的 非随机数组, 插入排序是很有效的: 当我们使用插入排序尝试对一个有序数组或所有主键均相同的数组进行排序时, 插入排序能够立即识别每个元素都在合适的位置之上 (因为其执行交换操作的内层循环判断条件就是元素是否依序排列), 此时 其运行时间是线性的, 而选择排序就需要 $n^2$ 级别的运行时间.

public class Insertion {
    public static void sort(Comparable[] a) {
        int N = a.length;
        for (int i=1; i<N; i++) {
            // insert element a[i] into the already-sorted sub-arrray:
            // [a[0], ..., a[n-2], a[n-1]]
            for (int j=i; j>0 && less(a[j], a[j-1]); j--) {
                // less(a[j], a[j-1]) == "a[j]<a[j-1]? true : false"
                // it means we only proceed the iteration iff a[j] is not being 
                // placed into the right place yet
                exch(a, j, j-1);
            }
        }
    }
}

我们下面考虑 部分有序数组:

定义: 倒置

数组中两个 顺序颠倒 的元素称为倒置.

定义: 部分有序数组

如果数组中 倒置的数量 小于 数组大小的某个倍数, 则称这个数组是 部分有序 的.

一些典型的部分有序数组是:

数组中每个元素距离其正确位置都不远.
一个有序的大数组接一个小数组.
只有几个元素的位置不正确的数组.

命题 2.3

插入排序所需要的交换操作和数组中 倒置的数量 相同, 且有:
倒置数量 $+$ 数组大小 $-1 \geqslant$ 需要的比较次数 $\geqslant$ 倒置的数量.

证明

插入排序执行的每一次交换都改变了 一对顺序颠倒的元素位置, 等价于 减少了一对倒置. 而当 倒置数量为 $0$ 时, 排序就完成了, 而每次交换都和一次比较对应, 因此 (需要的比较次数 $\geqslant$ 倒置的数量); 而 $1$ 到 $N-1$ 之间的每个 $i$ 都可能需要一次 额外的比较, 故 (倒置数量 $+$ 数组大小 $-1 \geqslant$ 需要的比较次数). $\blacksquare$

对插入排序和选择排序算法的比较

下面我们讨论插入排序和选择排序的性能孰优孰劣. 比对算法的速度这个问题会在我们今后对算法的学习中反复出现. 根据 Ch 1.4 所介绍的方法, 我们将通过以下的步骤对比两个算法:

实现并调试它们.
分析它们的基本性质.
对它们的相对性能作出猜想.
设计并进行实验对猜想进行验证.

在前两个小节中我们已经给出了选择排序和插入排序算法的实现, 因此我们已经完成了第一步. 而上两个小节中所描述和证明的三个命题组成了流程的第二步. 我们下面将依次完成第三步和第四步.

在实现了算法后, 我们需要确定一个适当的输入模型. 对排序而言, 上两个小节中的三个命题使用的自然输入模型假设数组中的元素 随机排序, 且 主键值不会重复. 而对于有 很多重复主键 的应用而言, 我们需要一个更复杂的模型.

我们已经知道, 对于随机排序数组, 两个算法的运行时间都是 $n^2$ 级别. 我们可由此得到下列猜想:

性质

对于 随机排序的无重复主键的数组, 插入排序和选择排序的运行时间是 $n^2$ 级别 的, 两者之比应该是一个较小的常数.

对于性能实验的设计和猜想的验证, 详见原书翻译版 $\text{P}254-257$ 页, 此处不做摘录和笔记.

希尔排序

下面我们讨论一种 基于插入排序 的快速的排序算法. 插入排序对于 大规模乱序数组表现不佳, 因为它只会 交换相邻的元素, 因为元素只能一点点的 从数组的一端移动到另一端.

为了加快速度, 希尔排序通过 交换不相邻的元素对数组的局部进行排序并最终用插入排序将局部有序的数组排序 对插入排序进行了简单的改进.

定义: $h$ 有序数组

$h$ 有序数组是由 $h$ 个相互独立的有序数组编织在一起组成的一个数组, 在这个数组中, 任意间隔为 $h$ 的元素都是有序的.

$h$ 为希尔排序中可自定义的一个控制被交换元素距离的参数, 其思想是让 数组中任意间隔为 $h$ 的元素都是有序的. 在进行排序时, 如果 $h$ 很大的话, 只需要经过一次交换我们就能将元素移动到很远的地方.

public class Shell {
    public static void sort(Comparable[] a) {
        int N = a.length;  
        int h = 1;
        // dynamically calculate h's val
        while (h < N/3) {
            h = 3*h + 1;
        }
        // in this implementation, we use geometric progression: 
        // [1, 3, 9, ..., N/3] for h in different iterations
        while (h >= 1) {
            for (int i=h; i<N; i++) {
                // insert a[i] into [a[i-h], a[i-2h], a[i-3h], ...]
                for (int j=i; j>=h && less(a[j], a[j-h]); j -= h) {
                    exch(a, j, j-h);
                }
            }
            h = h/3;    // decrease h after each iteration
        }
    }
}

希尔排序权衡了子数组的规模和 有序性. 在排序之初, 各个子数组都很短, 排序后各个子数组部分有序, 这两种情况都适合插入排序, 而子数组部分有序的程度取决于递增序列的选择.

选择递增序列是一项复杂的工作, 算法的性能取决于 $h$ 与序列中 $h$ 之间的数学性质. 我们在上文的实现中采用的简单递增序列与复杂递增序列的性能接近, 但可以证明复杂的序列在最坏情况下的性能表现是优于这个简单的序列的.

和选择排序, 插入排序不同的是, 希尔排序也可以用于 大型数组, 它对任意排序的数组表现也很好.

2.2 归并排序

我们在本节中将要讨论的算法都基于归并这个操作, 也就是将 两个有序的数组 归并成一个 更大的有序数组.

一种简单的递归排序算法: 归并排序 的工作原理就是基于这个操作之上的. 要将一个数组排序, 可以先 递归地 将它分成两半分别排序, 然后将结果归并起来. 归并排序能保证, 它排序 任意长度为 $N$ 的数组 所需要的时间和 $N\log(N)$ 成正比, 而它需要的额外空间和 $N$ 成正比.

原地归并的抽象方法

实现归并的一种简单方法是将两个不同的有序数组归并到第三个数组中. 虽然我们利用两个数组中的元素都实现了 Comparable 接口的特性可以指甲创建一个适当大小的数组并将两个数组中的元素由小到大依次放入其中, 但在需要进行多次归并 (如对一个很大的数组排序) 时, 如果每次归并都需要创建一个新数组存储排序结果就会带来存储空间使用上的问题. 因此, 我们需要考虑一种 能够在原地归并 的方法, 这样就可以分别将前半部分和后半部分排序, 然后在数组中移动元素而无需使用额外的空间.

下面我们给出一个抽象化原地归并操作的静态方法, 它将归并过程中涉及到的所有元素复制到一个辅助数组中, 然后再将归并的结果放回到原数组中:

public static void merge(Comparable[] a, int lo, int mid, int hi) {
    // merge a[lo...mid] and a[mid+1...high]
    int i = lo;
    int j = mid+1;
    
    // first copy a[lo...high] to aux[lo...high]
    for (int k=lo; k<high; k++) {
        aux[k] = a[k];
    }

    // then merge them and modify a[]
    for (int k=lo; k<=high; k++) {
        if (i>mid) {            // used all left-side subarray
            a[k] = aux[j++];
        } else if (j>hi) {      // used all right-side subarray
            a[k] = aux[i++];
        } else if (less(aux[j], aux[i])) {  // right < left
            a[k] = aux[j++];
        } else {                            // left < right
            a[k] = aux[i++];
        }
    }
}

该方法先将 a[] 中的所有元素复制到新数组 aux[] 中, 然后再归并回 a[]. 方法在执行归并时进行了四个 for 条件判断: 左半边子数组用尽 (故取右半边), 右半边子数组用尽 (故取左半边), 右半边子数组元素小于等于左半边和左半边子数组元素小于等于右半边 (故取较小的那一个).

自顶向下的归并排序

我们再介绍一个基于 原地归并的抽象实现 实现了 递归归并 的算法:

public class Merge {
    private static Comparable aux[];     // auxiliary array used in merge()
    
    public static void sort(Comparable a[]) {
        aux = new Comparable[a.length];
        sort(a, 0, a.length-1);
    }

    public static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int mid = lo + (hi - lo)/2;
        sort(a, lo, mid);       // sort left side
        sort(a, mid+1, hi);     // sort right side
        merge(a, lo, mid, hi);  // then merge them finally
    }
}

要理解归并排序, 我们可以研究该方法 调用的动态情况. 要将 $a[0…15]$ 排序, sort 方法会调用自身将 $a[0…7]$ 排序, 再在其中调用自己将 $a[0..3]$ 和 $a[4..]$ 排序, 而在将 $a[0], a[1]$ 排序后才会开始反过来合并数组. 在合并回 $a[0…7]$ 后, 再去进行后续的归并. 显然, sort() 方法的作用实际上在于 安排多次 merge() 方法调用的正确顺序.

我们同样可以通过树状图理解下列的命题: 在图中, 每个结点都表示一个 sort() 方法通过 merge() 方法归并而成的子数组, 这棵树恰好有 $n$ 层. 对于 $0$ 到 $n-1$ 之间的任意 $k$, 自顶向下的第 $k$ 层有 $2^k$ 个子数组, 每个数组的长度为 $2^{n-k}$, 归并最多需要 $2^{n-k}$ 次比较, 故每层的比较次数为 $2^k \cdot 2^{n-k} = 2^n$, $n$ 层总共为 $n \cdot 2^n = N\cdot \lg(N) ~~~ \small{(n = \lg(N)})$.

20210913204532

命题 2.4

对于长度为 $N$ 的任意数组, 自顶向下的归并排序需要 $\frac{1}{2}N\cdot \lg(N)$ 到 $N\cdot \lg(N)$ 次比较.

证明

记 $C(N)$ 表示将一个长度为 $N$ 的数组排序时所需要的比较次数. 立刻可知: $C(0) = C(1) = 0$.
对于 $N>0$, 通过递归的 sort() 方法可以由相应的归纳关系得到比较次数的上限:
\[C(N) \leqslant C(\lfloor\frac{N}{2}\rfloor) + C(\lceil\frac{N}{2}\rceil) + N.\]
其中, 不等号右侧分别为将数组左半部分和右半部分排序所用的比较次数, 以及归并所用的比较次数. 由于归并所需要的比较次数最少为 $\lfloor\frac{N}{2}\rfloor$, 故比较次数的下限是:
\[C(N) \geqslant C(\lfloor\frac{N}{2}\rfloor) + C(\lceil\frac{N}{2}\rceil) + \lfloor\frac{N}{2}\rfloor.\]
当 $N$ 为 $2$ 的幂且等号成立时我们能得到一个解: 由于 $\lfloor\frac{N}{2}\rfloor = \lceil\frac{N}{2}\rceil = 2^{n-1}$, 可得:
\[C(2^n) = 2\cdot C(2^{n-1}) + 2^n\]
即
\[\frac{C(2^n)}{2^n} = \frac{C(2^{n-1})}{2^{n-1}} + 1\]
故知
\[\frac{C(2^{n-1})}{2^{n-1}} = \frac{C(2^{n-2})}{2^{n-2}} + 1\]
因此有
\[\frac{C(2^n)}{2^n} = (\frac{C(2^{n-2})}{2^{n-2}} + 1) +1\]
重复该替换过程可得:
\[\frac{C(2^n)}{2^n} = (\frac{C(2^{0})}{2^{0}}+(n-1)) + 1\]
也就是
\[\frac{C(2^n)}{2^n} = \frac{C(2^{0})}{2^{0}}+n\]
去分母得
\[C(N) = C(2^n) = n \cdot 2^n = N\cdot \lg(N).\]

对于一般的 $N$, 对其比较次数的上下界不等式使用放缩的技巧同样不难证明前述结论成立. $\blacksquare$

命题 2.5

对于长度为 $N$ 的任意数组, 自顶向下的归并排序最多需要访问数组 $6N\cdot \lg(N)$ 次.

证明

由于在每一次归并中最多需要访问数组 $6N$ 次: $2N$ 次用于复制, $2N$ 次用于将排好序的元素移动回去, 另外最多比较 $2N$ 次, 结合上一命题立刻可得, 本命题成立. $\blacksquare$

上述的两个命题告诉我们, 归并排序所需要的时间和 $N\cdot \lg(N)$ 成正比, 远远快于我们在上一节中讨论的初级排序算法. 它表明, 我们只需要 比遍历整个数组多个对数因子的时间 就能将整个庞大的数组排序, 这使得使用归并排序处理大小为百万级别甚至更大规模的数组在事实上可行. 相应的, 归并排序的主要缺点则是 辅助数组所使用的额外空间和数组的大小成正比. 不过, 通过一些细致的思考我们还可以进一步地缩短归并排序的运行时间.

优化: 对小规模子数组使用插入排序

对不同的方法处理小规模问题能改善 大多数递归数组 的性能, 因为递归会使 小规模问题中方法的调用过于频繁, 因此改进对它们的处理方式就能改善整个算法. 在排序问题上, 基于上一节的讨论, 我们已经知道插入排序或选择排序非常简单, 因此它们很可能在小规模数组上比归并排序更快. 使用插入排序处理小规模的子数组 (如长度小于 $15$), 一般就可以将归并排序的运行时间缩短 $10 \sim 15 \%.$

优化: 测试数组是否已经有序

针对子数组有序的情况, 我们可以添加判别条件检测 $a[\text{mid}]$ 是否小于等于 $a[\text{mid+1}]$. 如果确实如此的话, 我们就可以直接将其拼接起来而跳过 merge 方法. 这样的优化不影响排序的递归调用, 但对于 任意有序的子数组, 算法的运行时间就变成线性的了.

优化: 不将元素复制到辅助数组

我们还可以节省将数组元素复制到用于归并的辅助数组所消耗的时间. 我们需要两种排序方法实现这一优化: 一种是将数据从输入数组排序到辅助数组, 另一种则是将数据从辅助数组排序到输入数组, 而在递归调用的每一层对输入数组和辅助数组的角色进行对换.

自底向上的归并排序

递归实现的归并排序是算法中 分治算法 的典型应用. 实现归并排序的另一种方法是先归并那些小规模的子数组, 然后再成对归并得到的更大的子数组:

public class MergeBU {
    private static Comparable[] aux;    // auxiliary array used for sorting

    // merge() is identical to Merge class
    
    public static void sort(Comparable[] a) {
        int N = a.length;
        aux = new Comparable[N];
        for (int sz=1; sz<N; sz = 2 * sz) {
            for (int lo=0; lo<N-sz; lo+= 2 * sz) {
                merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
            }
        }
    }
}

自底向上的归并排序会 多次遍历整个数组, 根据子数组大小进行 两两合并. 子数组的大小 sz 初始值为 $1$, 每次循环加倍一次. 最后一个子数组的大小只有在数组大小为 sz 的偶数倍时才会与其相等, 否则它会比 sz 小.

命题 2.6

对于长度为 $N$ 的任意数组, 自底向上的归并排序需要 $\frac{1}{2}N\cdot \lg(N)$ 到 $N\cdot \lg(N)$ 次比较, 并最多访问数组 $6N\cdot \lg(N)$ 次.

证明

处理一个数组的遍数恰好为 $\lfloor \lg(N) \rfloor$, 而每一遍会访问数组 $6N$ 次, 比较次数介于 $\frac{N}{2}$ 和 $N$.

注意, 当数组长度为 $2$ 的幂时, 自顶向下和自底向上的归并排序所用的比较次数和数组访问次数 恰好相同, 只是顺序刚好相反. 在其他情况下, 二者的比较和访问数组的次序均有不同.

自底向上的归并排序适合 用链表组织的数据. 这种方法只需要重新组织链表链接即可将链表 原地排序.

排序算法的复杂度

归并排序是证明 计算复杂性领域 的一个重要结论的基础, 而计算复杂性有助于我们理解排序自身 固有的难易程度. 我们下面就对排序算法的计算复杂性进行详细讨论.

为了研究复杂度, 首先需要建立 计算模型. 对排序而言, 我们研究的对象是 基于比较的算法, 它们对数组元素的操作是由 对主键的比较 所决定的. 一个基于比较的算法在两次比较之间可能会进行任意规模的计算, 但它只能通过 主键的比较 得到关于某个主键的信息. 注意: 由于我们局限于实现了 Comparable 接口的对象, 本章中讨论的所有算法都属于这一类; 此外, 我们还 忽略了访问数组的开销.

命题 2.7

没有任何基于比较的算法能够保证使用少于 $\lg(N!) ~ \sim ~ N \cdot \lg(N)$ 次比较以将长度为 $N$ 的数组排序.

证明

我们首先假设没有重复的主键, 这是任何排序算法都能处理的情况. 我们下面使用二叉树来表示算法对某个数组进行排序后可能的所有情况. 二叉树中的结点要么是一片 表示排序完成并且展示元素排序顺序的叶子, 要么是一个 表示两个元素之间的一次比较操作的内部结点. 从 根结点 到 叶子结点 的每一条路径都对应着算法在建立叶子结点所示顺序时进行的所有比较, 如下图:

从比较树得到的第一个重要结论是: 这棵树至少有 $N!$ 个叶子结点. 如果叶子结点的数量少于这个值, 那么一定 有一些排列顺序被遗漏了.

从根结点到叶子结点的一条路径上的内部结点 的数量就是某种输入下算法进行比较的次数. 我们所关心的是这种路径的长度几何, 也就是树的高度是什么, 因为这就是算法比较次数的最坏情况. 我们在这里介绍二叉树的一个基本的组合学性质: 高度为 $h$ 的树最多只可能有 $2^h$ 个叶子结点, 我们称拥有 $2^k$ 个结点的树为 完美平衡 的, 或称为 完全树.

结合上述的分析可知, 任意基于比较的排序算法都必然和一棵高为 $h$ 的比较树所对应, 因此有:
\[N! \leqslant \text{叶子结点的数量} \leqslant 2^h\]
其中 $h$ 的值就是 最坏情况下的比较次数, 因此对不等式两边同取对数可得任意算法比较次数的下界为 $\lg(N!)$. 由 Stirling 公式: $\lg(N!) \sim N\cdot \lg(N). \blacksquare$

本结论揭示了 设计排序算法时所能达到的理论最佳效果. 命题 2.6 表明归并排序在最坏情况下的比较次数约为 $N \cdot \lg(N)$, 这也是 其他排序算法复杂度的上限. 同时, 命题 2.7 告诉我们, 不存在只需要少于 $N \cdot \lg(N)$ 次比较就可完成数组排序的算法, 因此这也是 其他排序算法复杂度的下限, 即使最好的算法, 在最坏的情况下仍然至少需要这么多次比较. 因此我们有:

命题 2.8

归并排序是一种 渐进最优 的, 基于 比较排序 的算法.

归并排序的最优性远远不意味着对排序算法研究的结束. 实际上, 本节中为了讨论而进行的一些假设具备明显的局限性. 比如:

归并排序的 空间复杂度 不是最优的.
在实践中我们不一定会遇到最坏情况.
除了比较, 算法的其他操作 (如对数组的访问) 也可能同样重要.
不进行比较 也可以将某些数据排序.

因此, 我们下面继续研究其他的一些排序算法.

2.3 快速排序

快速排序可能是应用最为广泛的排序算法. 其流行的原因是 实现简单, 适用于各种不同的数据 且在一般应用中 比其他排序算法快很多.

快速排序是一种 原地排序 (它只需要很小的一个辅助栈), 且将长度为 $N$ 的数组排序所耗时间和 $N \cdot \lg(N)$ 成正比. 这两个优点在我们已经学习的排序算法中只有快速排序同时具备. 此外, 快速排序的内循环 比大多数排序算法都要短小, 这意味着它 无论是在理论上还是在实际中都要更快. 而其主要缺点是它非常脆弱, 许多错误都能导致其实际性能的劣化, 因此在实现时要非常小心.

基本算法

快速排序也是一种分治的排序算法, 它将一个数组 分为两个子数组, 并将两部分独立地排序.

和上一节中介绍的 归并排序 相比, 它有以下几个主要的不同:

归并排序将数组分为两个子数组分别排序, 并将有序的子数组归并以将整个数组排序; 而快速排序则是当两个子数组都有序时, 整个数组也就自然有序了.
在归并中, 递归调用发生在 处理整个数组之前, 而在快速排序中, 发生在 处理整个数组之后.
在归并排序中, 一个数组被分为两段, 而在快速排序中, 切分的位置取决于数组的内容.

快速排序的实现过程如下列代码所示:

public class Quick {
    // constructor
    public static void sort(Comparable[] a) {
        StdRandom.shuffle(a);
        sort(a, 0, a.length-1);
    }
    
    // the real sort method
    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int j = partition(a, lo, hi);   // split a[] into two parts
        sort(a, lo, j-1);   // sort left side: a[lo...j-1]
        sort(a, j+1, hi);   // sort left side: a[j+1...hi]
    }

    // core: partitioning
    // we will come back to implement it...very soon
}

快速排序递归地将子数组 a[lo...hi] 排序: 先用 partition() 方法将 a[j] 放到一个合适的位置, 然后用递归调用将其他位置的元素排序. 该方法的关键在于切分, 该过程使得数组满足下列的三个条件:

对于某个 j, a[j] 已经排定.
a[lo] 到 a[j-1] 中的所有元素都不大于 a[j].
a[j+1] 到 a[hi] 中的所有元素都不小于 a[j].

由于切分过程 总是能排定一个元素, 故用归纳法不难证明 递归能正确地将数组排序: 若左子数组和右子数组都是有序的, 则由左子数组 (有序, 且没有任何大于切分元素的键), 切分元素和右子数组 (有序, 且没有任何小于切分元素的键) 组成的结果数组也 一定有序. 上述代码实现了一个基于这个思路的递归程序. 因为它在将数组排序之前 会将其随机打乱, 因此它是一个 随机化的 算法.

要完成这个实现, 需要完成 切分方法: 我们一般的策略是 随意地 取 a[lo] 作为 切分元素, 也就是那个将会被排定的元素.

随后, 从数组 左端开始向右 扫描, 直到找到一个 大于等于 a[lo] 的元素, 再从数组 从右向左 扫描, 直到找到一个 小于等于它 的元素. 显然, 此时找到的这一对元素 尚未排定, 因此我们需要 交换他们的位置. 如此继续, 就可以确保 左指针 $i$ 的右侧元素都不大于切分元素 a[lo], 且 右指针 $j$ 的左侧元素都不小于切分元素 a[lo]. 在两个指针相遇时, 只需要 交换左子数组最右侧的元素 a[j] 和切分元素交换并 返回 j 即可. 快速排序切分的实现如下:

private static int partition(Comparable[] a, int lo, int hi) {
    int i=lo;   // left scanning ptr
    int j=hi+1; // right scanning ptr
    Comparable v = a[lo];   // partition element

    while (true) {
        while (less(a[++i], v)) {
            if (i == hi) {
                break;
            }
        }
        while (less(v, a[--j])) {
            if (j == lo) {
                break;
            }
        }
        if (i >= j) {
            break;
        }
        exch(a, i, j);
    }
    exch(a, lo, j);     // put v=a[j] into the right place
    return j;           // then we have a[lo...j-1] <= a[j] <= a[j+1...hi]
}

在上述的这段代码中, 我们 按照 a[lo] 的值 进行切分, 当指针 i, j 相遇时 主循环退出. 在循环中, a[i] $<$ v 时我们减小 j, 然后交换 a[i], a[j] 来确保 i 左侧的元素都 不大于 v, j 右侧的元素都不小于 v. 当指针相遇时交换 a[lo] 和 a[j], 切分结束.

在实现快速排序时, 我们必须注意以下几点:

请使用原地切分. 若使用辅助数组实现切分, 将切分后的数组复制回去的开销可能会明显降低排序的速度.
注意扫描指针的越界问题. 如果切分元素恰好是整个数组中最小或最大的, 此时就要在 partition() 方法中进行明确的检测以避免数组越界的情况出现.
确保数组元素经过一次乱序排列, 以保持随机性.
确保排序的切分循环的结束条件是有效的.
注意处理切分元素值有重复的情况. 左侧/右侧扫描最好是在遇到 大于等于/小于等于 切分元素值的元素时停下. 在典型应用中, 它能够避免算法的运行时间变为 平方级别.

快速排序切分方法的内循环会 用一个递增的索引 将数组元素和 一个定值 比较. 归并排序和希尔排序一般都比快速排序慢, 一个原因就是 它们还会在内循环中移动数据.

快速排序的另外一个速度优势在于 它的比较次数很少. 排序效率最终依赖于 切分数组的效果, 而这一效果又依赖于 切分元素的值. 切分的效果是将一个较大的随机数组分成两个随机子数组, 而实际上对于 元素不重复的数组而言, 这样的分割可能发生在 数组的任意位置.

性能特点

下面我们对快速排序算法进行简单分析, 讨论一下它和理想方法之间的差距:

在理想情况下, 快速排序每次 恰好将数组对半分割, 这种情况下的比较次数正好满足分支递归公式:

\[C_N = 2 \cdot C_{\frac{N}{2}} + N\]

其中 $2 \cdot C_{\frac{N}{2}}$ 表示 将两个子数组排序的成本, $N$ 表示用 切分元素 和 所有数组元素 进行比较的成本. 由 命题 2.4 可知, 该递归公式的解是 $N \cdot \lg(N)$. 虽然实际上我们不可能每次切分都恰好是理想情况, 但 平均而言 切分元素都能落在数组中间. 下面我们来对快速排序的性能表现进行证明:

命题 2.9

快速排序 将长度为 $N$ 的 无重复数组 排序平均需要 $\sim 2N \cdot \ln(N)$ 次比较.

证明

记 $C_N$ 为 将 $N$ 个不同元素排序平均所需的比较次数. 显然, $C_0 = C_1 = 1$. 对于 $N > 1$, 由递归程序可得如下的归纳关系:
\[C_N = N+1 + \frac{(C_0 + C_1 + \cdots + C_{N-2} + C_{N-1})}{N} + \frac{(C_{N-1}+C_{N-2}+\cdots+C_0)}{N}\]
第一项是 切分的成本, 总共为 $(N+1)$. 第二项是将长可能为 $0$ 到 $N-1$ 的左子数组 排序的平均成本, 而第三项则是将右子数组 排序的平均成本. 去分母后可得:
\[N \cdot C_N = N(N+1) + (C_0 + C_1 + \cdots + C_{N-2} + C_{N-1}) + (C_{N-1}+C_{N-2}+\cdots+C_0)\]
将该等式减去其 $N-1$ 时的相同等式 可得:
\[N\cdot C_N - (N-1)C_{N-1} = 2N + 2\cdot C_{N-1}\]
整理等式并将两边同除 $N(N+1)$ 可得:
\[\frac{C_N}{N+1} = \frac{C_{N-1}}{N} + \frac{2}{N+1}\]
由归纳推导得:
\[C_N \sim 2(N+1)(\frac{1}{3} + \frac{1}{4} + \cdots + \frac{1}{N+1})\]
近似于
\[C_N \sim \int_{1}^{N}\frac{2}{x}dx + 1 \sim 2N \ln(N).\]
注意到 $2N \ln(N) \approx 1.39 \lg(N)$. 也就是说, 平均比较次数只比最好情况多了 $39\%$.

快速排序的实现还有一个 潜在的缺点: 在切分不平衡时程序可能会极其低效. 这也是我们需要在执行快速排序前将数组 随机排序 的主要原因.

命题 2.10

快速排序最多需要 $\frac{N^2}{2}$ 次比较, 但随机打乱数组能预防这种情况.

算法改进

切换到插入排序: 对于小数组, 快速排序慢于插入排序. 我们可以在排序小数组时切换到插入排序提升算法的性能.
三取样切分: 我们可以使用 子数组的一小部分元素的中位数 来切分数组以得到更好的切分效果, 而将 取样大小设为 $3$ 并用大小居中的元素切分的效果更好.
熵最优的排序: 在实际应用中可能遇到 含有大量重复元素 的数组, 而快速排序会将本不需继续排序的, 元素全部重复的子数组继续切分, 因此可以通过将数组切分为对应 小于, 等于, 大于 切分元素的三个部分避免性能损失.

2.4 优先队列

队列是一种先进先出的数据结构. 元素在队列尾追加, 而从队列头删除. 在优先队列中, 元素被赋予 优先级. 我们将在本节中讨论优先队列的基本表现形式, 然后会学习基于 二叉堆 数据结构的, 一种 优先队列的经典实现, 用数组保存元素并按照优先级排序, 以实现对数级别的高效元素删除/插入操作.

通过插入一列元素并一个个地 删除其中最小的元素, 我们也可以用优先队列实现排序算法, 一种名为 堆排序 的重要排序算法也来自 基于堆的优先队列的实现. 在后续的章节中我们还会学习如何使用优先队列构造其他算法.

API的设计与实现

作为一种 抽象数据类型, 我们同样需要定义一组 API 为该数据解雇的用例提供足够的信息. 优先队列最重要的操作是 删除最大元素 和 插入元素. 我们称删除最大元素和插入元素的方法分别名为 delMax() 和 insert(). 按照惯例, 我们使用辅助函数 less() 对它们进行比较. 和排序算法相同, 若允许重复元素, 最大所表示的是 这些相同的最大元素之一.

`public class`	`MaxPQ<Key extends Comparable<Key>>`
	`MaxPQ()`	创建一个优先队列
	`MaxPQ(int max)`	创建一个最大容量为 `max` 的优先队列
	`MaxPQ(Key[] a)`	用 `a[]` 中的元素创建一个优先队列
`void`	`Insert(Key v)`	向优先队列中插入一个元素
`Key`	`max()`	返回最大元素
`Key`	`delMax()`	删除并返回最大元素
`boolean`	`isEmpty()`	检查队列是否为空
`int`	`size()`	返回队列中的元素个数

初级实现

我们在 第一章 中讨论过的四种基础数据结构是实现优先队列的起点. 我们可以使用 有序或无序的数组或链表 实现它:

数组实现 (无序)

public class MaxPQwArray {
    private String[] pq;
    private int N;

    public MaxPQ() {
        pq = new String[];
    }

    public MaxPQ(int max) {
        pq = new String[max];
    }

    public MaxPQ(Key[] a) {
        pq = a;
    }

    public void Insert(Key v) {
        pq[N++] = item;
    }

    public Key max() {
       for (int i=0; i<N; i++) {
            if (pq[i] >= pq[N]) {
                tmp = pq[N];
                pq[N] = pq[i];
                pq[i] = tmp;
            }
        } 
        return pq[N];
    }

    public Key delMax() {
        for (int i=0; i<N; i++) {
            if (pq[i] >= pq[N]) {
                tmp = pq[N];
                pq[N] = pq[i];
                pq[i] = tmp;
            }
        }
        return pq[N--];
    }

    public boolean isEmpty() {
        return N==0;
    }

    public int size() {
        return N;
    }
}

数组实现 (有序)

public class MaxPQwArray {
    private String[] pq;
    private int N;

    public MaxPQ() {
        pq = new String[];
    }

    public MaxPQ(int max) {
        pq = new String[max];
    }

    public MaxPQ(Key[] a) {
        pq = a;
    }

    public void Insert(Key v) {
        v = pq[++N];
        for (int i=N; i>0 && less(pq[i], pq[i-1]); i--) {
            exch(pq, i, i-1);
        }
    }

    public Key max() {
        return pq[N];
    }

    public Key delMax() {
        return pq[N--];
    }

    public boolean isEmpty() {
        return N==0;
    }

    public int size() {
        return N;
    }
}

链表实现

public class MaxPQwLlist {
    private Node pq;
    private int N;

    private class Node {
        Item item;
        Node next;
    }

    public MaxPQ() {
        pq = new Node();
    }

    public MaxPQ(Key[] a) {
        pq = new Node();
        pq.item = a;
    }

    public void Insert(Key v) {
        Node oldpq = pq;
        pq = new Node();
        pq.item = v;
        pq.next = oldpq;
        N++;
    }

    public Key max() {
        double max = Double.NEGATIVE_INFINITY;
        node = pq;
        while (node.next) {
            if (node.item >= max) {
                max = node.item;
            }
            node = node.next;
        }
        return max;
    }

    public Key delMax() {
        double max = Double.NEGATIVE_INFINITY;
        node = pq;
        node_last = pq;
        while (node.next) {
            if (node.next.item >= max) {
                max = node.next.item;
                tmp = node;
                node = node.next;
                node_last = tmp;
            }
        }
        N--;
        node.last.next = node.next;
        node = null;
    }

    public boolean isEmpty() {
        return N==0;
    }

    public int size() {
        return N;
    }
}

堆的定义

数据结构 二叉堆 能很好地实现优先队列的基本操作. 在二叉堆的数组中, 每个元素都要保证 大于等于另外两个特定位置的元素, 相应地这些位置的元素要 至少大于等于 数组中的 另外两个元素. 当我们将 二叉堆 中的所有元素画成一棵 二叉树, 将每个较大元素和两个较小元素用边连接就能直观地看出这种结构.

定义

当一棵二叉树的每个结点都 大于等于 它的 两个子结点 时, 称其为 堆有序.

相应地, 在 堆有序 的二叉树中, 每个结点都 小于等于 其父节点. 从任意结点向上, 我们都能得到一列 非递减 的元素; 从任意结点向下, 都能得到一列 非递增 的元素. 特别地:

命题 2.11

根结点是堆有序的二叉树中的最大结点.

我们下面讨论二叉堆的表示法:

如果使用指针表示 堆有序的二叉树, 则每个元素需要 三个指针 来定位它的上下结点, 父节点和两个子结点各一个.

若使用 完全二叉树, 就可以更为方便地表达. 要画出这样的完全二叉树, 可以先定下跟结点, 然后层层从上到下, 从左到右, 在每个结点的下方连接两个更小的结点直到全部连接完毕. 只要将二叉树的结点按照层级顺序放入数组中, 就可以只用数组而不需要指针就能表示完全二叉树.

定义

二叉堆 是一组能够用 堆有序的完全二叉树 排序的元素, 并在数组中按照层级储存.

我们下面 将二叉堆简称为堆. 在一个堆中, 位置 $k$ 的结点的父节点的位置为 $\lfloor \frac{k}{2} \rfloor$, 因此我们可以通过 计算数组的索引 在树中 上下移动:

要从 a[k] 向上一层, 就可令 $k = \frac{k}{2}$, 要向下一层的话就可令 $k=2k$ 或 $2k+1$.

命题 2.12

大小为 $N$ 的完全二叉树的高度为 $\lfloor \lg(N) \rfloor$.

证明

在 $N=1, 2$ 的情形下, 命题显然成立.
下面考虑 $N > 2$ 的情况. 不妨假设 $N=k$ 时命题成立, 此时有
\[h(k) = \lfloor \lg(k) \rfloor.\]
当 $N = k+1$ 时, 有下列的两种情况:
\[\begin{cases} 1. ~ h(k+1) = h(k)+1 ~~~~~~ \exists r, ~ \text{s.t.} ~ 2^r = k+1. \\ 2. ~ h(k+1) = h(k) ~~~~~~~~~~~~~ \text{else}\end{cases}\]
对于情形 $1$: $h(k)+1 = \lfloor \lg(k)+1 \rfloor$. 由二叉树的组合性质:
\[h(k+1) = r = \lg(k+1) = \lfloor \lg(k+1) \rfloor. ~~(*)\]
对于情形 $2$: 由于此时 $k+1$ 不是 $2$ 的幂, 故 $\exists r_1$, 使得 $2^{r_1} \leqslant k < k+1 < 2^{r_1+1}$. 也就是:
\[r_1 \leqslant \lg(k) < \lg(k+1) < r_1 + 1\]
由此有
\[\lfloor \lg(k) \rfloor = \lfloor \lg(k+1) \rfloor\]
所以同样有
\[h(k+1) = \lfloor \lg(k+1) \rfloor. ~~(**)\]
结合 $(*), (**)$ 可知, 原命题成立. $\blacksquare$

堆的表示如下图所示:

20210921211450

堆的算法

我们用长度 $N+1$ 的数组 pq 表示一个大小为 $N$ 的堆. 此数组的首元素 pq[0] 被闲置, 而堆元素被放在后面的 $N$ 个元素 pq[1], ..., pq[N]中.

定义

我们称打破堆的状态, 随后遍历它并按照要求将堆的状态恢复的过程为 堆的有序化.

在有序化的过程中, 我们可能需要 自下而上 或 自上而下 地恢复堆的状态. 前者可能发生于 某个结点的优先级上升 或 在堆底加入了一个新元素 时, 而后者可能在 某个结点的优先级下降 时.

自下而上的堆有序化 (上浮) 如果堆的有序状态被打破的原因是其某个结点变得 比它的父结点更大, 我们可以通过交换它和它的父节点实现状态的修复. 即使在交换后它仍然比其父节点更大, 通过有限次重复这一过程, 我们仍可以最终完全将堆的状态恢复:
```
1
2
3
4
5
6
 public void swim(int k) {
     while (k>1 && less(k/2, k)) {
         exch(k/2, k);
         k = k/2;
     }
 }
```
swim() 方法中的循环确保当且仅当位置 $k$ 上的结点大于它的父节点时才会打破堆的有序状态, 因此通过让该结点 不再大于 它的父结点, 就可以恢复有序状态.

自上而下的堆有序化 (下沉) 相应地, 如果堆的有序状态因为某个结点变得 比它的两个子结点 (的其中之一) 更小 而因此被打破, 通过将该结点与其子结点中 更大的那一个 交换, (也许同样需要交换多次) 我们最终就可以修复有序状态.

 public void sink(int k) {
     while (2*k <= N) {
         int j = 2*k;
         if (j<N && less(j, j+1)) {
             j++;
         }
         if (!less(k, j)) {
             break;
         }
         exch(k, j);
         k = j;
     }
 }

上述的两种方法是我们高效实现 优先队列API 的基础:

插入元素: 只需要将新元素加到数组末尾,增加堆的大小并将这个新元素 上浮到合适的位置 即可.
删除最大元素: 从数组顶端删去最大元素, 并将 数组的最后一个元素放到顶端, 减小堆的大小并 让这个元素下沉到合适的位置.

20210921233643

下列的算法对优先队列 API 的实现确保了 插入元素和删除最大元素 这两个操作的用时和队列的大小 成对数关系.

public class MaxPQ<Key extends Comparable<Key>> {
    private Key[] pq;
    private int = 0;

    public MaxPQ(int maxN) {
        pq = (Key[]) new Comparable[maxN+1];
    }

    public boolean isEmpty() {
        return N==0;
    }

    public int size() {
        return N;
    }

    public void insert(Key v) {
        pq[++N] = v;
        swim(N);
    }

    public Key delMax() {
        Key max = pq[1];    // fetch the largest element
        exch(1, N--);       // exchange it with the last elem (equals to deleting it)
        pq[N+1] = null;     // eliminate the ptr to the original max, prevent exceeding boundary
        sink(1);            // let this element sink to its proper position, recover the heap's order
        return max;
    }

    // these helpers are defined in the before this code snippet
    private boolean less(int i, int j)
    private void exch(int i, int j)
    private void swim(int k)
    private void sink(int k)
}

命题 2.13

对一个含有 $N$ 个元素的, 基于堆的优先队列, 插入元素操作 只需不超过 $\lg(N)+1$ 次比较, 删除最大元素操作 需要的比较次数不超过 $2\lg(N)$.

证明

两种操作都涉及在根结点和堆底之间的元素移动. 由 命题 2.12 得: 这种元素移动的路径不超过 $\lg(N)$, 结合代码段不难得出命题对 插入元素操作 的描述成立. 由于 删除最大元素 需要两次比较: 一次用于找出更大的那个子结点, 一次用来判断该子结点是否需要上浮, 因此剩下的描述也成立. $\blacksquare$

堆排序

将所有元素插入一个 查找最小元素的优先队列, 并 重复调用删除最小元素 的操作将它们按顺序删去, 这样的操作使用 无序数组 实现的优先队列来实现就相当于进行了 插入排序, 而使用 基于堆 的优先队列实现, 就相当于 堆排序.

堆排序基本上分为两个阶段. 在 堆的构造阶段 中, 我们将原始数组重新组织并安排进一个堆中, 而在 下沉排序 阶段, 则可从堆中按递减顺序取出所有元素并得到排序结果.

构造堆

我们可以简单地 从左到右遍历数组, 用 swim() 确保 扫描指针左侧所有元素都已经是一棵有序的完全数 即可. 这样的方法耗费的时间与 $N \cdot \log(N)$ 成正比.

更高效的方式是 从右到左 用 sink() 函数构造子堆. 我们可以将数组中的每个元素都视为 某个子堆的根结点, 因此 sink() 方法自然对每个元素对应的子堆都适用. 如果一个结点的两个子结点都已经是堆, 则在该结点上调用 sink() 就可以将它们三个变成一个更大的堆. 递归地重复这一过程, 我们就可以建立起堆的秩序.

命题 2.14

用 sink() 操作由 $N$ 个元素构造一个堆只需 少于 $2N$ 次比较 和 少于 $N$ 次交换.

堆排序的算法实现如下:

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, 1, N--);
        sink(a, 1, N);
    }
}

普林斯顿算法4-Ch2 排序

Sorting Algorithms