『算法导论』第 7 章:快速排序

主要内容

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

快速排序的描述

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

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
randomized_partition(int A[], int p, int r)
{
int i = rand() % (r - p + 1) + r; // 生成从p到r的随机数
Exch(A, r, i); // 将被选的主元交换到数组末尾
return partion(A, p, r);
}

快速排序分析

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

习题解答

练习题

7.1-1 解答:略。

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-1 解答:略。

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-2-6 解答:星号题,略。

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

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

7-4-1 解答:待完成。

7-4-2 解答:待完成。

7-4-3 解答:待完成。

7-4-4 解答:待完成。

7-4-5 解答:待完成。

7-4-6 解答:待完成。

思考题

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); // 排序大于等于主元的部分
}
}