插入排序与选择排序的最坏情形需要二次时间。有两个经典算法可在不使用大小为 的额外数组时达到 :快速排序(quicksort)围绕枢轴作划分;堆排序(heapsort)把数组变成二叉堆,再反复取出最大值。在“选择与线性时间排序”单元讨论的归并排序同样是 且稳定,但需要第二个数组。本单元证明快速排序与堆排序的正确性,推导其代价,并比较三者。它使用堆单元中的数组表示,以及复杂度单元的代价术语。
快速排序
快速排序排序 的方法是:选一个枢轴,重排区段使不大于枢轴的关键字在其前、较大的关键字在其后,再对两侧递归。
定义 3.4.1
(围绕枢轴的划分)
以枢轴 对 作划分,是重排该区段并返回一个下标 (),使 , 的每个元素都不大于 , 的每个元素都大于 。此时位置 的元素已在最终排序位置上。
int partition(int a[], int lo, int hi) {
int p = a[hi];
int i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] <= p) {
i++;
int t = a[i]; a[i] = a[j]; a[j] = t;
}
int t = a[i + 1]; a[i + 1] = a[hi]; a[hi] = t;
return i + 1;
}
void quicksort(int a[], int lo, int hi) {
if (lo < hi) {
int q = partition(a, lo, hi);
quicksort(a, lo, q - 1);
quicksort(a, q + 1, hi);
}
}
划分不变量。在下标 的每次迭代开始时: 的每个元素都不大于 , 的每个元素都大于 ,且 。起初两个区域皆为空。若 ,把 加 1 并交换 与 ,就把 放到第一个区域末端,而被挤出的较大元素移到第二个区域末端;若 ,第二个区域只是扩大。循环结束后,最后一次交换把 放到下标 ,其左侧只有不大于它的关键字,右侧只有较大的关键字。划分恰好作 次比较。
快速排序的正确性。对区段长度作强归纳。长度为 0 或 1 的区段无需处理。否则枢轴已在最终位置,两个递归区段都严格更短,由归纳假设它们已有序,且恰好含有应位于各侧的关键字。所以整个区段已有序。
定理 3.4.2
(快速排序的代价)
(a) 若每个枢轴都是所在区段的最小值或最大值,则对 个关键字的快速排序作 次比较。(b) 若每个区段被分成大小为 与 的两部分,则比较次数满足的递推式解为 。(c) 若每个区段的枢轴均匀随机选取且关键字互不相同,则期望比较次数至多为 。
证明
(递推式与逐对计数的论证)
(a) 的递推式为 ,,其和为 。以最后一个元素为枢轴时,已有序的输入(或反向有序、或全部关键字相等的输入,因为测试是 )正好产生这种行为。(b) 的 有 层,每层少于 次比较。(c) 把各关键字按排序后的次序记为 。两个关键字至多比较一次,因为比较涉及当前枢轴,而枢轴随后不再参与工作。对 , 与 被比较,当且仅当 中最先被选为枢轴的是 或 :若先选中某个 的 ,两者从此被分开。这 个关键字被最先选中的机会均等,故概率为 ,由期望的线性性,
证明透视
为什么逐对计数就能得到期望值
关键的一步是改为按关键字的配对来计算比较次数,而不是沿着递归树追踪。有两件事使每一对的计数有明确意义:一对关键字至多被比较一次,因为比较涉及当前枢轴,而枢轴随后不再参与运算,所以比较总次数就是每对一个指示变量之和;另外,两个关键字会一直留在同一区段,直到某个枢轴落在它们之间的闭区间内,因此 被比较,当且仅当从 中最先被选为枢轴的是两端之一。这里用到关键字互不相同:若有相等的关键字,就不存在排序 ,而且测试 把枢轴的所有副本放到同一侧,概率 就不再正确。随机性只用了一次,就是使这 个关键字中每一个成为最先枢轴的机会均等。证明以期望的线性性收尾,它不要求不同的配对相互独立,再配合调和级数的界 。若枢轴不随机,(a) 部分表明固定的规则总有输入使和大到 。
除递归深度外,快速排序是原地的;在情形 (a) 中递归深度可达 ,若先对较小一侧递归、对较大一侧用循环,深度就以 为界。它不稳定。
概念视角结构
递归树就是二叉搜索树
把每个选出枢轴的调用记作一个节点,两个递归调用分别是它的左、右子树。关键字互不相同时,这棵树是关键字上的二叉搜索树,因为一次调用的枢轴介于它两侧各关键字之间。划分时,区段内其余每个关键字都与枢轴比较一次,所以每个关键字恰好与它的每个真祖先各比较一次,比较总次数就是所有节点的深度之和(根的深度为 )。以三个关键字为例,枢轴为 时深度为 ,总和为 ;枢轴为 时树是一条链,深度为 ,总和为 。最好情形是平衡树,情形 (a) 的最坏情形则是一条链。均匀随机的枢轴使这棵树成为随机二叉搜索树,情形 (c) 界定的正是它的期望总深度。
堆排序
堆排序使用存储在从零开始的数组中的最大堆:下标 的子节点为 与 ,每个关键字都不小于其子节点的关键字。(堆单元的最小堆用同样方法会得到递减次序。)
void sift_down(int a[], int i, int size) {
for (;;) {
int big = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < size && a[l] > a[big]) big = l;
if (r < size && a[r] > a[big]) big = r;
if (big == i) return;
int t = a[i]; a[i] = a[big]; a[big] = t;
i = big;
}
}
void heapsort(int a[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
sift_down(a, i, n);
for (int end = n - 1; end > 0; end--) {
int t = a[0]; a[0] = a[end]; a[end] = t;
sift_down(a, 0, end);
}
}
sift_down(a, i, size) 假设 之下的两棵子树在 内都已是最大堆,并通过在较大子节点超过该关键字时与其交换,来修复 处的堆性质;每次交换使该关键字下降一层,所以至多 次交换。
正确性。第一个循环处理下标 到 0。下标 及以上都是叶子,自然是堆;处理下标 时,其子节点的子树已是堆,所以 sift_down 使以 为根的子树成为堆。循环结束后 是最大堆。第二个循环的不变量:在下标为 end 的迭代之前, 是最大堆,而 按序存放最大的 个元素。最大值在 ;把它换到位置 end 就扩展了有序的后缀,而 sift_down 修复较短前缀上的堆,因为只有根改变了。
代价。第一个循环由自底向上建堆的论证,代价为 (大部分节点靠近叶子,下沉的层数很少)。第二个循环执行 次,每次下沉至多 层。总计最坏情形 ,原地,额外空间 。它不稳定。
| 算法 | 最坏情形比较次数 | 额外空间 | 稳定 |
|---|---|---|---|
| 快速排序 | ;随机枢轴的期望为 | 栈(先递归较小一侧) | 否 |
| 堆排序 | 否 | ||
| 归并排序(数组) | 是 |
例题
例题 3.4.3
(对 [8, 3, 7, 1, 5, 2] 作快速排序)
以枢轴 2(最后一个元素)、 划分整个数组。元素 8、3、7 都大于 2。 时 ,所以 ,交换位置 0 与 3:。 时 5 较大。放置枢轴:交换位置 与 5:,枢轴下标为 1(5 次比较)。左部 无需处理。右部位置 2 至 5,,枢轴 3:7、8、5 都大于 3,所以 保持为 1;交换位置 2 与 5 得 ,枢轴下标为 2(3 次比较)。再处理位置 3 至 5,,枢轴 7:8 大于 7; 时 ,,交换位置 3 与 4:;最后交换位置 4 与 5,得 ,枢轴下标为 4(2 次比较)。余下的区段 与 无需处理。数组在 次比较后排好序。
例题 3.4.4
(对 [4, 10, 3, 5, 1] 作堆排序)
建堆:,从 开始。下标 1 的关键字 10 有子节点 5 与 1,不需移动。 时,关键字 4 有子节点 10 与 3;与 10 交换:,然后下标 1 的 4 有子节点 5 与 1;与 5 交换:。这是最大堆。
排序阶段。交换位置 0 与 4:;在大小为 4 的堆中下沉 1:较大的子节点是 5,交换;然后在下标 1,下标 3 的子节点为 4,交换:。交换位置 0 与 3:;在大小为 3 的堆中下沉:较大的子节点是 4,交换:。交换位置 0 与 2:;在大小为 2 的堆中下沉:子节点 1 较小,不动。交换位置 0 与 1:。结果为 。
例题 3.4.5
(三个互异关键字的期望比较次数)
取 ,关键字为 ,顶层枢轴随机均匀选取。若枢轴是 (概率 ),划分作 次比较,两侧都是空的,所以代价为 。若枢轴是 或 (概率 ),划分作 次比较,剩下两个关键字,还要再作一次比较,所以代价为 。期望值为 。
用逐对公式得到同一个值: 与 的 ,各以概率 被比较; 的 ,概率为 。总和为 。界 成立。边界情形 :没有配对,和为空,代价为 ,与递归的预期一致。
细节与常见错误
常见错误
(某些输入族使枢轴规则失效)
以最后一个元素为枢轴并使用测试 <= 的快速排序,在有序数组上退化为 ,在 个关键字全部相等的数组上也一样:每个元素都进入左侧区域,枢轴落在最后一个下标。随机枢轴可防止坏输入;它并不排除运气不好的可能,只是令其概率很小。三数取中或三路划分较能处理大量相等的关键字。
常见错误
(堆排序不稳定)
排序 :建堆时比较 与 ,因不是严格更大而不交换;第一次取出时交换位置 0 与 1,得 。相等的关键字次序被颠倒。
反例模式
建堆必须从最后一个内部节点向上进行
断言:既然 sift_down 在一个下标上修复堆性质,那么依 递增次序调用它,同样能建成堆。这是错的,因为 sift_down(a, i, size) 要求 之下的两棵子树都已是堆。取 ,,下标为 与 。在 时,以下标 为根的子树是 带子节点 ,并不是堆,前置条件不成立。调用比较子节点 与 ,把 与 交换,得 ;接着 把 与其子节点 交换,得 。根 小于其子节点 ,所以这不是最大堆,排序阶段就会取出错误的最大值。正确次序下,先 得 ,再 把 先与 交换、再与 交换,得堆 。修正办法就是建堆阶段的向下循环,它保证每次调用前子节点的子树已是堆。
习题与解答
快速检查
(1. 以枢轴 5(最后一个元素)对 [6,2,9,4,7,1,5] 作划分。求结果数组、枢轴下标与比较次数。)
解答 · 解答 1
:。:,,交换位置 0 与 1:。:。:,,交换位置 1 与 3:。:。:,,交换位置 2 与 5:。最后交换位置 3 与 6:。枢轴下标为 3,共 6 次比较。
快速检查
(2. 此快速排序对四个相等的关键字 [7,7,7,7] 作多少次比较?)
解答 · 解答 2
每个元素都满足 ,所以 每次都前进,枢轴落在最后一个下标。各区段的大小为 4、3、2、1,所以比较次数为 ,即 时的最坏情形 。
快速检查
(3. 以堆排序的建堆循环,由 [2,9,7,6,5,8] 建立最大堆,并给出数组。)
解答 · 解答 3
,从 开始。关键字 7 只有下标 5 的子节点(关键字 8):交换,得 。:关键字 9 的子节点为 6 与 5,不变。:关键字 2 的子节点为 9 与 8;与 9 交换:;在下标 1,关键字 2 的子节点为 6 与 5;与 6 交换:。下标 3 没有子节点。堆为 。
快速检查
(4. 对堆 [9,6,8,2,5,7] 执行排序阶段的第一步取出,并给出之后的数组与堆大小。)
解答 · 解答 4
交换位置 0 与 5:。堆现在占据下标 0 至 4。下沉 7:子节点为 6 与 8,较大者是 8,所以交换:。下标 2 的子节点在下标 5 与 6,超出大小为 5 的堆,于是停止。数组为 ,堆大小为 5。
快速检查
(5. 为何堆排序的建堆阶段虽然调用约 次下沉,代价却只有 ?)
解答 · 解答 5
在高度为 的节点处调用,至多作 次交换。 个节点的堆中,高度为 的节点至多有 个,所以总代价至多为 ,因为 。因此建堆阶段需要 ,而不是 。