排序算法是一种按照指定排序规则重新排列一组元素的算法,例如按数值升序、字母顺序,或依次按记录中的若干字段排序。输出必须包含与输入完全相同的元素,但排列顺序须符合指定规则。排序是计算机科学中的一项基础操作,因为有序数据有助于高效地进行查找、分组、重复项检测、合并以及多种分析。
排序方法之间的差异不只体现在速度上。有些方法会保留排序键相同的元素之间的原有顺序;有些需要大量临时存储空间;有些能够利用数据已有的部分有序性;还有些则专为磁盘、分布式计算机或专用处理器而设计。面对数据表示方式、排序规则、内存容量和执行环境的不同组合,没有哪一种方法始终最优。
排序这一课题将数学上的下界与工程实践联系起来。基于比较的排序通常需要 量级的比较次数,而利用整数或字符串排序键的表示方式的算法,则可以具有不同的复杂度界限。实际性能还取决于数据搬移、缓存行为、比较成本、并行性,以及所使用的软件接口提供的保证。
排序规则与排序问题
排序的输入通常是一个记录序列 ,每条记录都关联一个键。键可以是数据项本身,例如整数;也可以是从较大的记录中提取的值,例如员工的姓氏或交易时间戳。排序过程产生一个排列 ,满足
其中, 表示所要求的非递减顺序。排列这一条件至关重要:一个序列即使只包含输入中最小项的多个副本,也符合有序的要求,但它并不是对输入的正确排序结果。
在软件中,排序规则通常通过比较函数或表示“排在前面”的谓词来提供。许多通用排序接口要求采用严格弱序。其严格关系具有非自反性和传递性,而由“两个数据项都不排在对方前面”定义的等价关系也具有传递性。这使得不同记录可以具有相等的排序键,而不必是同一个对象。例如,按对象的内存地址排序,与按这些对象中存储的值排序,是两种不同的排序规则。
稳定排序会保留键比较结果等价的记录在输入中的相对顺序。假设交易记录最初按到达时间排列,随后按客户标识符进行稳定排序,那么每位客户的交易记录仍会保持到达时的先后顺序。稳定性还支持通过多轮排序实现多字段排序:先按次要键排序,再按主要键进行稳定排序,就能得到所需的字典序。另一种方法是让比较器直接比较完整的元组。
有些数据类型需要特殊处理。涉及 NaN 的普通浮点比较并不构成数值全序,因此排序接口可以明确定义 NaN 的排列规则。文本排序同样取决于所采用的规则:按码点数值排序、按特定语言的规则排序、忽略大小写排序,或将连续数字视为数值的“自然”排序。仅凭 Unicode统一码编码,并不能确定符合特定文化习惯的字典顺序。
排序的前提是相关数据项之间能够形成一致的顺序。如果依赖关系仅规定某个任务必须先于另一个任务执行,那么它定义的是有向图上的另一类问题,即拓扑排序。拓扑序不必依据某种比较规则确定每一对数据项的先后关系,只需遵守图中的先后约束。
成本模型与算法性质
标准分析将资源用量表示为元素数量 的函数。时间复杂度描述运行时间如何增长,而空间复杂度衡量内存需求。渐近记号忽略与具体机器有关的常数和低阶项。因此,在假设条件相当的情况下, 方法的运行时间最终会比二次时间方法增长得更慢,但在输入规模较小时,它仍可能更慢。
必须明确统计的是哪种操作。在比较模型中,每次键值比较的成本为一个单位,主要考察的量是比较次数。对于定长整数,这可以是一种有用的近似。对于字符串,一次比较可能需要检查很长的公共前缀。对于键值计算开销较大的记录,比较次数和键值提取次数所对应的开销可能超过其他所有工作的开销。因此,仅凭 并不能完整刻画对 个对象进行排序的成本。
数据搬移是另一项主要成本。某种算法的比较次数可能相对较少,却会反复复制大型记录。对指针或索引而非记录本身进行排序,可以减少数据搬移,不过后续通过这些指针进行访问时,局部性可能较差。交换对象可能调用特定编程语言的移动操作,而操作采用引用计数的对象则可能引入额外的管理开销。因此,同一种抽象算法的两种实现,在执行时间上可能存在显著差异。
最好情况、平均情况、最坏情况和期望界限描述的是不同的性能结论。平均情况分析需要给定输入的概率分布。期望分析则可以针对随机化算法所做的随机选择取平均,即使输入固定不变也是如此。随机化快速排序的期望运行时间可以是 ,但如果随机选择的序列不走运,仍可能出现二次时间的执行过程。最坏情况保证则在既定模型下排除了这种缓慢的执行过程。
原地算法通常被理解为仅使用少量辅助存储空间的算法,但这一术语的定义并不统一。严格的定义只允许使用 个额外机器字;较宽松的定义则可能允许使用 的递归栈空间。稳定性与原地操作是相互独立的性质:两者都不能推出另一者。
最后,存储层次结构会影响简单操作计数所掩盖的成本。顺序扫描能够高效利用缓存行和预取机制,而分散的访问则可能引发开销高昂的内存传输。对于外部存储,数据块的读写可能比比较次数重要得多。在分布式系统中,通信与协调的开销可能超过本地计算。
比较次数的下界及其局限
排序的核心下界可以通过计算可能结果的数量来推导。如果 个元素的键值互不相同,那么输入就有 种可能的排列顺序。确定性的比较算法可以表示为一棵决策树:内部节点对元素进行比较,叶节点则确定最终的排列顺序。对于互不相同的键值,每次比较只有两种有效结果,因此高度为 的树最多有 个叶节点。
要保证算法正确,就必须有足够多的叶节点来区分所有可能的排列顺序。因此,
利用阶乘的渐近性质可得
因此,任何比较排序算法在最坏情况下都需要进行 次比较。如果所有排列出现的概率相同,运用类似的决策树论证,可以得到渐近阶相同的平均情况下界。随机化也无法消除比较排序的这一普遍限制。
这一结论针对的是某种计算模型,并不是说所有排序都至少需要 时间。若一种方法将键值用作数组下标、检查其二进制位,或对其表示形式进行算术运算,就能获取纯比较算法无法获得的信息。计数排序和基数排序利用的正是这一差别。它们的开销取决于其他参数,包括键值范围、字长或位数。
对输入的限制也能减少不确定性。如果已知一个序列除少量扰动外已经有序,就不必再将其视为全部 种任意排列中的一种。能够识别已有顺序的算法可以利用这一点。重复键值也会减少不同键值序列的数量:如果各个键值的出现次数为 ,那么可区分的排列数量为
这些界限能指导算法设计,却不能直接预测实际运行时间。渐近最优的方法可能具有较大的常数因子、高昂的内存访问开销,或较高的初始化成本。反过来,对于很小的子数组,二次时间算法可能更合适。更广泛的计算复杂性领域区分了两类问题:在给定模型下哪些事情不可能做到,以及在特定机器上哪些方法运行得快。
基本的平方时间排序方法
插入排序每次处理一个元素,逐步构建有序前缀。对于接下来的每个元素,它将前面比该元素大的元素向右移动,再将该元素插入腾出的位置。每轮迭代结束后,前缀都保持有序,因此很容易论证算法的正确性。对于键值相等的元素,如果只移动键值严格大于待插入元素的元素,插入排序就是稳定的,而且只需要常数大小的辅助存储空间。
插入排序的性能与输入中的逆序对数量密切相关。逆序对是指满足 、但键值顺序错误的一对位置。标准插入排序对每个逆序对执行一次移动,因此其工作量为 ,其中 为逆序对数量。对于已经有序的序列,排序只需线性时间;而键值互不相同的逆序序列包含 个逆序对,因此需要平方时间。二分查找可以减少定位插入位置所需的比较次数,但无法消除数组中必要的元素移动。
选择排序反复从尚未排序的后缀中找出最小元素,并将其与下一个输出位置上的元素交换。无论初始顺序如何,其常见实现都恰好执行 次键值比较,但只需 次交换。当写入代价特别高时,这种比较开销与移动开销之间的差异可能很有价值。通常基于交换的选择排序并不稳定:将一条记录移到另一条记录的另一侧,可能颠倒键值相等记录的相对顺序。
冒泡排序反复比较相邻元素,并交换顺序错误的元素。每完成一趟遍历,就会将剩余元素中的一个最大元素移到当前处理区间的末尾。如果实现在某一趟没有发生交换时就停止,那么最好情况下只需线性时间,但平均情况和最坏情况仍需平方时间。虽然它的局部操作便于演示,但作为处理小规模输入的方法,通常不如插入排序。
这些算法的意义并不限于入门教学。插入排序被广泛用作更复杂算法的内部步骤,因为对于短数组,紧凑的循环、较低的初始化开销和良好的局部性都能带来优势。类似选择排序的方法则展示了这样一类场景:尽量减少写入比尽量减少比较更重要。相邻交换方法还揭示了一个有用的数学联系,即逆序对数量与恢复有序状态所需的局部调整次数之间的关系。
这些算法的局限性源于其结构,而不只是实现上的缺陷。当一种算法通过大量局部移动来消除无序,或反复扫描剩余输入中的大部分元素时,平方级的工作量对该方法而言可能无法避免。要提高处理大规模输入的能力,通常需要从更全局的角度组织比较与移动。
基于归并的排序
归并排序采用分治法:将输入划分为若干部分,分别排序,再将得到的有序序列合并。在常见的二路归并版本中,输入被划分为大小大致相等的两半。合并两个有序序列时,反复从两个序列当前最前面的元素中选出较小者,因此,合并总共包含 个元素的两个序列需要线性时间。
当两半大小均衡时,递推关系为
由此可得运行时间为 。每一层归并都会处理所有元素,而层数约为 。与基本的插入排序不同,普通归并排序在输入为逆序时,运行时间不会退化为平方级。合并长度分别为 和 的两个非空序列,最多需要 次比较。
稳定性来自一条细微却重要的规则:当两个序列最前面的元素关键字相等时,优先取出原输入中位置靠前的那一段里的元素。始终遵守这一规则,就能在整个排序过程中保持关键字相同的记录之间的相对次序。基于数组的实现通常会分配一个可容纳 个元素的临时缓冲区,以额外内存换取简单的顺序读写。对于链表,则可以通过修改链接来完成归并,无须移动存储的记录,也无须分配与数组等大的缓冲区。
自顶向下的归并排序使用递归来表达划分过程。自底向上的归并排序则从单个元素开始,依次合并长度为 1、2、4 等的有序段。这种方式避免了递归控制流程,在处理链表或由有序段构成的数据流时可能更为方便。自然归并排序会先找出已有的有序段,而不是假定每个元素最初都单独构成一个有序段。
当数据已经分成多个有序组时,归并同样很有用。优先队列可以从 个数据流各自最前面的元素中选出最小者,以 的选择操作开销完成 路归并。这是外部排序以及合并独立排序的各分区的核心步骤。
基于归并的方法具有重要的历史地位:约翰·冯·诺依曼于 1945 年在早期电子计算的背景下描述了归并排序。这类方法至今仍有价值,不仅因为它出现得早,更因为其性能可预测,并且采用顺序访问。虽然稳定的原地归并可以实现,但要同时保证良好的时间复杂度上界和较低的常数开销,其实现要比标准的缓冲区方法复杂得多。
快速排序与分区
快速排序由托尼·霍尔于 1959 年前后提出,并于 1961 年以算法形式发表,其排序过程围绕枢轴展开。分区过程重新排列元素,使一个区域的元素应排在枢轴之前,另一个区域的元素应排在枢轴之后。随后,算法递归地对这些区域排序。分区通常通过原地扫描数组完成,因此快速排序具有良好的局部性,所需的辅助存储空间也较少。
其开销取决于分区是否均衡。如果枢轴每次都将输入划分为大小近乎相等的两部分,递归深度就是对数级的,总工作量为 。如果每次分区只排除一个元素,工作量就会变为
当简单的枢轴选择规则遇到与之对应的输入模式时,就可能出现这种情况,例如在已经有序的数据中选择端点元素作为枢轴。
对于互不相同的键,若以均匀随机方式选择枢轴,标准模型下的期望比较次数为
其中 。其主导项为 。这是对枢轴选择取期望所得的结果,并不是对最坏情况的保证。三数取中等采样技术通常能改善实际的分区均衡性,但固定的采样规则仍可能遇到不利的输入。
对于包含大量重复值的数据,分区的具体实现会显著影响性能。三路分区将键分为小于枢轴、等价于枢轴和大于枢轴的三组。等价区域已经处理完毕,无须再递归处理。当所有键都相等时,合适的三路分区可以在线性时间内完成,而某些两路分区方案则会做多余的工作,或产生严重失衡的分区。
霍尔式分区和洛穆托式分区体现了不同的实现取舍。霍尔最初的分区方式从两端向内扫描,并返回一个分界位置;它不一定会将枢轴放到排序后的最终位置。洛穆托式分区通常会将选定的枢轴放到最终位置,但可能执行更多交换操作。正确的递归范围取决于所用分区过程约定的行为。
普通的原地快速排序并不稳定。不过,它的栈空间消耗仍然可以控制:递归排序较小的分区,并以迭代方式处理较大的分区,即使运行时间退化为二次时间,也能将栈深度限制在 。生产环境中的实现通常会设置深度上限,并在分区持续不理想时切换到其他算法。
堆排序与希尔排序
堆排序使用二叉堆,这是一种以数组紧凑表示的树形有序结构。在最大堆中,每个父节点的值都不小于其子节点的值,因此最大元素位于根节点。采用从零开始的下标时,位置 的子节点位于 和 ,前提是这些位置存在。数组表示法无需为各个节点单独分配内存。
排序过程首先构建一个堆,然后反复将堆根与当前有效区域的最后一个元素交换,并在缩小后的区域内恢复堆性质。每次恢复都沿着一条路径进行,其长度至多为对数级。自底向上建堆的时间复杂度为 ,而不是 ,因为大多数节点都靠近叶节点,只需少量调整。随后反复移除堆顶元素的总耗时为 。
J. W. J. 威廉姆斯于1964年提出堆排序,同年,罗伯特·弗洛伊德给出了一种改进的建堆方法。标准堆排序兼具最坏情况下 的时间复杂度和 的辅助空间需求,是一种很有保障的组合。它通常是不稳定的。它的访问模式是在父节点与子节点的位置之间跳转,而非扫描连续区间,因此在采用缓存的现代计算机上,尽管其复杂度界限很有吸引力,实际速度却可能不及快速排序或基于归并的方法。
希尔排序由唐纳德·希尔于1959年提出,它通过比较相隔一定间距的元素,将插入排序加以推广。对于选定的间距 ,算法对下标间隔为 的各个子序列分别进行插入排序。间距序列逐步递减,最终降至1,此时再执行一轮普通的插入排序,便完成了整个排序过程。前面几轮处理使元素能够长距离移动,而不必逐一跨越中间的每个位置进行移位。
与堆排序不同,希尔排序并不存在一个独立于其参数的统一复杂度界限。其性能在很大程度上取决于间距序列。希尔最初采用的反复减半序列在最坏情况下会产生平方级时间复杂度,而其他序列则具有更好的复杂度界限或实测性能。对实用间距序列的分析,远比算法那段简短的实现所呈现的要复杂。
这两种算法通常都不稳定,且只需很少的辅助内存,但它们解决的是不同的工程问题。堆排序可作为渐近性能可靠的后备方案。希尔排序则提供了一种紧凑、非递归的实现方式,在中等规模的数据上可能具有良好的实际性能;不过,讨论它的理论与实测表现时,都必须同时说明所选用的间距序列。
计数排序、基数排序与桶排序方法
计数排序假定键值属于一个已知的离散范围,通常为 。它先统计每个键值的出现次数,再通过累加确定位置,最后将记录放入各自的输出位置。标准的稳定版本需要 时间和 辅助存储空间。如果只需要键值,则可以直接根据频数数组生成输出,而不必保留键值所附带的记录。
当键值范围相对于输入规模不太大时,计数排序很高效。对一百万条键值为单字节的记录进行排序,与为每个可能的 64 位值分配一个计数器,是截然不同的问题。范围参数是复杂度表述的一部分;不说明这一参数,就简单地称计数排序为“线性”算法,可能会造成误导。
基数排序将键分成称为“位”的若干组成部分进行处理。最低位优先基数排序从最低位开始,每一轮都使用稳定排序。稳定性确保在当前位相同的组内,前几轮建立的顺序得以保留。如果共有 位,每轮使用的基数为 ,即每位有 种可能取值,那么基于计数排序的实现需要 时间。
最高位优先基数排序则先按最高位对记录分组,再递归处理各组。这种方法适合字符串,因为不同组的处理可能在不同深度结束,而分组方式由共同前缀决定。字符串终止符需要有明确的排序约定,例如,使一个前缀排在以该前缀开头的较长字符串之前。某些最高位优先的变体会原地重排记录,但不一定保持稳定性。
桶排序将元素分配到对应不同取值范围的桶中,对每个桶内部进行排序,再将各桶依次拼接起来。在对输入分布和桶的数量作出适当假设时,可以达到期望线性时间。没有这些假设,元素可能集中在一个桶中,使桶内排序问题的规模基本没有缩小。桶排序对数据分布的假设,不同于计数排序对有限键值逐一精确计数的做法。
利用数据表示方式进行排序时,必须准确处理有符号整数、字节序和浮点格式。将原始位模式视为无符号数时,其顺序并不直接对应有符号数的数值顺序;浮点编码则需要经过变换,并为特殊值制定明确的处理规则。提取各位也有内存开销:增大基数可以减少处理轮数,但会扩大计数表,并可能降低缓存性能。这些方法通过改变可用的操作来绕开比较排序的下界,而不是与该下界相矛盾。
自适应排序与混合排序
自适应排序算法会根据输入中已有的结构调整所需的工作量。衡量这些结构的有效指标包括逆序对数量、已有有序段的数量,以及各元素与其最终位置之间的距离。这些指标不能相互替代。一个由两个较长有序块组成的序列,可能包含大量逆序对,却仍可通过一次归并轻松完成排序。
蒂姆排序由蒂姆·彼得斯于 2002 年为 Python 引入,它结合了自然有序段检测、基于插入排序的短有序段处理,以及稳定归并。它会识别单调区段,并可将符合条件的递减区段反转为递增区段。要保持稳定性,就必须谨慎处理关键字相等的情况:如果一个递减段中包含关键字相等的记录,反转该段就可能颠倒这些记录原有的次序,因此有序段的检测规则必须考虑关键字相等的情况。
蒂姆排序式的实现会将短有序段扩展到适用的最小长度,并遵循相应规则,决定归并哪些相邻有序段。归并策略十分重要,因为反复将一个很大的有序段与很小的有序段归并,可能导致过多的数据移动。当下一个输出元素连续多次来自同一个有序段时,“疾驰”模式可以加快归并:先进行指数搜索,再在缩小的范围内搜索,从而定位出一块可以整体复制的元素。不同实现和版本在有序段调度及归并策略的细节上有所不同。
内省排序由戴维·穆瑟于 1997 年提出,采用了另一种混合思路。它从快速排序开始,监测递归深度;如果分区过程导致递归深度过大,就切换到堆排序。常见的阈值与 成正比。由于达到阈值之前的工作只涉及对数数量级的分区层数,而剩余区间均使用堆排序,因此整体最坏情况复杂度界为 。较小的区间通常使用插入排序处理。
混合排序的范围并不限于这些有专名的方法。程序库可能针对基本数值类型采用专门的处理路径,对存在重复关键字的数据采用三路分区,对对象采用稳定归并策略,或对固定位宽的整数采用基数排序方法。它还可能检测出某个区间已经有序,从而提前返回。这些选择并未改变排序的要求,只是满足这些要求的不同方式。
应当区分自适应性与“所有看起来容易处理的输入都能以较低代价处理”这一保证。针对有序段数量自适应的方法,未必对逆序对较少的输入最优;针对近乎有序数据的优化,也可能给随机数据带来额外开销。因此,有意义的描述应明确指出算法利用了哪种结构指标、采用何种后备处理方式,以及最坏情况下的资源消耗界限。
外部排序与存储系统
外部排序处理的是规模过大、无法完全放入工作内存的输入。其主要开销是内存与存储设备之间的数据传输,而不是单次比较。在标准模型中,内存可容纳 个数据项,存储设备以包含 个数据项的块为单位进行传输。高效算法力求让这些传输批量大、顺序进行且次数少。
外部归并排序通常从初始归并段生成开始。程序读入一部分能够装入内存的输入,在内存中完成排序,再将其写出为一个有序归并段。随后,程序将归并段分组进行归并,为每个归并段设置一个输入缓冲区,并另设一个输出缓冲区。一次 路归并需要足够的内存来容纳约 个输入缓冲区,以及输出缓冲区和用于选择下一数据项的数据结构,因此可用内存限制了能够同时归并的路数。
如果最初约有 个归并段,而每一趟归并可同时合并数量级为 的归并段,那么归并趟数随归并段数量呈对数增长。在通常的基于比较的外存模型中,满足该模型的标准参数假设时,排序所需的块传输次数通常为
其中,。这个表达式凸显了为何增加内存或减少完整遍历数据的趟数,可能比为每个数据项减少几次比较更为重要。
置换选择是另一种生成归并段的技术。它维护一个由候选记录组成的优先队列,每次输出能够接续当前归并段的最小记录。若某条记录过小,无法接在当前已输出记录之后,就将其推迟到下一个归并段。在适当的随机输入假设下,归并段的平均长度约为堆容量的两倍,但具有特定结构的输入可能表现得截然不同。
数据库管理系统可能会调用外部排序,以执行显式排序、去重、分组、索引创建或连接处理。当某项操作所需的内存超出分配额度时,系统可以将中间归并段溢写到临时存储中。记录宽度、压缩方式、并发工作负载和临时文件管理都会影响最终开销。
固态存储改变了延迟和带宽特性,但并未消除外存处理中的问题。顺序传输仍然高效,而写入中间数据会消耗带宽,也会损耗存储设备的写入寿命。系统可以让读取、排序和写入重叠执行,使用异步 I/O,或者先对紧凑的记录引用进行排序,再按序收集完整记录。这些技术不仅优化比较过程本身,也同样着力于优化排序算法所涉及的数据传输模式。
并行排序、分布式排序与排序网络
在并行计算中,排序的评价指标包括总工作量、给定处理器数量下的执行时间,以及最长依赖链的长度。仅仅把递归子问题分配给不同的处理器,并不能保证高效的扩展性。划分、合并、分配和通信都可能成为串行瓶颈,而对于小任务,调度开销可能比实际执行的开销还大。
并行归并排序将彼此独立的有序段分配给各个工作单元,再分阶段将其合并。合并操作本身也可以通过寻找分割位置来并行化:从一个输入序列中选取元素,利用二分查找确定它们在另一个输入序列中的位置,从而划定互不重叠的输出区间。并行快速排序同样需要并行划分操作,通常通过统计各类别的元素数量并计算偏移量来实现。起始的高层阶段尤为重要,因为普通递归分支在靠近根节点时能提供的并行性很有限。
排序网络采用固定排列的比较交换操作,不随数据值而改变。Batcher 于 1968 年提出的双调排序网络,对于规模为二的整数次幂的标准情形,需要 个比较器,深度为 。其规整结构适用于电路以及处理固定小规模数据的并行内核。虽然存在渐近深度更小的网络,但其常数因子和构造复杂度可能限制实际应用价值。
在图形处理器上,数据布局、合并访存、同步和寄存器使用情况都会显著影响性能。对于能容纳在局部存储中的小组数据,双调排序网络很方便;而对于大量定长键,基于基数排序的方法往往更有效。抽象操作次数较少的方法,如果导致不规则的内存访问或线程间的执行分歧,实际性能反而可能更差。
在分布式计算中,记录还必须在机器之间传输。采样排序通过样本估计划分点,将记录发送至负责相应连续键值区间的机器,然后在各台机器上对各自区间进行本地排序或合并。如果划分点能使记录均匀分布,各台机器的工作量就会大致相当。键值分布偏斜或大量记录具有相同键值时,除非划分方案专门加以处理,否则可能造成严重的负载不均衡。
全局有序不仅要求各分区内部有序:较前分区中的每条记录都必须排在较后分区中的每条记录之前。全局稳定性还提出了另一项要求,通常通过为记录附带原始位置或序列标识符,并将其作为键值相同时的排序依据来满足。故障恢复、网络带宽、序列化和临时存储的开销,可能超过本地排序的开销。因此,分布式排序不仅涉及算法选择,也同样涉及数据放置与系统协调。
库接口与实现选择
排序库对外提供的是行为约定,而不是对内部算法的完整描述。这些约定可能规定稳定性、最坏情况下的比较次数、迭代器要求、内存使用方式,或比较失败时的处理方式。只要遵守这些约定,实现就可以在不同版本之间发生变化。因此,不应将与某种语言相关联的算法名称视为该语言所有实现永久不变的属性。
在 C编程语言中,qsort 接受起始地址、元素数量、元素大小和比较回调函数。尽管名称如此,这个接口并不要求使用快速排序,也不保证稳定性。其通用的面向字节的接口还意味着,与针对已知类型生成的专用代码相比,比较函数调用和记录移动的开销可能相对较高。
C++ 区分 std::sort 和 std::stable_sort。前者不保留等价元素之间的相对顺序,现代标准要求其最坏情况下的比较次数为 。后者提供稳定性保证,具体的资源需求和复杂度取决于适用的标准及可用的辅助存储空间。内省排序是 std::sort 常见的实现策略,但规范所作的保证比任何一种内部设计都更为根本。
Python 的列表排序和 sorted 操作都是稳定的,并且支持键函数。在一次排序中,每个输入项的键只计算一次,从而避免反复执行开销较大的转换。ECMAScript 2019 及后续版本要求 JavaScript 的 Array.prototype.sort 保持稳定性,但其默认排序方式会先将值转换为字符串,再比较这些字符串的 UTF-16 码元序列。因此,对数值排序通常需要显式提供数值比较函数,而不能依赖默认的字符串顺序。
“装饰—排序—去装饰”模式将键提取过程明确地分为几个步骤:为每条记录计算一个可排序的键并附在记录旁,对这些带有附加信息的记录进行排序,然后移除附加信息。将原始位置作为最后的决胜条件,可以模拟稳定性,不过这会占用额外存储空间,并改变用于比较的键。对索引而不是对象进行排序,也是一种有用的间接处理方式。
接口要求也反映了底层数据结构的特点。数组排序受益于随机访问能力,而链表排序则天然更适合采用归并。仅支持向前遍历的迭代器,无法直接高效地支持所有面向数组的算法。设计健全的应用程序编程接口会明确说明这些要求,而不是让看似通用的操作掩盖开销出乎意料地高的访问模式。
正确性、验证与对抗性行为
排序实现必须同时保证有序性和置换保持性。有序性指的是,按照指定的次序关系,任何靠后的元素都不应排在靠前的元素之前。置换保持性指的是,没有任何元素丢失、被重复添加或被替换。对于稳定排序,还需要满足第三项性质:键值相等的记录必须保持原有的相对顺序。
这些性质通常借助循环不变量来证明。在插入排序中,当前位置之前的前缀始终保持有序,且恰好包含相应的已处理元素。在归并过程中,输出前缀是合并后的全部输入在正确顺序下的前缀,而输入中尚未取用的部分仍保留着,供后续使用。采用分区操作的算法需要更精细的不变量,来描述哪些区域中的元素小于、等于或大于枢轴,以及哪些区域中的元素尚未与枢轴比较。
形式验证能够揭示测试通过后仍未显现的缺陷。2015 年就出现过一个著名案例:对 Java 的 Timsort 实现进行验证时发现,其对待合并有序段的管理未能足够严格地保证预期条件成立;精心构造的输入可能导致栈所用数组发生越界。这个案例说明,算法在高层逻辑上的正确性,并不能自动保证具体实现中的容量计算和调度规则也正确。
比较器的正确性同样重要。如果比较器的返回结果随时间变化、会修改集合,或违反传递性,就会破坏算法所依赖的假设。在某些语言的库中,这可能导致未指明行为或未定义行为;在另一些语言的库中,则可能引发异常或产生错误的排序结果。即便是看似简单的整数比较器,如果通过减法实现,而减法发生溢出,也可能存在缺陷。
因此,测试不能仅限于随机排列。值得测试的情况包括空输入和单元素输入、所有键值相等的输入、交替模式、较长的有序段、逆序输入、含有大量重复值的输入、数值极值,以及身份标识与键值不同的记录。稳定性测试会为键值相等的记录附上原始位置,并检查这些位置是否仍然保持有序。
当不可信输入能够迫使系统执行过量计算时,排序还涉及网络安全问题。可预测的快速排序枢轴选择规则可能使某些输入触发平方时间复杂度,从而让对外提供服务的数据处理流水线面临拒绝服务风险。随机化可以减轻某些利用可预测性的攻击,而具有最坏情况复杂度上界的后备方案则提供了另一种保护。固定的比较网络在比较调度层面与数据无关,但仅凭这一点还不能保证恒定时间执行:比较、交换、内存访问以及周边计算也必须避免依赖秘密数据的行为。
应用、部分排序与算法选择
排序常用于为后续操作准备数据。有序数组支持通过 二分查找,在 次比较内完成查找;两个有序集合也可以通过线性扫描进行合并或比较。键值相等的记录在排序后彼此相邻,便于去重和分组聚合。因此,即使用户并不要求输出直观可见的排序结果,排序在 数据库、文件处理和 信息检索 中仍然发挥着重要作用。
几何算法利用排序来组织空间关系。扫描线方法按坐标顺序处理事件,将多维问题转化为一系列更新操作。有些凸包算法会先按字典序或角度对点排序。在区间处理中,对端点排序有助于检测重叠和计算资源分配。在这些场景中,排序都提供了一种有用的顺序,但它只是完整算法的一个组成部分。
并非所有任务都需要对全部输入排序。选择算法可以找出指定秩的元素,例如中位数,而不必确定所有元素的秩。随机化快速选择算法的期望时间复杂度为线性;通过精心选择枢轴,也可以实现确定性的线性时间选择算法。利用堆可以在 时间内维护最大或最小的 个元素,随后对这 个元素排序需要 时间。当 较小时,这种做法的开销可能远低于对全部 条记录排序。
其他操作有时可以完全避免排序。如果只关心按相等关系划分的等价类,基于哈希的分组方法可能达到期望线性时间,但不会生成有序输出。基于树的索引可以在记录陆续到达时增量维护顺序。优先队列支持反复访问最大或最小元素,而无须将整个集合维持为完全有序的序列。这些替代方案解决的是彼此相关但并不相同的问题。
因此,选择算法首先要明确所需的结果。如果要求稳定性,宜采用稳定的归并方法,或利用数据表示特征的稳定方法。辅助内存限制严格时,宜采用原地算法。对最坏情况下的延迟有严格要求时,宜采用具有明确性能上界的算法或混合算法。对于接近有序的记录,自适应方法更有优势;对于存储在磁盘上的超大规模数据,外部归并更合适;对于定长整数键,则可以优先考虑基数排序技术。
基准测试必须与实际工作负载相匹配。需要考虑的变量包括记录大小、键值分布、重复项数量、比较器开销、已有的有序段、可用内存,以及读取和写入的相对开销。单独衡量排序操作的开销时,应将输入生成、内存分配和结果验证与排序本身区分开来;而在端到端测量中,如果这些步骤属于实际任务的一部分,就必须将其计入。因此,实际比较的对象不应只是算法名称,而应是具体实现、它所提供的保证,以及它运行的环境。