先把事故还原。期末结束,教务处要按总分从高到低导出一份成绩单。老师拿到表后打电话过来,说数据被改过了:上次看的时候,同分的几个学生是按学号排的,这次同分的那几个人顺序全乱了,要求恢复原文件。开发把两次导出的文件逐行比对,发现每一行的姓名、分数都对得上,只是同分记录的先后顺序不同。
问题不在数据,也不在导出代码写错了字段,而在排序这一步:代码用了一个不保证稳定性的排序,排序键又只有分数一个。分数相同的记录,谁在前谁在后,完全由算法内部的交换决定。换一次实现、换一个版本、甚至输入顺序稍微变一下,同分的顺序就变一次。老师看到的不是数据被改,而是同一批数据被排成了不同的样子。
这篇讲清楚三件事:稳定性到底保证什么,哪些算法稳定、哪些不稳定,以及当排序结果要给人看、要分页、要导出比对时,应该怎么把顺序钉死。最后会解释一个常见的困惑:为什么 Java 里对象数组排完是稳定的,原始类型数组排完却对不上原来的位置。
现场:分数一样,名单顺序却不一样
用最小的一组数据复现。五条记录,分数分别是 90、80、90、80、90,原始顺序是 a、b、c、d、e。先写一个手写快排,按分数降序,比较时相等也归到左侧。
function quickSortDesc(arr, lo = 0, hi = arr.length - 1) {
if (lo >= hi) return arr;
const pivot = arr[hi].score;
let i = lo;
for (let j = lo; j < hi; j++) {
if (arr[j].score >= pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
}
}
[arr[i], arr[hi]] = [arr[hi], arr[i]];
quickSortDesc(arr, lo, i - 1);
quickSortDesc(arr, i + 1, hi);
return arr;
}
本机跑出来的顺序是 a90、c90、e90、d80、b80。同样的数据,换成原生 Array.sort,比较器仍然只按分数降序,输出是 a90、c90、e90、b80、d80。两组结果分数都正确,九十分在前、八十分在后,但八十分那两个人的顺序反了。数据一条没少,位置变了。
原因在快排的分区方式:它把「不小于基准」的元素依次换到左侧,交换是跨距离的,两个相等的八十分可能被互换;原生排序在规范上要求稳定,相等元素不会被重排。快排本来就不承诺稳定,事故往往来自把「符合比较器」误解成「和上次一样」。
稳定性的定义:相等键保持原相对顺序
稳定性(stability)的定义很短:如果两条记录被比较器判定为相等,排序之后它们的相对先后顺序与排序之前相同,这个排序算法就是稳定的。注意主语是算法,不是数据;稳定性是实现的属性,不是结果的属性。
这里的「相等」是比较器说了算,不是对象相等。比较器只看分数时,九十分的张三和李四就是相等的,哪怕姓名、学号完全不同。排序算法没有义务知道它们还有别的差别,它只看到比较器返回了零。
还要分清「稳定」和「正确」。只按分数降序,任何同分排列都满足要求,不稳定排序并没有算错。稳定性提供的是一份额外的确定性:同样的输入,顺序可预期,换实现也不容易变。业务上需要「同分按学号」时,这份确定性才是必须的。
不稳定也不等于随机,同一个实现和输入通常是固定的;变的是换实现、换版本或换输入顺序。线上事故多发生在这些变化之后。
哪些算法稳定,哪些不稳定
判断一个算法稳不稳,看它会不会跨距离交换相等元素。插入排序和冒泡排序只比较相邻元素,遇到相等就停,相等元素的相对顺序不会变,所以稳定。归并排序在合并两段时,相等时规定先取左边那段,也能保证稳定。基数排序和计数排序按位或按桶分配,只要分配时保持原顺序,同样稳定。
快速排序的分区会把元素从一端换到另一端,相等元素可能被跨距离移动,所以不稳定。堆排序建堆和下沉时,会把末尾元素搬到根上,一次跨越很多位置,也不稳定。选择排序每轮把最小值换到前面,交换会打乱相等元素的次序。希尔排序按间隔分组插入,远距离移动同样破坏稳定性。
稳定的算法
插入排序、冒泡排序、归并排序、TimSort、基数排序、计数排序。共同点是相等元素不会被跨距离交换,或者合并时明确规定相等取左侧。
不稳定的算法
快速排序、堆排序、选择排序、希尔排序。共同点是存在远距离交换,相等元素的相对位置会被打乱,且算法不记录原始次序。
稳定是有代价的。归并和 TimSort 需要一个额外的临时数组,空间是 O(n);快排和堆排可以原地完成,额外空间是 O(log n) 或 O(1)。这也是很多标准库在原始类型上选择不稳定排序的原因:原始类型没有身份,稳定性对它们没有意义,省下临时空间更划算。
工程结论很直接:能用标准库的稳定排序就别自己写快排;必须自己写,就接受它不稳定,并在比较器里加唯一 tie-breaker,把「相等」消灭掉。
比较器返回 0 到底意味着什么
比较器的约定通常是三态:返回负数表示第一个应该排在前面,返回正数表示第二个应该排在前面,返回 0 表示两者相等、先后无所谓。关键在于最后这句「先后无所谓」:它不是让算法保持原顺序,而是允许算法自行决定。稳定算法会保持,不稳定算法不会。
最常见的错误是把比较器写成布尔值。JavaScript 会把 true 当成 1、false 当成 0,于是「不满足」被解释成「相等」,大量元素被判定为同分,排序几乎不生效。本机实测:五个字母用 (x, y) => x > y 排序,输出仍然是 b、d、a、c、e;改成三态写法后才是 a、b、c、d、e。
// 错误:返回布尔值,false 会被当成 0,也就是相等
const bad = (x, y) => x.score > y.score;
// 正确:三态,负数、零、正数
const byScore = (x, y) => y.score - x.score;
// 正确:字符串比较不要相减,用显式三态
const byName = (x, y) => (x.name < y.name ? -1 : x.name > y.name ? 1 : 0);
第二个常见错误是字符串直接相减,得到 NaN。NaN 参与任何比较都返回 false,排序结果看起来像随机,而且不同引擎结果可能不同。第三个错误是只比较一个字段,却以为「其他字段会自动按原顺序」。只有稳定算法加固定输入顺序才会,两个条件缺一不可。
比较器还必须满足传递性:甲大于乙、乙大于丙,却得出丙大于甲时,Java 会抛 comparison method violates its general contract,JavaScript 不报错但结果不可信。多键比较用或运算依次比,最容易保持传递性。
多键排序:顺序对了,结果才对
要让「同分按学号」,有两条路。第一条是两趟稳定排序:先按次要键排,再按主要键排。因为第二趟是稳定的,主键相等时不会打乱第一趟排好的次键顺序。第二条是单趟多键比较:主键相等时接着比次键,最后加一个唯一键兜底。
顺序不能反。先按主键排、再按次键排,第二趟会按次键重新组织全部数据,主键的顺序被覆盖,结果就错了。这是多键排序里最常见的错误,而且出错时的结果往往「看起来也有序」,只是按的是错的键。
// 两趟法:先次键,后主键,两趟都必须稳定
rows.sort((x, y) => (x.name < y.name ? -1 : x.name > y.name ? 1 : 0));
rows.sort((x, y) => y.score - x.score);
// 单趟法:主键相等时比次键,最后用唯一键兜底
rows.sort((x, y) => (y.score - x.score) || (x.id - y.id));
本机用五个学生验证。原始顺序是陈 88、李 92、王 88、赵 92、周 88。只按分数稳定排序,结果是李 92、赵 92、陈 88、王 88、周 88,同分保持了输入顺序。先按姓名排再按分数排,结果是李 92、赵 92、周 88、王 88、陈 88,同分内部按姓名有序。单趟加学号兜底,结果与两趟法一致。
tie-breaker 必须唯一。拿姓名当兜底,遇到重名仍然会留下「相等」,顺序又回到不确定。正确的兜底是主键、学号、自增编号这类能唯一确定一条记录的东西。只要比较器永远不返回 0,稳定性就不再重要,任何算法都能给出确定结果。
两趟法要排两次,时间大致翻倍,但比较器简单;单趟法只排一次,比较器更复杂。数据量大时单趟通常更快。
分页与导出:顺序抖动会变成事故
排序结果给人看时,顺序变了会被当成数据变了。更严重的是分页:按分数倒序取第一页十条、第二页十条,如果同分记录正好跨在边界上,顺序抖动会让某条记录同时出现在两页,或者两页都取不到。用户看到的是重复行和缺失行,实际数据库里一条没少。
这类问题的根源是「排序键不唯一」。SQL 的 ORDER BY 只写了一个分数,数据库没有义务保持同分记录的稳定顺序;即便某次执行恰好稳定,换索引、换执行计划、并行扫描、数据更新都会改变输入顺序。SQL 标准也不保证排序稳定。
修法有三层。第一层,把唯一键写进排序条件,ORDER BY score DESC, id ASC,让任意两条记录都有确定先后。第二层,分页不要用偏移量,改成按上一页最后一条的排序键继续取,也就是游标分页,避免边界漂移。第三层,导出时固定完整的排序键,并在文件里保留主键列,方便对方核对。
导出比对的误报也很常见:对账脚本按行号比较,一同分顺序变化就报大量差异;改成按主键对齐再比字段,差异立刻归零。比较两份数据,不要依赖行的物理顺序。
Java:对象数组稳定,原始类型不稳定
Java 的标准库把这件事做成了两套实现。对象数组用 Arrays.sort(Object[]),底层是 TimSort:稳定,最坏 O(n log n),需要一个临时数组。原始类型数组用 Arrays.sort(int[]) 这类重载,底层是双轴快速排序:不稳定,原地完成,没有对象开销,通常更快。
本机用 JDK 11 跑了一遍:五条记录按分数降序,Arrays.sort 和 List.sort 的输出都是 a90、c90、e90、b80、d80,同分的 a、c、e 保持了原顺序,八十分的 b、d 也保持了原顺序。同一组分数放进 int[] 排序,结果是 80、80、90、90、90,值是对的,但已经无法分辨哪个八十分是 b、哪个是 d。
这不是缺陷,而是取舍。原始类型数组里只有值、没有身份,稳定性无处观察,省下临时数组更划算;对象数组元素有身份,用户能看到同分先后,所以标准库选稳定实现。
所以「Java 排序是稳定的」这句话只对了一半。排对象稳定,排 int、long、double 不稳定;而且原始类型排完,原来的下标信息已经丢了,想恢复也恢复不了。需要稳定时,排对象数组,或者排一个下标数组,用下标回查原数据。
跨语言时更不要假设。同一份数据在不同语言上可能得到相同结果,也可能不同。把顺序要求写成显式的排序键,比记住实现细节可靠。
现象、原因与第一步排查
下面这些现象经常被误判成「数据被改」或者「数据库有问题」。看到类似症状,先按表里的第一步定位,不要急着重导数据。
| 现象 | 真实原因 | 第一步查什么 |
|---|---|---|
| 两次导出同分记录顺序不同 | 排序不稳定,且排序键只有一个,没有唯一兜底 | 比较器是否带唯一 tie-breaker |
| 翻页出现重复行或漏行 | 同分记录跨在分页边界,顺序每次抖动 | ORDER BY 是否包含唯一键 |
| 老师认为数据被修改 | 行内容没变,只是同分记录的相对顺序变了 | 按主键集合比对,而不是按行号 |
| Java 里对象数组稳定,int 数组对不上原位置 | 原始类型走双轴快排,而且值本身不带身份 | 是否应改为排对象或下标数组 |
| 比较器写成布尔返回,排序几乎没生效 | true 变 1、false 变 0,零被当成相等 | 返回值是否为三态 |
| 数字按字符串排,10 排在 2 前面 | 按字典序比较,逐字符比大小 | 是否转成数字或用自然排序 |
| 多键排序结果仍然不对 | 先排主键再排次键,次键把主键覆盖了 | 稳定排序的调用顺序 |
| 换语言或升级版本后顺序变了 | 稳定性是实现属性,不是数据属性 | 是否依赖了没写进代码的稳定保证 |
第一行和第三行是同一件事的两面:一面是技术原因,一面是人的感受。把两份数据按主键排序后再比内容,一致就说明只是顺序问题,根子在排序键。
边界与代价
稳定的代价首先是空间。归并和 TimSort 要开一个和输入同量级的临时数组,数据量大时内存峰值明显上升;快排和堆排原地完成,额外空间小。内存紧张、元素又很大时,这个差别足以影响能不能跑起来。
稳定的边界是「比较器认为相等」。如果比较器里混进了浮点误差、时区差异、大小写规则,两条本该相等的记录可能被判成不相等,稳定性就无从谈起。反过来,比较器判成相等的两条记录,业务上可能并不同等,稳定排序也只是保持它们原来的相对位置,不会替你排成业务想要的顺序。
还有一个边界是输入顺序本身。稳定排序保证的是「相对于输入不变」,可输入可能来自哈希表、并行扫描、无序的文件遍历,每次都不一样。这时候哪怕算法稳定,输出也会变。要彻底钉死顺序,只能让排序键唯一,让输出与输入顺序无关。
比较器不合法,稳定与否都救不了:不满足传递性时,TimSort 会抛异常,JavaScript 的结果则不可解释。这类 bug 往往要数据量变大才暴露。
结论:稳定性是算法的性质,确定性是业务的要求,两者不是一回事。要确定性就把唯一键写进比较器;要省空间就用不稳定算法加唯一键。
当天能做的练习
- 把本文的手写快排和原生 sort 各跑一次,打印五条记录的输出,确认八十分那两条的顺序差异,并说明是哪一步交换造成的。
- 把记录扩到五十条、只有三个分数档,统计原生 sort 前后同分记录的位置变化,验证稳定排序下这个变化为零。
- 写一个返回布尔值的比较器,对十个字母排序,记录结果;再改成三态写法,对比两次输出并解释差异。
- 用同一批学生数据,分别做「先姓名后分数」的两趟排序和单趟 tie-breaker 排序,确认两种结果一致;再把顺序反过来,观察错误结果。
- 造二十条同分记录,按每页五条取三页,分别用「只按分数」和「分数加学号」两种排序条件,统计重复行与漏行。
小结与下一篇
三句话收一下:稳定性只保证比较器判为相等的记录保持输入时的相对顺序,它是算法的性质,不是数据的性质;快排、堆排、选择排序不稳定,插入、归并、TimSort 稳定,稳定的代价通常是 O(n) 临时空间;要业务上的确定性,靠的是把唯一键写进排序条件,而不是指望底层算法。
下一篇讲内置排序怎么选。既然标准库里的排序大多是 TimSort,它到底做了哪些事:先找已经有序的小段,短段用插入排序,长段用归并,遇到坏输入还会检测并切换策略。理解了这些,就能判断什么时候该用内置排序、什么时候该自己控制比较器,以及为什么「换个语言排序就变慢」并不是玄学。