排序的“公平性”：稳定性是什么？以插入排序为例¶

想象这样一个场景：你和同桌一起参加跑步比赛，你们俩同时冲过终点线，成绩完全相同。教练说按“先到先排”的规则颁奖，那么你们俩的奖项顺序应该和赛前的起跑顺序一致——你先跑就排在你前面，同桌后跑就排在他后面。这就像排队时遇到“长得一样”的人，大家默认按先来后到的顺序，这就是一种“公平”。

在计算机的排序算法里，也有这种“公平性”，它的名字叫做稳定性。

什么是排序的“稳定性”？¶

简单说，稳定性就是指：当排序后的数组中出现两个值相等的元素时，它们在排序前的相对顺序是否保持不变。如果保持不变，这个排序算法就是稳定排序；如果顺序变了，就是不稳定排序。

举个例子：假设我们有一个数组 [3, 1, 3, 2]，这里有两个相等的元素 3（第一个 3 在原数组的第 0 位，第二个 3 在原数组的第 2 位）。如果排序后，这两个 3 的位置依然是“第一个 3 在前面，第二个 3 在后面”，那就说明这个排序算法是稳定的。

插入排序如何体现“稳定性”？¶

我们用插入排序来具体看看它是如何保持稳定性的。插入排序的核心思想是：每次从无序部分取出一个元素，插入到有序部分的正确位置。

模拟插入排序过程¶

以数组 [3, 1, 3, 2] 为例，它包含两个相等的 3，我们来一步步模拟插入排序：

初始状态：有序部分为空，无序部分为 [3, 1, 3, 2]。
处理第一个元素 3：有序部分变为 [3]，无序部分变为 [1, 3, 2]。
处理第二个元素 1：1 比 3 小，插入到 3 前面，有序部分变为 [1, 3]，无序部分变为 [3, 2]。
处理第三个元素 3：现在有序部分是 [1, 3]，当前元素是 3。我们需要找到 3 在有序部分的位置：
- 比较 3 和有序部分的最后一个元素 3，发现它们相等。此时插入排序的“关键”来了：相等时不交换，直接把新元素插入到相等元素的后面。
- 所以 3 插入到有序部分的末尾，有序部分变为 [1, 3, 3]，无序部分变为 [2]。
处理第四个元素 2：2 比 3 小，插入到 3 前面，再比 1 大，最终有序部分变为 [1, 2, 3, 3]。

最终排序结果是 [1, 2, 3, 3]，原来两个 3 的相对位置（第一个 3 在原数组第 0 位，第二个 3 在原数组第 2 位）在排序后依然保持：第一个 3 出现在第二个 3 前面。

为什么插入排序是稳定的？¶

插入排序的“稳定性”来源于它的插入逻辑：当插入一个新元素时，它会从有序部分的末尾开始，逐个与元素比较，遇到相等的元素就停止移动，直接把新元素插在后面。这就保证了：如果两个元素相等，后出现的元素永远不会跑到先出现的元素前面。

比如我们再用一个例子 [2, 2, 1] 测试：
- 初始有序部分 [2]，处理第二个 2 时，比较发现 2 等于有序部分的最后一个元素 2，所以直接插在后面，有序部分变为 [2, 2]。
- 接着处理 1，插入到有序部分最前面，最终结果 [1, 2, 2]。原来两个 2 的相对顺序（先出现的 2 在前面，后出现的 2 在后面）完全保持。

稳定性的意义¶

为什么要关心稳定性？想象你在做成绩排名：先按分数排序，分数相同的同学按学号从小到大排列。如果排序不稳定，两个分数相同的同学学号顺序可能被打乱，导致原本学号小的同学拿到了错误的排名。这时候，稳定性就保证了“公平性”——相同条件下，原始顺序被尊重。

插入排序正是因为这种“公平性”，在处理重复元素时表现优异。比如电商订单按“金额+时间”排序，相同金额的订单按下单时间先后处理，稳定性就确保了最早下单的客户优先。

总结¶

排序的“公平性”就是稳定性：当两个元素的值相等时，它们在排序前后的相对顺序是否不变。插入排序通过“相等时不交换，直接后插”的插入逻辑，天然保证了稳定性。这就像排队时遇到“同分选手”，严格按原始顺序排列，让每个元素都“公平”对待。

下次当你看到排序算法时，不妨想想：如果有两个相同的数字，它们的“座位”会被打乱吗？如果没有，那它大概率就是稳定的。而插入排序，就是一个永远“公平”的排序选手。