算法导论第 7 章：快速排序

发表于 分类于 Waline： 本文字数： 1.7k 阅读时长 ≈ 6 分钟

主要内容

快速排序通常是实际排序应用中最好的选择。它在最坏情况下的时间复杂度很差，但是平均性能非常好。另外，它能够进行原址排序。

快速排序的描述

与归并排序一样，快速排序也用到了分治思想。其主过程的代码如下：

1
2
3
4
5
6
7
8
void quicksort(int A[], int p, int r)
{
    if (p < r) {
        int q = partition(A, p, r);
        quicksort(A, p, q-1);
        quicksort(A, q+1, r);
    }
}

算法的关键是数组划分过程PARTITION，它实现了对子数组\(A[p..r]\)的原址重排。选择\(x=A[r]\)作为主元，围绕它来划分数组\(A[p..r]\)。完成划分后，\(A[p..q-1]\)的每一个元素都小于等于\(A[q]\)，而\(A[q]\)也小于等于\(A[q+1..r]\)中的每个元素。程序最后返回主元的新小标。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void Exch(int *arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

int partition(int A[], int p, int r)
{
    int x = A[r];
    int i = p - 1;
    for (int j = p; j < r; j++) {
        if (A[j] <= x) {
            ++i;
            Exch(A, i, j);
        }
    }
    Exch(A, i+1, r);
    
    return (i + 1);
}

PARTITION在子数组\(A[p..r]\)上的复杂度为\(\Theta(n)\)，其中\(n=r-p+1\)。

快速排序的性能

当划分产生的两个子问题分别包含了\(n-1\)个元素和\(0\)个元素时，快速排序的最坏情况就发生了。假设算法的每一次递归调用中都出现了这种不平衡划分，可以得到如下的递归式：

\[ T(n) = T(n-1) + T(0) + \Theta(n) = T(n-1) + \Theta(n) \]

可以得到时间复杂度为\(T(n) = \Theta(n^2)\)，也就是说，最坏情况下，快速排序的运行时间并不比插入排序好。当输入数组已经完全有序时，快速排序的时间复杂度为\(\Theta(n^2)\)，而这种情况下插入排序的时间复杂度为\(O(n)\)。

在可能的最平衡的划分中，PARTITION得到的两个子问题的规模都不大于\(n/2\)，这便是快速排序的最好情况。运行时间的递归式为：

\[ T(n) = 2T(n/2) + \Theta(n) \]

上述递归式的解为\(T(n) = \Theta(n \lg n)\)，通过在每一层递归中都平衡划分子数组，我们得到了渐近时间上更快的算法。

实际上，只要划分是常数比例的，算法的运行时间总是\(O(n \lg n)\)，即使是\(99:1\)的划分，其时间复杂度仍然是\(O(n \lg n)\)。当对一个随机输入的数组进行快速排序时，平均情况下，划分同时混合有「好」和「差」的划分。当好和差的划分交替出现时，快速排序的复杂度和全是好的划分时一样，仍然是\(O(n \lg n)\)，区别只在于隐含的常数因子要略大一些。

快速排序的随机化版本

前面的讨论基于一个前提：输入数据的所有排列都是等概率的。实际工程中并不总是这样的，所以我们可以通过在算法中引入随机性，从而使得算法对于所有的输入都能获得较好的期望性能。

可以从子数组\(A[p..r]\)中随机选择一个元素作为主元，这通过将\(A[r]\)与从\(A[p..r]\)中随机选出的一个元素交换来实现。由于主元元素是随机选取的，在平均情况下，对数组的划分是比较均衡的。随机化版本的划分函数实现代码如下：

1
2
3
4
5
6
int randomized_partition(int A[], int p, int r)
{
    int i = rand() % (r - p + 1) + p;  // 生成从p到r的随机数
    Exch(A, r, i);                     // 将被选的主元交换到数组末尾
    return partition(A, p, r);
}

快速排序分析

本节用严格的数学推导计算了快速排序算法的运行时间。在输入元素互异的情况下，随机化版本的期望运行时间为\(O(n \lg n)\)。

习题解答

练习题

7.1-2 解答：返回的\(q\)值等于\(r\)。可以加一个条件判断，如果\(A[\lfloor (p+r)/2 \rfloor]\)等于\(A[r]\)，则返回\(q = \lfloor (p+r)/2 \rfloor\)。

7.1-3 解答：简单的证明就是，该操作只需要遍历一趟子数组。

7.1-4 解答：将PARTITION第四行小于等于号改成大于等于号即可。

7-2-2 解答：当所有元素都相同时，PARTITION返回值为\(r\)，会造成不平衡的划分，所以QUICKSORT的时间复杂度为\(\Theta(n^2)\)。

7-2-3 解答：当所有元素不同，而且按照降序排列时，PARTITION会返回\(1\)，造成不平衡的划分，所以时间复杂度为\(\Theta(n^2)\)。

7-2-4 解答：严格的证明太辛苦了，算了。因为它是几乎有序的输入序列，非递归的插入排序算法的性能会优于递归的快速排序算法。

7-2-5 解答：当\(0 < \alpha \le 1/2\)时，\(\alpha \ge 1-\alpha\)。如果某个分支正好每次都碰到较小的划分，则叶节点的深度最小，根据等式\(n \alpha^x = 1\)求得深度\(x = \log_{\alpha} 1/n = - \lg n / \lg \alpha\)；如果某个分支正好每次都碰到较大的划分，则叶节点的深度最大，类似地有\(n (1-\alpha)^x = 1\)，可以求得此时的深度为\(- \lg n / \lg (1-\alpha)\)。

7-3-1 解答：因为有随机性，统计意义上的平均时间才有意义。

7-3-2 解答：最坏情况下随机数生成器RANDOM被调用了\(\Theta(n)\)次；最好情况下随机数生成器RANDOM被调用了\(\Theta(\lg n)\)次。

思考题

7-1 （Hoare划分的正确性） 根据题干中PARTITION过程的伪代码，我给出如下的代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int hoare_partition(int A[], int p, int r)
{
    int x = A[p];
    int i = p - 1;
    int j = r + 1;
    for (;;) {
        do {
            --j;
        } while (A[j] > x);
        do {
            ++i;
        } while (A[i] < x);
        if (i < j) {
            Exch(A, i, j);
        } else {
            return j;
        }
    }
}

习题解答如下： a）略。 b）因为两端的下表\(i\)和\(j\)分别递增和递减向中间靠拢，而且一旦有\(i \ge j\)，函数即返回，所以不会访问到数组外的元素。 c）因为只有\(i \ge j\)函数才会返回，所以返回值\(j\)不可能等于\(r\)，有可能等于\(p\)。 d）当\(A[i]>x\)且\(A[j]<x\)时，会交换两个元素的位置，所以满足题目中的条件。 e）要将主程序稍微修改一下：

1
2
3
4
5
6
7
8
void quicksort(int A[], int p, int r)
{
    if (p < r) {
        int q = hoare_partition(A, p, r);  // 调用hoare_partition
        quicksort(A, p, q);                // 排序小于主元的部分，此行有修改
        quicksort(A, q+1, r);              // 排序大于等于主元的部分
    }
}