快速排序是一种基于比较的排序算法:它选择一个称为基准值的值,以此为界划分序列,再对划分得到的各部分排序,从而使整个序列有序。该算法由托尼·霍尔于 1959 年提出,并于 20 世纪 60 年代初发表,后来成为分治法最具影响力的范例之一。它在实践中颇具吸引力,因为它既只需较少的辅助存储空间,又能高效地访问连续存储的数据。
对于 个元素,在对输入顺序或基准值随机化作出适当假设的情况下,普通快速排序的期望运行时间为 ,但最坏情况下的运行时间为 。这些界描述的是一族算法,而非某个固定程序:基准值的选择、划分方式、相等键的处理以及递归管理,都会显著影响算法的表现。实际生产环境中的实现通常将快速排序与其他排序方法结合,以改善小规模输入下的性能,或保证最坏情况下的时间界。
快速排序既是一种重要的实用技术,也是计算机科学中的重要研究对象。对它的分析展示了概率推理的运用,它的实现揭示了正确性方面的微妙问题,而它的各种变体则说明,数学上的操作次数如何与内存访问、分支预测及并行执行相互影响。
起源、原理与排序模型
1959 年,霍尔在莫斯科从事机器翻译工作时设计了快速排序。当时的问题是如何组织单词以便查词典,但由此产生的方法具有通用性。1961 年,他以《算法 64:快速排序》为题发表了简短介绍,随后于 1962 年发表了更详尽的论文《快速排序》。快速排序的发展恰逢人们对递归编程的兴趣日益浓厚:简洁的递归描述就能表达一种在执行过程中涉及多次相互依赖的划分的算法。
快速排序的核心操作是划分。给定序列中的一个片段,算法选择一个枢轴,并重新排列元素,将应排在枢轴之前的值与应排在其后的值分开。有些划分方案会直接将某个枢轴元素放到排序后的最终位置;另一些方案则仅在两组元素之间确定一条分界。这些方案提供的保证不同,递归调用必须与所用方案实际提供的保证相匹配。
如果划分产生了两个正确分隔的组,那么分别对两组排序,就能使整个片段有序。与归并排序不同,快速排序通常不需要归并阶段。它主要在递归调用之前重新排列元素,而不是在调用之后。例如,以 为枢轴对互不相同的值 进行划分,可能得到 。再将枢轴两侧各含两个元素的组分别排好序,即可完成排序,无须再让元素跨越枢轴移动。
快速排序通常用于可修改的数组,其中每个元素都可在常数时间内访问。元素不一定是数字:记录可以按姓名、时间戳、由多个字段组成的元组,或应用程序提供的比较函数来排序。数学模型通常假定比较结果前后一致,且每次比较耗时为常数。这两个假设都并非必然成立。比较长字符串可能需要检查许多字符,而移动大型记录的开销也可能远高于移动整数键值。
因此,描述快速排序时需要区分几种资源。它的时间复杂度衡量计算工作量的增长,通常以比较次数为依据;它的空间复杂度包括递归或显式栈所占的空间;实际运行速度则取决于内存访问量和比较操作的开销。普通的数组划分只使用常数个索引和临时值,但完整的递归算法未必只占用常数空间。称快速排序为“原地”排序,通常是指它能够在不另行分配规模相当的数组的情况下重新排列输入,而不是无条件地断言其辅助内存总量为 。
划分方案与正确性
两种影响深远的划分方法通常分别归于霍尔(Hoare)和尼科·洛穆托(Nico Lomuto)。两者对一个区间所做的工作量都是线性的,但建立的后置条件不同。这些差异会影响比较次数、交换次数、相等键值的处理,以及后续递归调用的区间边界。将一种划分过程替换到按另一种划分方案编写的代码中,是程序出错的常见原因。
洛穆托划分通常选择最后一个元素作为枢轴。扫描下标逐一检查其他元素,同时用一个边界标记已被归为小于枢轴的区域的末端。每当扫描遇到一个较小的元素,就通过交换将其移入较小元素区域。最后,再通过交换将枢轴放到该区域之后的下一个位置。如果枢轴最终的下标为 ,则分别对以 结尾和以 开头的区间进行递归。采用严格的“小于”判断时,等于枢轴的值会留在它的右侧。
相应的循环不变量为:已检查的部分由两个区域组成,前一个区域中的元素小于枢轴,后一个区域中的元素大于或等于枢轴;扫描下标之后的所有元素尚未分类。每次迭代都保持这一性质,最后一次交换则确定枢轴的最终位置。这一方案易于解释和验证,但可能执行大量交换,而且在键值重复时可能产生极不均衡的划分。
霍尔原始风格的划分使用两次从区间两端相向推进的扫描。以下是一种具有代表性的版本,其中上下界均包含在区间内:
partition(A, lo, hi):
pivot = A[lo]
i = lo - 1
j = hi + 1
loop:
repeat:
i = i + 1
until A[i] >= pivot
repeat:
j = j - 1
until A[j] <= pivot
if i >= j:
return j
swap A[i], A[j]
对于至少包含两个元素的区间,快速排序接下来对 A[lo..j] 和 A[j+1..hi] 排序。返回的下标是分隔边界,不一定是所选枢轴元素的最终位置。特别是,不能仅仅因为 j 是划分过程返回的下标,就将它排除在左侧递归调用的区间之外。
正确性包含三个方面:划分必须保持元素的多重集合不变,输出的各组必须满足所要求的大小关系,且递归必须在严格更小的区间上进行,以保证终止。交换操作保持多重集合不变,扫描过程中的不变量保证大小关系成立,正确的边界规则则保证递归不断推进。对相等值的处理尤为重要:在上述版本中,扫描遇到相等值时会停止,但在下一次迭代时又会继续前进,从而避免无休止地交换相等元素。这些需要证明的性质使划分成为形式验证中一个很有价值的案例:即使程序很短,也可能需要格外精确的规格说明。
运行时间分析与概率保证
在标准的常数成本比较模型中,对 个元素进行一次划分需要 时间。如果划分后得到的两个子问题分别包含 个和 个元素,那么,将枢轴放到最终位置的实现满足如下形式的递推关系:
近乎均等的划分会产生 层递归,其中每个主要递归层的划分工作总量为 ,因此运行时间为 。划分不必完全均衡:即使始终按固定比例划分,例如四分之一与四分之三,也仍然能得到这一渐近界。
另一个极端是,每次都选中最小或最大的元素,导致其中一个子问题的规模为 。此时递推关系变为:
由此得到 的运行时间。在每次划分进行 次比较的简单实现中,比较总次数为 。如果始终选择首元素或尾元素作为枢轴,且划分过程反复将这个极值元素单独分离出来,那么已排序的输入就会导致这种情况。有序本身并不一定有害;关键在于输入顺序与枢轴选择策略之间的相互作用。
当所有键值互不相同,且每一步递归都均匀随机地选择枢轴时,标准模型下的期望比较次数为:
其中, 是第 个调和数。因此,
这个精确表达式适用于这样一种模型:在划分过程中,枢轴与其他每个元素各比较一次。具体的扫描实现可能具有不同的低阶开销,或者采用不同的比较次数统计方式。
一种巧妙的推导方法是按排序后的顺序考察各个键。秩分别为 的两个键会进行比较,当且仅当从秩区间 中最先选出的枢轴是该区间的两个端点之一。这一事件的概率为 。对所有键对的这些概率求和,就得到期望比较次数。这个论证利用了期望值的线性性质,不要求各次比较事件相互独立。
必须区分“平均”的两种不同含义。对于确定性的枢轴选择规则,可以在输入排列服从均匀随机分布的假设下进行分析。而对于随机化算法,则可以针对任意固定输入进行分析,并对算法自身的随机选择取期望。后一种分析不要求用户提供随机排列的数据。但这两种解释都不会消除普通快速排序的二次时间最坏情况:期望值并不是每次执行的上界。
枢轴选择、采样与对抗性输入
枢轴选择的目标是在不耗费过多选择时间的前提下,使划分尽可能均衡。选取端点元素成本很低,却容易受到常见数据排列模式的影响。选取数组中间位置的元素,可以避免端点选择在已排序输入上最简单的退化情形,但中间位置的值未必接近中位数。位置和秩是两个不同的属性。
一种广泛使用的启发式方法是三数取中:比较三个采样元素,通常是首元素、中间元素和尾元素,然后将其中的中位数用作枢轴。这样可以避免选中这三个元素中的极端值,也能较好地处理许多有序输入。更大的样本可以进一步改善划分的预期均衡程度。“九数取中”(ninther)这一名称源于约翰·图基的采样术语,其做法是将九个采样值分为三组,每组三个,先分别取中位数,再取这三个中位数的中位数。这类方法可以估计秩居中的值,而不必精确找出当前区间的真正中位数。
采样也有成本。只有当划分更加均衡或元素移动次数减少所带来的收益足以抵消额外比较的开销时,这些比较才值得进行。此外,按某一种成本指标衡量的最佳枢轴,未必也是另一种指标下的最佳选择。对于传统的单枢轴快速排序,接近中位数的枢轴有利于均衡两侧的比较工作量;而对于划分成本不对称或使用多个枢轴的实现,最优采样选择可能有所不同。因此,样本大小和采样方法往往会随区间长度调整。
从数组位置中均匀随机地选择一个位置,可以使每个元素成为枢轴的概率相同。在键值互不相同的情况下,对于任意固定输入,这种方法都能得到标准的期望 时间复杂度结果。另一种常见做法是先将整个数组随机打乱,再执行确定性的快速排序,前提是打乱过程均匀随机,且后续算法满足相关假设。随机化本身也会带来成本,包括生成随机数或额外遍历一次数据。
仅靠确定性采样并不能保证抵御对抗性输入。精心排列的序列可以使三数取中规则反复选出较差的枢轴。1999 年,M. 道格拉斯·麦克罗伊描述了一种“反快速排序”(antiquicksort)技术,能够针对某些快速排序实现,构造出使其比较过程陷入困境的情形。这体现了网络安全中的一个更普遍的问题:受外部影响的排序任务可能成为耗尽资源的手段,不过,能否利用某个具体实现,取决于它的防护措施和输入接口。
通过中位数的中位数选择算法,可以选出具有秩范围保证的枢轴。结合线性时间的划分过程,这种方法可以实现最坏情况下 的排序。然而,它的额外开销往往使其不如混合方案有吸引力:混合方案通常使用选择成本较低的枢轴,只有在排序进展差得可疑时才切换算法。因此,枢轴质量只是稳健性的一个组成部分,不能替代完整的最坏情况应对策略。
相等键值、序关系与稳定性
重复键值既会改变性能问题,也会影响适宜采用的划分策略。假设所有元素的键值都相同。采用严格比较的 Lomuto 划分法每一轮都会将枢轴放在一端,导致二次方级别的运算量。遇到相等元素便停止的 Hoare 式扫描通常会将这类输入划分为大小大致均衡的两组,从而避免上述问题,但仍会在多个递归层级中反复处理相等元素。
三路划分明确地将元素分为小于枢轴、等价于枢轴和大于枢轴的三个区域。只有第一个和第三个区域需要递归排序。中间区域已经处理完毕,因为其中所有元素在排序所依据的序关系下都可以互换。这种方法与艾兹赫尔·戴克斯特拉提出的荷兰国旗问题密切相关;该问题通过移动少量边界来排列三类元素。
一种常见的三路划分过程维护四个区域:左侧是已处理完毕的小于区域,其后紧接着等于区域,中间是尚未检查的区域,右侧是大于区域。遇到较小的元素时,将其交换到左侧;遇到等价元素时,向前推进扫描位置;遇到较大的元素时,将其与未检查区域最右端的元素交换。在最后一种情况下,换入的元素仍需检查,因此扫描索引不能前移。这一细节是保证正确性的关键。
对于所有元素都相等的数组,三路快速排序只需一次线性时间的划分即可完成。更一般地说,它的性能不仅取决于元素数量,还能反映各键值出现频率的分布。若各个不同键值出现的概率为 ,则
衡量了区分这些键值类别所需的信息量。适当的随机化三路划分变体可以达到形如 的期望时间界。即使 ,线性项仍不可省略,因为算法依然必须检查输入。
等价并不一定意味着对象是同一个对象,也不意味着每个字段都相等。在严格弱序下,如果两个对象中的任何一个都不小于另一个,它们就是等价的。例如,按部门对员工排序时,同一部门的员工即使姓名不同,也被视为等价。比较结果不一致、键值发生变化,或对浮点数 NaN 处理不当,都可能破坏划分所依赖的前提。
普通的原地快速排序并不稳定:它可能改变等价记录之间的相对顺序。如果需要在键值相等的各组内部保留先前的顺序,稳定性就很重要。快速排序存在稳定的变体,通常需要额外的存储空间或更复杂的重排操作,但常规的基于交换的实现并不具备稳定性。将原始位置作为键值相同时的次级比较依据,可以得到与稳定排序一致的输出顺序,但这也会使原本等价的键变成不同的比较键,并改变算法的性能特征。
混合实现与存储空间保证
实际应用中的快速排序通常采用混合策略。对于较大的区段,划分很有效;但对于很小的区段,初始化、分支判断和函数调用的开销可能反而占据主要部分。一种常见实现是在区段长度低于固定阈值时停止递归划分,改用插入排序。对于不受限制的输入,插入排序的最坏情况时间复杂度为平方级;但对于大小有界的小区段,其简单的循环和较低的开销可能使它更快。
组合这两种方法主要有两种方式。一种是立即对每个小区段排序;另一种是暂不完成这些小区段的排序,等划分全部停止后,再对整个数组执行一遍插入排序。由于划分边界已经使各区段处于正确的相对顺序,剩余的无序性仅限于各个小区域内部。在截断阈值固定的情况下,收尾工作的时间仍与 成线性关系,只是常数因子取决于该阈值。最佳阈值取决于具体实现,而不是普遍适用的算法常数。
递归管理是另一个需要单独考虑的问题。如果直接对两个分区都进行递归,最坏情况下的调用栈深度会达到 。一种标准的改写方式是只递归排序较小的分区,而用循环处理较大的分区。由于较小分区所含的元素数至多约为当前元素数的一半,无论枢轴选择得好坏,同时处于活动状态的函数调用数都是 。即使运行时间仍为平方级,这也能限制栈空间的使用量。
David Musser 于 1997 年提出的内省排序加入了最坏情况时间保障。它先使用快速排序,同时跟踪划分深度。如果深度超过与 成正比的上限,就改用堆排序对剩余区段进行排序。常用的上限约为 ,不过其中的常数是设计上的选择。对于大小为 的剩余区段,堆排序提供 的时间上界,从而保证整个混合算法的最坏情况时间为 。
内省排序中的深度计数器衡量的是划分过程的深度,而不只是实际的函数调用深度。当较大的分区采用迭代方式处理时,这一区别尤为重要:一条病态的处理链可能只占用很少的栈空间,却仍然执行大量质量很差的划分。正确的实现必须在沿这条链处理时,持续更新逻辑上的剩余深度额度。
进一步的改进包括检测已经有序的区段、识别反复出现的不平衡划分,以及在相等键值占主导时改变策略。这些启发式策略必须结合起来评估:额外的预扫描可以减少近乎有序数据上的工作量,却可能在随机输入上浪费时间。因此,基准测试需要涵盖多种数据分布、记录大小、比较成本和对抗性模式。如果只报告随机打乱的互异整数上的性能,就会遗漏一些重要的行为特征。
内存行为、处理器开销与并行执行
快速排序在实践中的良好声誉,部分得益于它使用内存的方式。划分过程中的扫描会遍历连续的数组区域,有利于硬件预取,也能较为高效地利用 CPU 缓存。随着递归产生的区域越来越小,整个子问题的数据可能都能放入速度更快的缓存层级中。这些优势有助于解释:为什么一种在比较次数的渐近界上并无优势的方法,能在许多内存内处理任务中胜过其他方法。
不过,仅凭比较次数仍不足以预测性能。如果一个分支的两种结果出现的概率相同,处理器就可能难以预测。对随机数据进行划分时,往往恰好会出现这种情况。预测错误可能使推测执行的工作作废,并拖慢中央处理器的执行进度。反过来,即便某种实现执行的基本指令更多,只要它避开了难以预测的分支,运行速度仍可能更快。
基于分块的划分将分类与数据移动分离。它先检查一块元素,记录其中应归入另一侧的元素的偏移量,再利用这些记录下来的偏移量进行交换。这种组织方式可以减少依赖数据的分支。无分支技术或向量化技术也旨在实现类似目标,但其收益取决于可用的指令集、键的类型,以及存储分类信息的开销。对定长整数有效的方法,未必适合需要通过任意用户自定义比较操作来排序的对象。
数据移动同样重要。反复交换大型记录可能占据执行时间的大部分,因此,一种实现方式是先对指针或索引排序,再据此重新排列记录。这样可以减少划分过程中移动的数据量,但也会引入间接内存访问。如何取舍,取决于记录大小、缓存局部性,以及后续使用这些记录的程序是否要求记录在物理存储上重新排列。对连续存放的引用数组进行快速排序,与对相同数量、直接存放在数组中的大型记录进行快速排序,具有不同的硬件性能特征。
划分完成后,得到的两个区段可以独立排序,这为并行计算提供了天然的机会。基于任务的实现可以将这些区段交给不同的线程处理。任务必须足够大,才值得付出调度开销;而划分不均衡则可能使部分工作线程空闲。因此,较小的子问题通常采用顺序方式处理。
顺序执行的划分过程限制了这种简单方法的并行扩展能力。即使划分完全均衡,最长的依赖链上仍包含与 成正比的划分开销,即 。并行划分可以通过并发地对不同数据块进行分类,再利用前缀和或相关操作计算输出位置,从而缓解这一瓶颈。这些技术通常需要额外的存储空间和同步。在图形处理器和分布式系统上,与直接移植递归式原地快速排序相比,基于基数、归并或采样的方法可能具有更合适的通信模式。
相关算法、库接口与应用
快速排序的划分思想也可用于快速选择,这是一种用于查找指定秩元素的算法。划分后,快速选择只在包含该秩元素的区域中继续查找。例如,查找中位数时,无须对已知仅包含较小值的区域进行排序。随机化快速选择的期望运行时间为线性,但其直接实现的变体在最坏情况下仍需二次时间。确定性选择方法则可以保证最坏情况下的线性时间界。
部分排序和重复选择介于选出单个指定秩的元素与对所有元素完全排序之间。围绕第 小的元素进行划分,可以分离出最小的 个元素,而不对它们的内部顺序作出要求。随后只对这一区域排序,即可解决 top- 问题;当 较小时,这比对全部 个元素进行完整排序所需的工作量更少。数据库执行系统和数据分析系统在完整排序、选择以及用堆维护有限结果集这几种方案之间作出选择时,都会利用这种基本区别。
使用多个枢轴的变体会将一个区段划分为更多区域。双枢轴快速排序使用两个已按大小排列的枢轴形成三个区域,再对各区域递归排序。弗拉基米尔·雅罗斯拉夫斯基的双枢轴算法曾受到广泛关注,并被 Java 7 用于基本类型数组的排序。它在实践中的成功表明,减少比较次数并非加快排序的唯一途径:扫描和内存访问的方式也会显著影响性能。多枢轴设计并不总是更优,其价值取决于实现细节和工作负载。
库接口的名称不一定代表其所用的算法。C编程语言中的 qsort 接口规定通过比较回调函数进行排序,但语言标准并未要求其使用快速排序实现。库可以使用归并排序、堆排序或混合算法,同时提供相同的接口。同样,C++ 的 std::sort 规定的是行为和复杂度要求,而非强制采用某种特定的划分过程。内省排序是一种常见的实现策略,并不是该接口的定义。
当数据位于可写的随机访问内存中、不要求稳定性,而且比较操作能够给出所需次序时,快速排序尤其适用。其他需求则可能更适合采用别的算法。归并排序天然支持稳定排序和顺序归并。蒂姆排序能利用数据中已有的有序段。当键具有合适的数位表示时,基数排序方法可以不受比较排序复杂度界限的约束。对于数据量超过内存容量的情况,外部排序通常优先考虑大块的顺序传输,因此多路归并特别有用。
这些选择也解释了为什么数据库管理系统可能会针对不同查询采用不同的排序策略。内存中的一批数据可以用比较排序算法处理,而需要将数据溢写到存储设备的操作则可能先生成有序段,再进行归并。决策的关键并非快速排序是否在所有情况下都是最快的,而是其划分方式、数据移动方式、稳定性和存储特征是否适合数据的表示形式与执行环境。