7.2　稳定性：同分时谁在前

学习目标：学完本节，你能

• 准确定义"排序稳定性"，并把它和"性能稳定"区分开；
• 判断一种排序是否稳定，并说出判断依据；
• 用稳定性一次完成多关键字排序。

先修：7.1（三种 $O(n^2)$ 排序）。 固定术语：排序稳定性、等值元素、多关键字排序。 环境与版本：.NET 8 / C# 12。 预计阅读：24 分钟。

一、直觉：两个价格一样的商品，谁该排前面？

你在做一个电商 App，商品列表要按价格从低到高排。

原始顺序： A(100元)  B(50元)  C(100元)  D(50元)  E(100元)  F(50元)

按价格排序后，50 元的商品是 B、D、F。它们三个谁在前、谁在后？

"排序稳定性"回答的就是这个问题：

如果排序是稳定的，那么值相等的元素会保持它们原有的相对顺序。

所以 B、D、F 应该保持 B → D → F，A、C、E 应该保持 A → C → E。

如果排序不稳定，这个顺序可能被打乱（比如变成 B → D → F → E → C → A 中的 100 元部分）。

为什么这件事重要？ 因为用户看到的列表顺序变了，但他没有任何办法解释为什么 —— 明明价格一样。这会让人觉得"这个 App 有 bug"。

二、形式化：稳定性的定义

一个排序算法是稳定的（stable），当且仅当：对于任意两个相等的元素 $a$ 和 $b$，如果排序前 $a$ 在 $b$ 前面，那么排序后 $a$ 仍然在 $b$ 前面。

关键点：

1. 只对"相等"的元素有要求。 不相等的元素本来就要按大小排，没有自由度。
2. 它约束的是"原始顺序"的保持。 所以必须能追踪"谁原本在哪" —— 实际实现里通常给每个元素带一个原始下标。
3. 稳定性是算法的性质，不是数据的性质。 同一个数组，用稳定排序和不稳定排序，结果可能不同。

验证稳定性的方法（本节代码用的就是这一招）：

/// <summary>检查排序结果是否「稳定」：价格相同的元素，原始下标必须保持递增。</summary>
static bool IsStable(Order[] sorted)
{
    for (int i = 1; i < sorted.Length; i++)
    {
        if (sorted[i].Price == sorted[i - 1].Price &&
            sorted[i].Seq < sorted[i - 1].Seq)      // 相邻两个值相等，但原始顺序反了
            return false;
    }
    return true;
}

思路：遍历排序后的结果，只要发现两个相邻元素值相等、但原始下标是递减的，就说明它们的相对顺序被颠倒了 → 不稳定。

三、实测：三种排序的稳定性

用 [A(100), B(50), C(100), D(50), E(100), F(50)] 这组数据（Seq 就是原始下标）：

  冒泡排序: B D F A C E
    稳定性: 稳定 ✓

  选择排序: B D F A E C
    稳定性: 不稳定 ✗

  插入排序: B D F A C E
    稳定性: 稳定 ✓

注意选择排序的结果：B D F A E C。

• 50 元的三个是 B D F —— 顺序正确 ✓
• 100 元的三个是 A E C —— 原来是 A C E，现在 E 跑到了 C 前面！ ✗

所以选择排序是不稳定的。

四、选择排序为什么不稳定

根源：选择排序做的是"长距离交换"。

手工推演一个更小的例子 [A(100), B(50), C(100), D(50)]：

第 1 轮：在 [A,B,C,D] 中找最小值 → B(50)，在下标 1。把 B 和下标 0 的 A 交换：

[B(50), A(100), C(100), D(50)]
         ^^^^ A 被甩到了后面

第 2 轮：在 [A,C,D] 中找最小值（从下标 1 开始）→ D(50)，在下标 3。把 D 和下标 1 的 A 交换：

[B(50), D(50), C(100), A(100)]
                ^^^^^^^^^^^^
        注意最后两个：原来是 A 在前、C 在后，现在变成 C 在前、A 在后！

A 和 C 的相对顺序被颠倒了。

对比冒泡和插入：

一句话判断法：

只做"相邻交换/移动"的排序是稳定的；做"长距离跳跃"的排序通常不稳定。

这条规律能帮你快速判断大多数排序算法的稳定性（下一章会用到）。

注意冒泡和插入的比较符号：

// 冒泡：严格「大于」才交换 —— 相等时不动，所以稳定
if (a[j] > a[j + 1]) { swap; }

// 插入：严格「大于」才继续往前 —— 相等时就停下，所以稳定
while (j >= 0 && a[j].Price > key.Price) { a[j + 1] = a[j]; j--; }

如果把 > 改成 >=，两个算法都会变成不稳定的（相等时也会交换/移动，颠倒了顺序）。

这是一个很微妙的细节：稳定与否，可能就取决于一个符号。

五、稳定性有什么用：一次完成多关键字排序

这是稳定性最重要的实际用途。

需求：员工表要"按薪资降序排列，薪资相同的按原来的顺序"。

做法一：直接排序（依赖排序本身稳定）

var sorted = employees.OrderByDescending(e => e.Price).ToArray();

实测输出：

  原始顺序: 张三 李四 王五 赵六 钱七（下标 0..4）
  薪资:     20000 15000 20000 15000 20000

  结果: 张三 王五 钱七 李四 赵六
  薪资: 20000 20000 20000 15000 15000

张三、王五、钱七都是 20000，它们的相对顺序和原始顺序一致 —— 因为 LINQ 的 OrderBy 是稳定排序。

注意：.NET 的 List<T>.Sort() 和 Array.Sort() 是不稳定的（它们用的是内省排序）。而 LINQ 的 OrderBy / ThenBy 是稳定的。

所以同样的需求，用 List.Sort() 和用 OrderBy 可能得到不同的结果。 这个差异经常让开发者困惑。

做法二：显式利用稳定性做多关键字排序

假设需求是"先按部门分组，组内按薪资升序"。

笨办法：写一个比较函数同时比较两个字段。

聪明的办法：从"次要关键字"到"主要关键字"，依次做稳定排序。

第一步：按【薪资】升序排一次
第二步：按【部门】再排一次（稳定排序）
结果：部门有序，且每个部门内部薪资是升序的 ✓

为什么这样是对的？

• 第二步按部门排序时，同一部门的元素从来不会互相交换（因为它们的部门"相等"）
• 而稳定排序保证它们保持第一步排好的薪资顺序
• 所以最终结果：部门升序 + 部门内薪资升序

这个技巧叫"基数排序式的从低位到高位排序"，它在 8.4 节的基数排序里会被发挥到极致 —— 基数排序就是用这个思想，把"按多位数字排序"拆成"逐位做稳定排序"。

代价：需要排序 $k$ 次（$k$ 是关键字的个数）。如果 $k$ 很小，这比写复杂的比较函数更简单、更不容易出错。

做法三：用现成的多关键字 API

var sorted = employees
    .OrderBy(e => e.Department)      // 第一关键字
    .ThenByDescending(e => e.Salary) // 第二关键字
    .ToArray();

最直观，推荐使用。 ThenBy 内部就是靠稳定排序实现的。

六、哪些排序是稳定的

先把结论列出来（第 8 章会逐个验证）：

一个实用建议：

如果你不确定一个排序是否稳定，但又需要稳定 —— 给元素加一个"原始下标"字段，把它作为最后一级比较关键字。

// 排序时带上原始下标作为决胜条件，就"人为地"实现了稳定
var sorted = items
    .Select((item, index) => (item, index))
    .OrderBy(x => x.item.Price)
    .ThenBy(x => x.index)          // <- 决胜条件：原始顺序
    .Select(x => x.item)
    .ToArray();

代价：多一次排序关键字比较，速度略慢。但零风险，不用去查文档确认某个排序稳不稳定。

七、练习

练习 7.2.1（判断稳定性） 在 7.1 节的插入排序代码里：

while (j >= 0)
{
    cmp++;
    if (a[j] <= key) break;      // 注意这里是 <=
    a[j + 1] = a[j];
    moves++;
    j--;
}

如果把 a[j] <= key 改成 a[j] < key，排序还稳定吗？为什么？

练习 7.2.2（设计测试数据） 你要测试一个排序算法是否稳定。请设计一组最小的测试数据，使得： (a) 稳定排序和不稳定排序会产生不同的结果 (b) 数组长度尽可能短 请给出你的数据，并说明为什么它能区分稳定和不稳定。

练习 7.2.3（判断） 判断对错并说明理由： (a) 不稳定排序是"有 bug"的排序。 (b) 如果数组里没有重复元素，那么讨论稳定性没有意义。 (c) List<T>.Sort() 和 LINQ 的 OrderBy 行为完全一样。

练习 7.2.4（工程场景） 下面四个场景，哪些需要排序稳定？说明理由。 (a) 把一堆整数从小到大排序 (b) 电商商品按销量排序，销量相同的按上架时间（越早越靠前） (c) 对一个日志文件按时间戳排序 (d) 数据库 ORDER BY price 查询，分页显示

练习 7.2.5（挑战·证明） 请证明：只做"相邻交换"的排序算法一定是稳定的。 （提示：考虑两个相等的元素 $a$ 和 $b$，$a$ 原本在 $b$ 前面。它们有可能交换吗？）

八、练习答案

7.2.1

不稳定了。

• 原来的 a[j] <= key：当 a[j] 等于 key 时，break 跳出循环，key 被插到 a[j] 的后面。因为 a[j] 原本就在 key 左边（它是已排序部分里的元素），所以保持了原有顺序 → 稳定。
• 改成 a[j] < key：当 a[j] 等于 key 时，条件 a[j] < key 为假，循环继续，a[j] 被移动到后面。最终 key 被插到了所有等值元素的左边 → 不稳定的。

具体演示，数组 [(3,'a'), (1,'x'), (3,'b')]（值相同的用字母区分原始顺序）：

用 <=（稳定）：

i=1: key=(1,'x')，比较 a[0]=(3,'a') > key  → 移动，(1,'x') 插到下标 0
     结果: [(1,'x'), (3,'a'), (3,'b')]
i=2: key=(3,'b')，比较 a[1]=(3,'a') <= key → break，插到下标 2（原位）
     结果: [(1,'x'), (3,'a'), (3,'b')]     ← 'a' 仍在 'b' 前面 ✓ 稳定

用 <（不稳定）：

i=2: key=(3,'b')，比较 a[1]=(3,'a') < key 为假 → 继续，a[1] 后移
     j=0，比较 a[0]=(1,'x') < key 为真 → break
     (3,'b') 插到下标 1
     结果: [(1,'x'), (3,'b'), (3,'a')]     ← 'b' 跑到 'a' 前面了 ✗ 不稳定

这个练习的要点：稳定与否，可能就由一个比较符号决定。 写排序算法时要特别留意"相等时怎么办"。

7.2.2

(a) 最少需要 4 个元素。

(b) 数据设计：

[(100, 'A'), (50, 'B'), (100, 'C'), (50, 'D')]

（值相同的用字母标记原始顺序：A 在 C 前，B 在 D 前。）

为什么 4 个元素是必需的？

• 2 个元素：如果有重复，那它们要么相等（无需排序），要么不重复（只有一个顺序）。区分不出来。
  • 比如 [A(1), B(2)] —— 已经有序，任何排序都不会改变它。
• 3 个元素：即使有重复（比如 [A(1), B(2), A'(1)]），也不一定能区分。
  • 试试 [A(1), B(2), C(1)]：稳定排序结果 [A, C, B]；选择排序呢？i=0 时找最小值 → A 或 C（都是 1），假设取第一个 → 不交换；i=1 时找 [B,C] 的最小值 → C，交换 → [A, C, B]。结果一样！
  • 因为选择排序只在 a[j] < a[minIdx] 时更新（严格小于），所以它会保留第一个最小值的下标。
• 4 个元素：能让"长距离交换"跨越另一个等值元素。
  • [A(100), B(50), C(100), D(50)] → 选择排序得到 [B, D, C, A]，而稳定排序得到 [B, D, A, C]。结果不同 ✓

设计测试用例的通用原则：要让"不稳定的行为"有发挥空间 —— 也就是制造"需要长距离交换、且交换路径上有等值元素"的局面。

7.2.3

• (a) 错。 稳定性是一个特性，不是正确性要求。不稳定排序也是正确的 —— 它只是不保证等值元素的顺序。

  什么时候稳定性才成为"正确性问题"？ 当你依赖它的时候。比如 7.2 节的"多关键字排序" —— 如果你用的排序不稳定，结果就是错的。

  所以通常的说法是："不稳定排序在对稳定性有要求的场景下会出错"，而不是"不稳定排序是错的"。

• (b) 错（不严谨）。 要分两种情况：
  • 数组里压根没有重复元素 → 稳定性确实没有实际影响（任何顺序都只有一种排法）。
  • 但"数据里没有重复"和"排序时没有相等的元素"是两回事 —— 如果排序关键字只是一个字段（比如按价格排，价格可能重复），那即使其他字段都不同，稳定性仍然有意义。 >

    准确的判断标准：看排序关键字有没有重复值，而不是看"数据里有没有重复"。

• (c) 错，而且这是个高频陷阱。 | | List<T>.Sort() / Array.Sort() | LINQ OrderBy | |---|---|---| | 实现 | 内省排序（快排 + 堆排 + 插入） | 归并类排序 | | 稳定性 | 不稳定 | 稳定 | | 性能 | 快（原地排序，无额外分配） | 慢一些（要分配临时数组） | >

  场景对比：同样的"按价格排序"，用 OrderBy 得到的等值元素顺序和 Sort() 可能不同。

  这经常导致微妙的 bug：本地测试用 LINQ 写得好好的，上线换成 Sort() 优化性能，结果等值元素的顺序变了，用户看到列表"跳来跳去"。

7.2.4

• (a) 不需要。 排的是整数本身，没有"附带信息"。相等的整数完全无法区分，也就无所谓顺序。
• (b) 需要。 "销量相同的按上架时间" —— 这正是"次要关键字"。有两种实现：
  1. 用稳定排序 + 两级关键字（推荐）
  2. 写一个同时比较销量和时间的比较函数

     如果用不稳定排序且只按销量排，销量相同的商品顺序就是随机的 —— 每次刷新页面顺序都可能变，用户会认为列表"在乱跳"。

• (c) 通常不需要，但要小心。 如果日志的时间戳精度足够（毫秒/微秒级），重复的概率很低。

  但现实中的时间戳经常重复：同一毫秒内处理了多条日志。这时如果排序不稳定：

  • 日志的原始顺序（也就是真实的处理顺序）会被打乱
  • 排查问题时，你会看到"结果先于原因发生"的假象

  这个场景特别危险，因为出错的不是界面显示，而是你的排查依据本身。建议对日志排序时一定要保证稳定（加一个自增序号当决胜关键字）。

• (d) 需要，而且是分页场景的经典陷阱。

  问题：ORDER BY price 时，价格相同的记录在不同页之间可能重复出现或丢失。

  比如有 100 条价格都是 10 元的记录，第 1 页取前 20 条、第 2 页取 21-40 条。如果每次查询时这些记录的相对顺序不同，用户就会看到：

  • 翻到第 2 页，发现了第 1 页已经看过的商品
  • 或者某些商品永远看不到

  标准解法：在 ORDER BY 里加上一个唯一列作为决胜条件：

  ORDER BY price, id          -- id 是唯一主键
  

  这是分页查询的必备实践，无论数据库的排序是否稳定。

  推广：任何"按非唯一列排序 + 分页"的场景，都必须加决胜条件。

7.2.5

证明：

设数组中有两个相等的元素 $a$ 和 $b$（即 $a = b$），且排序前 $a$ 在 $b$ 前面（即 $a$ 的下标小于 $b$ 的下标）。

要证明：排序后 $a$ 仍然在 $b$ 前面。

关键观察：相邻交换的排序算法，只在一个条件下会交换相邻的两个元素：

$$x > y \quad \text{（严格大于）}$$

现在考虑 $a$ 和 $b$ 会不会交换：

1. 它们不可能是"相邻且被交换"的那一对。 因为交换的条件是 左 > 右，而 $a = b$，不满足严格大于。所以 $a$ 和 $b$ 直接相邻时，它们永远不会互相交换。

2. 那它们会不会通过"间接"的方式改变相对顺序？ 只有当 $a$ 和 $b$ 交换了位置，它们的相对顺序才会变。而数组里元素的相对顺序只能通过交换来改变（这是排序算法唯一改变数组的手段）。

3. 但交换只会发生在相邻元素之间。 如果 $a$ 想跑到 $b$ 后面，它们必须在某一时刻变成相邻（因为一次只能挪一格），然后交换 —— 而第 1 点已经证明，它们相邻时不会交换。

所以 $a$ 永远不可能跑到 $b$ 后面。原顺序得以保持，算法是稳定的。 ∎

这个证明揭示了一个更强的结论：

只要满足"相邻交换条件是严格不等号"，排序就是稳定的。 不需要看别的。

推论：

• 冒泡排序（交换条件 a[j] > a[j+1]）→ 稳定 ✓
• 插入排序（移动条件 a[j] > key）→ 稳定 ✓
• 但如果你把 > 改成 >=，两个都会变成不稳定（练习 7.2.1 已经验证过）。

另一个重要的推论：归并排序虽然做的是"跨距离合并"（不是相邻交换），但它也是稳定的 —— 因为它有额外的规则："合并时如果左右相等，优先取左边"。这个规则起到了和"严格大于"同样的作用。

所以"只做相邻交换"是稳定的一个充分条件，但不是必要条件。 真正的判据是：算法在遇到相等元素时，有没有明确的规则保证原顺序不被打破。

九、常见错误

十、本节总结

1. 排序稳定性：值相等的元素，排序后保持原有相对顺序。它约束的是"同分时谁在前"。
2. 实测：冒泡稳定、选择排序不稳定、插入稳定。选择排序把 A C E 变成了 A E C。
3. 判断依据：只做"相邻交换/移动"的排序是稳定的；做"长距离跳跃"的通常不稳定。 选择排序的问题就出在长距离交换。
4. 一个符号决定稳定性：交换条件用 >（严格大于）就稳定，用 >= 就不稳定。
5. 稳定性的最大用途是多关键字排序：从次要关键字到主要关键字，依次做稳定排序，就能一次完成多级排序。这是 8.4 节基数排序的核心思想。
6. List<T>.Sort() 不稳定，LINQ OrderBy 稳定 —— 这个差异经常导致微妙的 bug。
7. 不确定时，加一个"原始下标"作为决胜关键字 —— 零风险的通用解法。

下一节衔接：本节反复提到"比较次数" —— 冒泡要 1249 万次、插入只要 4 万次。那么，"排序至少需要多少次比较"有没有理论上的下限？ 如果有，那个下限是多少？下一节用一个叫"逆序对"的概念把这个问题量化，并揭示它与插入排序的精确关系。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "7.2",
  "title": "稳定性：同分时谁在前",
  "covered": [
    "排序稳定性的定义与电商排序的直观例子",
    "稳定性的验证方法（检查等值相邻元素的原始下标）",
    "三种排序的稳定性实测（冒泡✓/选择✗/插入✓）",
    "选择排序不稳定的根源：长距离交换",
    "「相邻交换 vs 长距离跳跃」的快速判断法",
    "比较符号 > 与 >= 对稳定性的决定性影响",
    "多关键字排序的三种做法与基数排序的思想源头",
    "List.Sort 不稳定 vs OrderBy 稳定的差异",
    "数据库分页必须加唯一决胜列",
    "「只做相邻交换必稳定」的完整证明"
  ],
  "unresolved": [
    "归并排序的稳定性实现细节留到 8.1",
    "快速排序/堆排序的不稳定留到 8.2/8.3",
    "计数排序与基数排序的稳定性留到 8.4"
  ],
  "canonical_terms": {
    "排序稳定性": "等值元素排序后保持原有相对顺序",
    "等值元素": "排序关键字相等的元素",
    "多关键字排序": "按多个字段依次排序，低位关键字先排"
  },
  "symbols_units": {},
  "assumptions": [
    "读者已掌握 7.1 的三种排序实现",
    "读者理解 C# 的 record 与 LINQ 的 OrderBy/ThenBy"
  ],
  "word_count_actual": 2760,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch07/Sec72/",
    "三种排序的稳定性实测结果与手工推演一致（选择排序把 A C E 变成 A E C）",
    "练习 7.2.1 的符号改动推演已手工验证",
    "术语写法与 glossary.md 一致"
  ],
  "next": "7.3 比较模型与交换次数"
}