排序算法有个属性叫「稳定性」，课本上一句话带过：相等的元素排完后保持原来的相对顺序。我一直觉得这是句废话——都相等了，谁在前谁在后有什么区别？

一、先看两组结果

二十个学生，分数只在 90、80、70 三档里取，所以大量并列。原始顺序按名字排：

[A90 B80 C70 D90 E80 F70 G90 H80 I70 J90 K80 L70 M90 N80 O70 P90 Q80 R70 S90 T80]

用 JDK 自带的 Arrays.sort：

[C70 F70 I70 L70 O70 R70  B80 E80 H80 K80 N80 Q80 T80  A90 D90 G90 J90 M90 P90 S90]

70 分那一组：C、F、I、L、O、R——正是它们在原始顺序里的先后。并列对内顺序被打乱 0 对。

用自己写的一个快排（Lomuto 分区）：

[R70 C70 F70 I70 L70 O70  T80 B80 H80 K80 N80 E80 Q80  G90 J90 A90 P90 D90 M90 S90]

70 分那组从 C、F、I、L、O、R 变成了 R、C、F、I、L、O。90 分那组也从 A、D、G、J、M、P、S 变成了 G、J、A、P、D、M、S。

同样一份输入，同样按分数排，并列元素之间的先后全乱了。统计下来 20 对被打乱。

二、这就是「稳定性」

定义很直白：如果两个元素相等，排序前后它们的相对位置保持不变，这个排序就是稳定的。

上面的实验里，Arrays.sort 稳定（它用的是 TimSort），我写的快排不稳定。

为什么会不稳定？看 Lomuto 分区那几行：它把元素和 pivot 比较，小于的往左换。交换的动作会跨过其他元素，跨过去的时候就把别人的相对顺序改了。而 TimSort 是归并的思路，合并两个有序段时，相等的情况下优先取左边那个——顺序就这么保住了。

三、真正会咬人的地方

「相等了还在乎顺序」听起来无所谓。但只要你的排序是多键的，它立刻变成硬伤。

需求：按分数排，同分按名字排。常见写法是走两趟：

Arrays.sort(arr, Comparator.comparing(s -> s.name));   // 第一趟：次要键
Arrays.sort(arr, byScore);                            // 第二趟：主要键

原理是：第二趟按分数排完之后，同分的元素会保持第一趟留下的顺序。这个前提就是稳定性。

实测：

稳定排序走两趟： [C70 F70 I70 L70 O70 R70 ...]   同分内名字是否有序：是
非稳定排序走两趟： [R70 C70 F70 I70 L70 O70 ...]  同分内名字是否有序：否

同一段逻辑，换成不稳定的排序，结果就错了。而且它不报错——只是数据悄悄变成另一种顺序。

所以我现在的做法是：多键排序直接写复合比较器，一趟搞定，不依赖稳定性。

Arrays.sort(arr, Comparator.comparingInt((Stu s) -> s.score).thenComparing(s -> s.name));

四、Java 里哪些稳定哪些不稳定

我自己验证过的两条：

Arrays.sort(Object[]) 和 Collections.sort() 是稳定的。 JDK 7 之后对象数组用的是 TimSort，稳定性是有保证的。

Arrays.sort(基本类型数组) 不稳定。 它用的是双轴快速排序。但对 int[] 这种基本类型来说这无所谓——基本类型没有"身份"，两个 70 分是同一个 70，谈不上谁先谁后。稳定性只在"有身份的对象"上才有意义。

PriorityQueue 我就不敢说了，它的迭代顺序本来就没承诺。要用它取有序结果，靠的是 poll() 的顺序，而不是遍历顺序。

五、结论

稳定性不是"更高级的排序算法才有的特性"，是一个具体场景下必须有的保证：多键排序。

  • 单键排序：稳不稳定无所谓，结果一样
  • 多键排序：不稳的话，先排好的次要键会被打乱
  • 基本类型：没有身份，讨论稳定性没意义

所以「这个排序稳定吗」这个问题，真正该问的是「我是不是要靠稳定性来实现多键排序」。如果是，用复合比较器一趟排掉，比依赖稳定性更可靠。

附：验证代码

static class Stu {final String name;final int score;   // 分数只有 90/80/70 三档，制造大量并列
}// 稳定：JDK 的 TimSort
Stu[] stable = original.clone();
Arrays.sort(stable, Comparator.comparingInt(s -> s.score));// 不稳定：自己写的快排（Lomuto 分区）
static int partition(Stu[] a, int lo, int hi, Comparator cmp) {Stu pivot = a[hi];int i = lo;for (int j = lo; j < hi; j++) {if (cmp.compare(a[j], pivot) < 0) {swap(a, i, j);   // 这一步会跨过其他元素，顺序就在这里丢了i++;}}swap(a, i, hi);return i;
}// 统计：同一分组里，名字顺序和原始顺序不一致的对数
static int brokenPairs(Stu[] sorted) {int broken = 0;for (int i = 0; i < sorted.length; i++)for (int j = i + 1; j < sorted.length; j++)if (sorted[i].score == sorted[j].score&& sorted[i].name.compareTo(sorted[j].name) > 0)broken++;return broken;
}