排序是本课程许多结构暗中依赖的问题:二分查找需要有序数据,而堆和平衡树在某种意义上就是为了避免重复排序。前面关于链表归并排序的单元,展示了如何通过重新链接节点来合并与分割。本单元改为处理数组,并回答三个问题:归并排序和快速排序为何正确、代价是多少,以及只靠比较关键字的算法能否在渐近意义上优于 ?
定义
定义 18.2.1
(比较排序、稳定排序与原地排序)
比较排序接收序列 ,只能通过询问所选位置是否满足 来获得关键字信息,并输出按关键字非递减排列的一个置换。若关键字相等的记录保持输入时的相对次序,排序就是稳定的;若除数组外只用 个额外存储单元,就是原地排序(对快速排序的递归栈,我们放宽为 )。除非另有说明,下文的代价 指长度为 的所有输入中,关键字比较次数的最坏情形。
数组上的归并排序
归并排序先递归排序 的两半,再借助临时数组把两半合并。
def merge_sort(a, lo, hi):
if hi - lo <= 1:
return
mid = (lo + hi) // 2
merge_sort(a, lo, mid)
merge_sort(a, mid, hi)
left, right = a[lo:mid], a[mid:hi]
i = j = 0
for k in range(lo, hi):
if j == len(right) or (i < len(left) and left[i] <= right[j]):
a[k] = left[i]; i += 1
else:
a[k] = right[j]; j += 1
定理 18.2.2
(数组归并排序的正确性与代价)
对长度 的区段,merge_sort(a, lo, hi) 使该区段按非递减次序排好,元素不变,且关键字相等的记录保持输入次序。当 时,最坏情形的比较次数满足 、,因此 。
证明
(对长度归纳,以及合并的不变量)
正确性。对长度 归纳。长度不超过 1 的区段已有序。较长的区段中,两半都严格更短,由归纳假设,两次递归调用后它们已有序。合并循环的不变量是:写入位置 之前,位置 按序存放两半中最小的 个元素,而 left[i:] 与 right[j:] 中每个剩余元素都不小于它们。由于两个剩余后缀各自有序,取两个首元素中较小者即可保持该不变量。关键字相等时取左边的首元素,使排序稳定,因为左边的记录在输入中先于右边的记录。每个元素都恰好被写入一次,所以区段保持原有的元素。
代价。合并 个元素至多作 次比较,因为每次比较写入一个元素,而最后一个元素无需比较就写入。因此当 时,最坏情形满足
逐层展开:第 层有 次大小为 的合并,每层少于 次比较,共有 层。故 ;对一般的 ,两半的大小为 与 ,同一上界在相差一个常数因子下仍成立。临时数组需要 个额外存储单元。
证明透视
合并不变量在哪里用到有序与相等规则
归纳假设在合并中恰好用到一次:它说明 left 与 right 各自已有序,所以各自剩余的首元素就是该半中最小的剩余元素。两个首元素中较小者因此是全部剩余元素中最小的,这就是为什么写入它能保持“每个剩余元素都不小于已写入的元素”。已写入的前段保持有序,是因为每个被写入的元素都不大于仍然剩余的所有元素,特别是下一个被写入的元素。
相等规则不影响有序性,只影响稳定性:当 left[i] == right[j] 时取左边的首元素,使输入中较早的左边记录排在右边记录之前。循环在 时结束:所有元素均已写入,没有剩余后缀,不变量说明整个区段就是全部元素的有序排列。
快速排序
快速排序选一个枢轴,重排区段使较小的关键字在枢轴之前、较大的关键字在其后,再对两侧递归。
定义 18.2.3
(a[lo..hi] 的 Lomuto 划分)
取枢轴 ,并维护下标 ,初始为 。对 :若 ,就把 加 1,并交换 与 。最后交换 与 ,并返回 。
循环不变量(在每个 值之前): 只含不大于 的关键字, 只含大于 的关键字,且 。结束时枢轴位于位置 ,其左侧各关键字不大于 ,右侧各关键字大于 ,所以它已在最终位置。
quicksort(a, lo, hi) 先作划分,再对 与 递归,其中 是返回的下标。终止性:两次调用的区段都严格短于原区段,因为枢轴被排除。正确性由归纳得出:划分后枢轴已在最终位置,而两侧由归纳假设排好序,且恰好含有应属于该处的关键字。对 个元素划分恰好作 次比较。
定理 18.2.4
(快速排序的代价)
(a) 若枢轴总是所在区段的最小或最大关键字,快速排序作 次比较。(b) 若每个区段的枢轴均匀随机选取,且关键字互不相同,则期望比较次数至多为 。
证明
(最坏情形的递推式,平均情形的指示概率)
(a) 的递推式是 ,其和为 。以最后一个元素为枢轴时,已有序的数组恰好触发这种行为。
(b) 把各关键字按排序后的次序记为 。两个关键字至多被比较一次,因为比较必定涉及当前枢轴,而枢轴随后被放到最终位置,不再参与。对 , 与 被比较,当且仅当 中最先被选为枢轴的是 或 :若先选中某个 的 ,它会永远把两者分到不同侧。由对称性,这 个关键字被最先选中的机会均等,故概率为 。由期望的线性性,
其中用到 。
概念视角结构
快速排序的枢轴构成一棵搜索树
把每个选出的枢轴当作一个节点,其左、右子节点分别是两个递归调用所选的枢轴。较小的关键字放左边,较大的放右边,所以这是关键字上的一棵二叉搜索树。每次比较都是把一个枢轴与其区段内的关键字配对,也就是与它的后代配对,而每一对祖先与后代恰好比较一次。因此比较次数等于所有节点深度之和(根的深度为 )。对已排序输入、以最后一个关键字作枢轴时,这棵树是四个节点的链,深度之和为 ,与下面的例题一致。
除递归栈外,快速排序是原地的;若总是先对较小一侧递归、对较大一侧用循环,栈深为 。它不是稳定排序。
下界
定理 18.2.5
(比较排序下界)
任何对 个互不相同关键字的所有输入都正确排序的比较排序,在某个输入上至少作 次比较。此外 ,因此最坏情形的比较次数为 。
证明
(数决策树的叶子)
固定一个确定性算法与长度 。每次执行是一串比较,下一次比较只取决于先前的答案。这给出一棵二叉树:内部节点是比较,边是两种答案,每个叶子是最终输出的置换。 个互不相同关键字的不同输入次序必须到达不同的叶子,因为一个叶子规定了唯一的重排方式,而两种不同次序需要不同的重排才能排好序。输入次序共有 种,所以至少有 个叶子。高度为 的二叉树至多有 个叶子,故 ,即 。树的高度就是最坏情形的比较次数。
渐近形式:,该乘积有 个因子,每个至少为 ,所以当 时 。
证明透视
叶子计数依赖的假设
这个论证只有一步关键:它不分析某个特定算法的行为,而是计算任何正确算法必须能产生多少种不同的结果。三个假设各在一处使用。确定性使下一次比较成为先前答案的函数,执行因而成为二叉树中的一条路径。对每个输入都正确,迫使每个叶子指定唯一的重排,所以两种不同次序不能共用一个叶子。关键字互不相同才使 种次序需要 种不同的重排:若所有关键字相等,任何重排都已是有序序列,所以这个计数对这类输入没有任何说明。
证明的结尾,是把叶子数 夹在两个界之间:。之后把乘积折半,只是把 换成明确的形式 。
因此,归并排序在比较排序中渐近最优,而快速排序在期望意义上与之相当。该下界不适用于以其他方式检查关键字的算法,例如按数位计数的排序。
例题
例题 18.2.6
(八个关键字的归并排序)
排序 。两半 与 先递归排序。前半中, 以 1 次比较变成 , 以 1 次比较保持不变;合并 与 时比较 、、,得 (3 次比较)。后半中, 与 各 1 次比较;合并时比较 、、,得 (3 次比较)。
最后合并 与 :比较 (取 1)、(相等,取左边的 2)、(取右边的 2)、(取 3)、(取 4)、(取 5)、(取 6)。此时右半已空,7 不经比较直接接上。输出为 ,共 次比较。总计 。
例题 18.2.7
(一次 Lomuto 划分与小规模下界)
以枢轴 及 划分 。 时 ,(与自身交换)。 时 ,不变。 时 ,,交换位置 1 与 2:。 时 ,,交换位置 2 与 3:。 时 ,交换位置 3 与 4:。 时 ,交换位置 4 与 5:。 时 ,不变。最后交换位置 与 7:。枢轴在下标 5,左部 内部尚未排序(右部 恰好已有序),共用了 次比较。
当 时,下界给出 ,因为 。归并排序处理四个关键字至多用 次比较,所以最坏情形下没有比较排序能做得更好。
例题 18.2.8
(已有序输入上的快速排序,直至空区段)
取 ,以最后一个元素为枢轴。枢轴为 4 时, 的关键字都不大于 4,所以 每次都前进,每次交换都是与自身交换;最后一次交换也是与自身。划分在 3 次比较后返回 。左侧调用处理 ;右侧调用处理 ,这是空区段,不作任何比较就立即返回。
在 上取枢轴 3 要 2 次比较,右侧同样为空;在 上取枢轴 2 要 1 次;单个关键字 要 0 次。总数为 ,与 (a) 的预测相符。每次划分都只剥掉枢轴本身,所以递归深度为 ,而每个右侧调用都是空的。
细节与常见错误
反例模式
快速排序不稳定
以最后一个元素为枢轴,按关键字排序 。两个 2 都大于枢轴 1,循环从不交换,最后一步交换位置 0 与 2,得 。两个相等的关键字次序被颠倒了。归并排序对同一输入返回 。
常见错误
(把期望界当成对所有输入取平均)
界 是对算法自身随机枢轴选择取的期望,对每个固定输入都成立。它不是对随机输入取的平均:固定的枢轴规则总有坏输入,例如以最后一个元素为枢轴时的已有序输入,5 个关键字要作 10 次比较。
常见错误
(把下界当成对每个输入的界)
说的是长度为 的输入中的最坏情形。它并不禁止某个特定算法对个别输入(例如已有序的输入)更快,也不适用于以比较以外方式检查关键字的算法。
常见错误
(在合并中使用严格比较)
若合并改用 left[i] < right[j] 而不是 left[i] <= right[j],关键字相等时会先取右边。左边为 、右边为 时,输出是 ,稳定排序就不再稳定。有序性与比较次数都没有改变,所以这个疏忽很容易被漏过。
习题与解答
快速检查
(1. 以枢轴 5 对 [4,9,1,7,3,8,5] 作 Lomuto 划分。求最终数组、枢轴下标与比较次数。)
解答 · 解答 1
时 ,。 时 9 不动。 时 ,,交换位置 1 与 2:。 时 7 不动。 时 ,,交换位置 2 与 4:。 时 8 不动。最后交换位置 3 与 6,得 。枢轴下标为 3,共 6 次比较。
快速检查
(2. 以最后一个元素为枢轴的快速排序,对已有序数组 [1,2,3,4,5] 作多少次比较?)
解答 · 解答 2
每次划分后所有元素都留在枢轴左侧,因此各区段的大小依次为 5、4、3、2、1。划分共作 次比较,等于 。
快速检查
(3. 对 6 个互不相同的关键字,比较排序必须能在某个输入上使用的比较次数,最少是多少?)
解答 · 解答 3
是 。由于 ,在某个输入上至少需要 10 次比较。
快速检查
(4. 用归纳法证明:由 与 ,当 为 2 的幂时 。)
解答 · 解答 4
当 时,公式给出 。设公式对 成立,则 。由于 ,有 ,与上式相同。所以公式对 成立。
快速检查
(5. 解释为何决策树论证需要 个叶子,而不只是每次比较有两种结果。)
解答 · 解答 5
种输入次序各自需要不同的重排才能排好序,所以两种不同次序不能终止于同一个叶子。具有 个叶子的二叉树,高度至少为 ,而 迫使高度至少为 ,即 。