什么是排序的稳定性？哪些排序稳定、哪些不稳定？为什么它重要？
简化版
稳定性指:排序后,值相等的元素相对顺序保持不变。稳定的排序有冒泡、插入、归并、计数、桶、基数;不稳定的有选择、希尔、快速、堆排。稳定性在多关键字排序里至关重要:先按次要键排、再按主要键用稳定排序,才能保证主键相同的记录仍按次要键有序。
详细版
定义:如果排序前 A 排在 B 前面,且 A、B 的排序键相等,那么排序后 A 仍在 B 前面,就是稳定的;否则不稳定。
按分数排序 [(小明,90), (小红,85), (小刚,90)]
稳定结果: [(小红,85), (小明,90), (小刚,90)] ← 90 分的小明仍在小刚前(原顺序)
不稳定可能: [(小红,85), (小刚,90), (小明,90)] ← 小明小刚顺序被打乱稳定性一览:
| 稳定 ✅ | 不稳定 ❌ |
|---|---|
| 冒泡排序 | 选择排序 |
| 插入排序 | 希尔排序 |
| 归并排序 | 快速排序 |
| 计数排序 | 堆排序 |
| 桶排序 | |
| 基数排序 |
口诀:稳定「冒插归 + 计桶基」,不稳定「选希快堆」。
完整版教学
一、稳定性到底是什么
稳定性只在「有相等的排序键」时才有意义。它关心的是:当两个元素的排序键一样时,它们排完序后的先后顺序,是否和排序前一致。
- 如果对基本类型(纯数字)排序,相等就是完全相同,谁前谁后无所谓,稳定性看不出区别。
- 但对对象/记录排序(按某个字段排),相等的键背后是不同的对象。这时「相等元素的相对顺序」就有实际意义了——稳定性才凸显出来。
二、为什么稳定性重要:多关键字排序(核心)
稳定性最重要的应用是多关键字排序。比如要「按部门排序,同部门内按入职时间排序」。做法是:
- 先按次要键(入职时间)排序。
- 再按主要键(部门)用稳定排序。
因为第二次排序是稳定的,部门相同的记录会保持第一次排好的入职时间顺序。如果第二次用不稳定排序,部门内的入职时间顺序就会被打乱,前功尽弃。
目标:先按部门、部门内按入职时间
① 先按入职时间排 → 全部按时间有序
② 再按部门稳定排 → 部门相同的,时间顺序不变 ✓
若②不稳定 → 部门相同的时间顺序被打乱 ✗这就是「稳定排序 = 能叠加多轮排序而不破坏前面结果」,是数据库 ORDER BY 多列、Excel 多级排序的底层原理。
三、为什么这些排序稳定
稳定的排序有个共同点:只在「严格必要」时移动元素,且相等时不改变相对顺序。
- 冒泡:只在
a[j] > a[j+1](严格大于)时交换,相等不换。 - 插入:
a[j] > cur时才后移,遇到相等就停,插在它后面。 - 归并:合并时
a[i] <= a[j]相等取左边,左边本来在前。 - 计数/基数:按值域/按位分配,天然保持先来后到。
它们都不会让相等元素「越过」彼此。
四、为什么这些排序不稳定
不稳定的排序都有**「远距离交换/移动」**,会让相等元素跨越彼此:
- 选择排序:
[5a, 5b, 3]选最小的 3 和 5a 交换 →[3, 5b, 5a],5b 跑到 5a 前。 - 快速排序:分区时基准两侧的远距离交换会打乱相等元素。
- 堆排序:建堆和「堆顶换末尾」的跨越式交换会打乱。
- 希尔排序:不同 gap 分组的跨组移动会打乱。
一个远距离交换就可能把某个元素甩到与它相等的元素后面,破坏稳定性。
五、能不能把不稳定改成稳定
一些不稳定排序可以「人为改稳定」,但有代价:
- 通用技巧:给每个元素附加一个「原始下标」作为次级比较键——当主键相等时,按原始下标比较。这样任何排序都变稳定,代价是需要额外存下标、比较变复杂。Java 的
Arrays.sort(对象)保证稳定(用 TimSort),Arrays.sort(基本类型)用快排不保证稳定(但基本类型不需要稳定)。 - 快排、堆排改稳定通常得不偿失,实际中要稳定就直接选归并/TimSort。
六、把不变量、推演与工程边界落到代码上
算法正确性的核心不是记住某个 while，而是始终维护这个不变量：稳定排序后，键相等记录的原始相对次序保持不变。
对应的状态推进是：判断具体实现是否让相等元素发生跨越，而不能只背算法名称。每次推进前都应能解释“为什么被排除的部分不可能再包含答案”，否则只是碰巧通过样例。
初始化边界与状态
while 尚未结束:
根据当前状态作出唯一可证明安全的选择
更新边界、计数或局部结构
断言不变量仍然成立
返回不变量在终止状态下推出的答案复杂度不能只背一个符号。稳定性不改变渐进时间复杂度，却可能要求额外空间或更受限的移动方式。
带数字走一遍：先按姓名稳定排序，再按部门稳定排序，最终部门为主键且同部门保持姓名序。手算时要同时记录下标、区间含义和本轮排除的候选，才能暴露等号与边界错误。
| 核对项 | 结论 |
|---|---|
| 前提 | 多字段记录、分阶段排序和业务顺序有语义时需要稳定性 |
| 时间复杂度 | 取决于所选排序算法 |
| 额外空间 | 取决于所选排序算法与稳定化方案 |
| 关键边界 | 快速排序、堆排序的远距离交换常破坏稳定；相等时取左保证归并稳定 |
| 替代方案 | 若键能拼成完整复合键，也可一次排序显式表达优先级 |
易错点：模板只有在前提和不变量一致时才成立；换了区间定义、重复值规则或输出语义，等号与推进方式就必须重新推导。
实现完成后至少检查五类用例：
- 空输入或题目允许的最小规模，验证初始化不会越界。
- 单元素与两个元素，验证循环条件和最后一次推进。
- 大量重复值，验证相等分支、稳定性或去重语义。
- 已满足目标性质与极端逆序/偏斜分布，观察最好和退化路径。
- 上面的数字样例逐轮手算，并与程序记录的状态轨迹逐项对照。
七、常见误区与追问
- 误区：只要记住模板就适用于所有输入。 本题成立的前提是“多字段记录、分阶段排序和业务顺序有语义时需要稳定性”，前提被破坏后必须换算法或重新证明。
- 误区：复杂度只写 取决于所选排序算法 就算完整。 还要说明输入参数、预处理、递归栈以及最坏退化条件；本题的推导是“稳定性不改变渐进时间复杂度，却可能要求额外空间或更受限的移动方式”。
- 误区：重复值和边界值不会改变代码。 快速排序、堆排序的远距离交换常破坏稳定；相等时取左保证归并稳定。
- 追问：为什么每次推进不会漏掉答案？ 因为始终维护“稳定排序后，键相等记录的原始相对次序保持不变”，被舍弃区域已由顺序或状态关系证明不可能更优。
- 追问：用一个数字例子怎么讲？ 可以从“先按姓名稳定排序，再按部门稳定排序，最终部门为主键且同部门保持姓名序”开始，逐轮写出状态与被排除区间。
- 追问：什么时候不该使用这个方案？ 当前提不满足或退化代价不可接受时，应考虑“若键能拼成完整复合键，也可一次排序显式表达优先级”。
- 追问：如何设计自测避免只过样例？ 同时覆盖最小规模、重复值、极端分布、无解/边界解，并对关键状态加断言。
八、加强记忆
排序稳定性 = 排序后相等元素的相对顺序不变。稳定的:「冒插归 + 计桶基」(冒泡、插入、归并、计数、桶、基数);不稳定的:「选希快堆」(选择、希尔、快速、堆排)。稳定的共性是「相等不越过彼此」,不稳定的都有「远距离交换」。重要性在多关键字排序:先排次要键、再用稳定排序排主要键,才能保持「主键相同按次要键有序」(数据库 ORDER BY 多列同理)。要稳定就选归并/TimSort。