Chapter-Eleven.md

第十一章 排序

1. 就像其他任何强大的工具一样，我们经常会在不该使用排序的时候使用排序，而在应该使用排序的时候却不使用排序。请解释在计算 n 元浮点数组的最小值、最大值、均值、中值、众数等统计量时，哪些情况会导致过度使用排序，哪些情况会导致不能充分利用排序。

通过排序来查找 n 个浮点数中的最小值或最大值通常属于过度使用。答案 9 告诉我们，不使用排序也可以更快地求出中值；但是在某些系统上，可能使用排序更容易一些。排序对于求众数很有效，但散列的速度可能更快。求均值的算法的运行时间通常正比于 n，但如果先进行一轮排序可能有助于提高数值精度，见习题 14.4.b。

2. [R.Sedgewick]把 x[l] 用作哨兵以加速 Lomuto 的划分方案。说明如何利用该方法来移除循环后面的 swap。

使循环下标 i 从高到低变化，逐渐靠近 x[l] 中的已知值 t。

Bob Sedgewick 发现，可以使用下面的不变式，将 Lomuto 的划分方案修改为从右向左进行。

t

?

<t

≥t

从而划分代码可写为： ``` m = u + 1 for (i = u; i >= l; i--) if x[i] >= t swap(--m, i) ``` 由于循环终止时 x[m]=t，所以可以直接使用参数 (l,m-1) 和 (m+1,u) 进行递归，不再需要 swap 操作。Sedgewick 还用 x[l] 作为哨兵省去了内循环中的一次测试： ``` m = i = u + 1 do while x[--i] < t ; swap(--m, i) while i != l ```

3. 在特定的系统上如何求出最佳的 cutoff 值？

为了确定 cutoff 的最佳值，我将 n 固定为 1 000 000，然后对 cutoff 在 [1,100] 上的每个可能取值都运行了一遍程序，结果如下图所示。（图略）

不难看出，50 是一个比较理想的取值。cutoff 在 30~70 取值时，运行时间与取 50 的情况相比只相差几个百分点。

4. 虽然快速排序平均只需要 O(log n) 的栈空间，但是在最坏情况下需要线性空间，请解释原因。修改程序，使得最坏情况下仅使用对数空间。

当你有两个子问题需要解决时，哪个问题应该立即解决，哪个问题应该留在栈上等以后解决——大一些的子问题还是小一些的子问题？

5. [M.D.Mcllroy]说明如何用 Lomuto 的划分方案来排序可变长的位字符串，要求排序时间与位字符串的长度之和成正比。

McIlroy 的程序运行时间正比于待排序的数据量，这在最坏情况下是最好的。该程序假定 x[0..n-1] 中的每一项都包含一个整数 length 和一个指向数组 bit[0..length-1]的指针。

void bsort(l, u, depth)
    if l >= u
        return
    for i = [l, u]
        if x[i].length < depth
            swap(i, l++)
    m = l
    for i = [l, u]
        if x[i].bit[depth] == 0
            swap(i, m++)
    bsort(l, m-1, depth+1)
    bsort(m, u, depth+1)

一开始用 bsort(0, n-1, 1) 调用该函数。注意，程序中为参数和定义 for 循环的变量赋值了。线性运行时间很大程度上得益于 swap 操作移动的是指向位字符串的指针，而不是位字符串本身。

6. 使用本章的方法实现其他排序算法。选择排序首先将最小的值放在 x[0] 中，然后将剩下的最小值放在 x[1] 中，依此类推。希尔排序（或“递减增量排序”）类似于插入排序，但它将元素向后移动 h 个位置而不是 1 个位置。h 的值开始很大，然后慢慢减小。

选择排序的实现代码如下：

void selsort()
    for i = (0, n-1)
        for j = (i, n)
            if x[j] < x[i]
                swap(i, j)

希尔排序的实现代码如下：

void shellsort()
    for (h = 1; h < n; h = 3*h+1)
        ;
    loop
        h /= 3
        if (h < 1)
            break
        for i = (h, n)
            for (j = i; j >= h; j -= h)
                if (x[j-h] < x[j])
                    break
                swap(j-h, j)

7. 本章排序程序的实现在本书网站上可以下载。统计在你的系统上运行各个排序函数所需的时间，然后将统计值制成类似于 11.3 节的表。

8. 起草一份一页纸的指南，告诉用户如何在你的系统中选择排序算法。确保你的方法考虑到了运行时间、空间、程序员时间（开发和维护所需的时间）、通用性（如果我想排序代表罗马数字的字符串会怎样？）、稳定性（具有相同关键字的项在排序前后的相对顺序不变）及输入数据的特殊性质等。用第 1 章描述的排序问题对你的方法进行极端测试。

9. 编写程序，在 O(n) 时间内从数组 x[0..n-1] 中找出第 k 个最小的元素。算法可以对 x 中的元素进行排序。

修改快速排序，使其仅在包含 k 的子范围内进行递归。

下面的选择算法来自 C.A.R.Hoare，代码由 qsort4 稍作修改而得。

void select1(l, u, k)
        pre l <= k <= u
        post x[l..k-1] <= x[k] <= x[k+1..u]
    if l >= u
        return
    swap(l, randint(l, u))
    t = x[l]; i = l; j = u+1
    loop
        do i++; while i <= u && x[i] < t
        do j--; while x[j] > t
        if i > j
            break
        temp = x[i]; x[i] = x[j]; x[j] = temp
    swap(l, j)
    if j < k
        select1(j+1, u, k)
    else if j > k
        select1(l, j-1, k)

由于递归是函数的最后一个操作，因此可以将其转换成一个 while 循环。在 The Art of Computer Pragramming Volume 3：Sorting and Searching 一书的习题 5.2.2-32 中，Knuth 证明该程序平均需要 3.4n 次比较来求出 n 个元素的中值；证明方法本质上类似于答案 2.A 中的最坏情况证明。

10. 收集并显示有关快速排序程序运行时间的经验数据。

11. 编写一个“宽支点”划分函数，使得结果如下图所示：

<t

=t

>t

**

如何将这个函数应用到快速排序中？

**

12. 研究非计算机应用（如邮件收发室和零钱分类器）中的排序方法。

13. 本章介绍的快速排序程序随机选择一个划分元素。研究更好的选择，如数组样本的中间值。

14. 本章的快速排序使用两个整数下标表示子数组。在 Java 等语言中必须这样做，因为它们没有指向数组的指针。在 C 或 C++ 中，可以为初始调用和所有的递归调用使用类似下面的函数来排序整数数组：void qsort(int x[], int n) 修改本章中的算法，使它们都使用这一接口。

这一版本的快速排序需要用到指向数组的指针。由于只使用 x 和 n 两个参数，只要读者能够理解 x+y+1 表示的是从位置 x[j+1] 开始的数组，它甚至可以比 qsort1 还简单。

void qsort5(int x[], int n) {
    int i, j;
    if (n <= 1)
        return;
    for (i = 1; j = 0; i < n; i++)
        if (x[i] < x[0])
            swap(++j, i, x);
    swap(0, j, x);
    qsort5(x, j);
    qsort5(x+j+1, n-j-1);
}

由于该函数用到了指向数组的指针，因此它可以用 C 或 C++ 实现，但不能用 Java 实现。我们还必须将数组名（即指向数组的指针）传递给 swap 函数。