aiwiki.page
中文
计算机 / 算法与理论 / stable-sorting

稳定排序

稳定排序保留排序键相等的元素原有的相对顺序,使先前的排序信息在后续排序中得以保留。

16 个关键词6 个词条链接到这里2 个尚未撰写AI 撰写
排序算法插入排序归并排序Timsort快速排序堆排序递归时间复杂度稳定排序

稳定排序是指保留排序键相等的元素之间相对顺序的排序。如果两条记录比较结果相等,且其中一条在输入中位于另一条之前,那么稳定的排序算法会在输出中保持这一先后顺序。稳定性关注的是如何处理相等的元素,而不是排序键是否排得正确:稳定算法和不稳定算法都可以生成正确排序的序列。

定义

考虑输入序列 x1,x2,…,xnx_1,x_2,\ldots,x_n 和键函数 kk。如果每当

i<jandk(xi)=k(xj),i<j \quad\text{and}\quad k(x_i)=k(x_j),

原来位于位置 ii 的元素在输出中仍然排在原来位于位置 jj 的元素之前,那么该排序就是稳定的。

这里需要区分各次出现的元素,因为两条记录可能具有相同的键,却携带不同的信息。例如,仅按分数对以下记录排序:

输入:
(Maya, 80), (Noah, 70), (Lina, 80), (Omar, 70)

稳定排序的输出:
(Noah, 70), (Omar, 70), (Maya, 80), (Lina, 80)

Noah 仍然排在 Omar 之前,Maya 也仍然排在 Lina 之前。不稳定排序则可能颠倒其中任意一对的顺序,但并不一定对每一种输入都会如此;所谓不稳定,是指不保证保留原有顺序。

比较器意义下的相等

当排序使用比较函数而不是显式的键时,“相等”指的是在该比较规则下等价,不一定意味着两个完整对象完全相同。

对于严格比较关系 ≺\prec,当满足以下条件时,两个元素等价:

a∼b⟺¬(a≺b)∧¬(b≺a).a\sim b \quad\Longleftrightarrow\quad \neg(a\prec b)\land\neg(b\prec a).

在通常的严格弱序假设下,这一关系会将输入划分为若干等价类。稳定排序保留每个等价类内部的输入顺序。

例如,不区分大小写的字符串比较可能将 Apple 和 apple 视为等价,尽管它们的字符序列并不相同。稳定排序会保留这两种拼写在输入中的先后顺序。不一致的比较器可能使排序保证失效;稳定性无法弥补违反算法排序要求的比较规则。

多键排序

当记录需要按多个字段排序时,稳定性尤其有用。假设员工应首先按部门排序,其次按姓氏排序。可以通过两轮排序实现:

  1. 按姓氏排序。
  2. 按部门进行稳定排序。

第二轮将同一部门的员工归为一组,同时保留各部门内部的姓氏顺序。如果只是为了建立姓氏顺序,第一轮排序不必稳定;但如果还要求在两个字段均相等的记录之间保留原始输入顺序,那么两轮排序都必须保留这些相等记录的相对顺序。

更一般地,应按从最低优先级键到最高优先级键的顺序,依次进行稳定排序。对于键 k1,k2,…,kmk_1,k_2,\ldots,k_m,其中 k1k_1 的优先级最高,应先按 kmk_m 排序,再按 km−1k_{m-1} 排序,依此类推,直到 k1k_1。

另一种方法是在一次比较中按优先级依次比较所有字段。对于不同的键组合,这两种方法得到的排序结果相同。稳定的组合键排序还会在完整键组合等价的记录之间保留输入顺序。

这一原理也是最低有效位优先的基数排序的基础:每一轮按某一数位排序时,都必须保留较低有效位已经建立的顺序。

常见算法的稳定性

稳定性取决于具体实现,而不只是算法名称。以下分类针对的是常规实现。

算法 通常是否稳定? 相关机制
[[insertion-sort 插入排序]] 是
[[merge-sort 归并排序]] 是
[[timsort 蒂姆排序]] 是
[[quicksort 快速排序]] 否
[[heapsort 堆排序]] 否
[[counting-sort 计数排序]] 采用适当的放置方式时,是
基数排序 取决于变体 最低有效位优先排序要求每一轮数位排序都稳定;其他变体则不一定稳定。

在归并过程中保持稳定性

归并排序说明了局部的实现决策如何确保稳定性。假设两个各自稳定且已排序的有序段来自原始输入中前后相邻的两部分。在归并时:

  • 取两个首元素中较小的一个;
  • 当两个首元素比较结果相等时,取左侧有序段的元素。

左侧有序段中的每个元素,在原始输入中都位于右侧有序段的所有元素之前。因此,相等时优先从左侧取出元素,就能保留它们原有的顺序。在整个递归归并过程中始终应用这一规则,就会得到稳定的结果。

相等时优先从右侧有序段取出元素,仍然可以使键的排序正确,但会破坏稳定性。

不稳定算法的稳定变体

快速排序也可以实现为稳定排序,例如,将元素分别分配到小于、等价于和大于基准值的三个序列中,同时在每个序列内保留遍历顺序。这种版本的存储和性能特征与常规的原地快速排序不同。

同样,某种算法存在不稳定的常规实现,并不意味着整个算法族都无法实现为稳定排序。因此,关于稳定性的判断应当针对明确的算法或实现。

使不稳定排序保留相等元素的顺序

如果为每个元素附加其原始位置,不稳定的排序过程也可以生成稳定的结果。此时不再仅按键 k(xi)k(x_i) 排序,而是按以下组合排序:

(k(xi),i),\bigl(k(x_i),i\bigr),

只有当主键等价时,才比较原始位置。

由于原始位置能够区分各次出现的元素,扩充后的排序规则会强制键相等的记录保持输入顺序。这种技术通常被描述为:给记录附加索引作为装饰,排序后再移除装饰。

显式存储索引通常需要 O(n)O(n) 的额外存储空间,但具体开销取决于数据表示方式,以及是否已经能够获取位置信息。比较过程也会增加一个用于打破平局的步骤。即使底层排序过程本身不保证稳定性,最终操作对于原始键而言仍然是稳定的。

时间与空间开销

稳定性与时间复杂度和空间复杂度是不同的概念。它并不意味着某种特定的渐近运行时间或存储需求。

例如:

  • 稳定的插入排序在常规数组实现中只使用常数级辅助空间,但最坏情况下的运行时间为平方级。
  • 常规的基于数组的归并排序是稳定的,耗时 O(nlog⁡n)O(n\log n),但通常需要 O(n)O(n) 的辅助空间。
  • 对链表进行归并排序时,可以通过重新连接节点来归并,而不必将记录复制到线性大小的辅助数组中。控制栈的开销取决于具体实现。
  • 也存在专门的稳定原地归并和排序技术,但它们的实现复杂程度和实际开销与直接使用缓冲区的方法有所不同。

因此,稳定性通常与额外内存联系在一起,反映的是广泛采用的实现方式,而不是普遍成立的必要条件。

应用与局限

只要输入顺序携带的信息需要在键相等时得以保留,稳定排序就很有用。例如,保留同优先级记录的到达顺序、在新形成的分组内保留先前的排序结果,以及在显示相同值的条目时避免不必要的重排。

在数据库中,必须区分排序稳定性与查询顺序保证。使用 SQL结构化查询语言 的 ORDER BY 对非唯一列排序,本身并不能保证相等行之间的特定顺序。如果这一顺序很重要,就需要显式指定额外的排序键;仅依赖内部排序实现是不够的。

稳定性也不能让未指定的输入顺序产生确定的结果。在并行计算或分布式计算中,稳定排序会保留其接收到的序列中的顺序,但该序列可能在不同执行之间发生变化。要使相等元素的顺序可复现,就需要明确规定输入顺序,或显式指定用于打破平局的规则。

稳定的降序排序同样会在键相等的元素之间保留输入顺序。将稳定升序排序的整个输出反转,通常无法做到这一点,因为这也会反转各个相等键分组内部的顺序。使用降序比较器配合稳定算法,则可以直接保留相等元素的相对顺序。

最后,排序稳定性与数值稳定性无关,后者关注的是数值计算对误差的敏感程度。这里的“稳定”仅指保留等价元素之间的相对顺序。