1. 概述
本文将介绍什么是稳定排序算法，以及它在实际开发中的应用场景。同时我们也会分析排序稳定性在哪些场景下是必须考虑的，哪些场景下可以忽略。
2. 排序算法中的稳定性
排序算法的“稳定性”指的是：当待排序的数据中存在多个相等的元素时，排序算法是否会保持它们原有的相对顺序。
- ✅ 稳定排序：相等元素在排序后的相对顺序不变
- ❌ 不稳定排序：相等元素之间的顺序可能被打乱
举个例子：
我们有数组 A = [5, 8, 9, 8, 3]，其中有两个 8。如果我们能通过排序算法得到 [3, 5, 8, 8, 9]，并且两个 8 的相对顺序没有变化，那这个排序算法就是稳定的。
下面这张图可以更直观地帮助我们理解：
如图所示，稳定排序保留了两个相同值（8）的原始顺序，而不稳定排序可能会打乱它们的顺序。
3. 稳定性何时重要？
3.1 稳定性适用的场景
并不是所有排序场景都需要稳定性。只有在以下情况下，稳定性才显得重要：
- 数据中存在可区分的相等元素
- 数据本身已经部分有序，排序操作需要保留原有顺序
举个实际例子：假设我们正在统计一篇文章中各个单词的出现频率，并希望按频率排序。如果多个单词频率相同，我们希望它们按字母顺序排列。
3.2 实例说明：单词频率排序
第一步：统计单词频率
输入文本：
how much wood would woodchuck chuck if woodchuck could chuck wood
输出结果：
how 1
much 1
wood 2
would 1
woodchuck 2
chuck 2
if 1
could 1
第二步：先按字母顺序排序，再按频率排序
第一次排序（按字母顺序）：
(chuck, 2)
(could, 1)
(how, 1)
(if, 1)
(much, 1)
(wood, 2)
(woodchuck, 2)
(would, 1)
第二次排序（按频率，使用不稳定排序）：
(wood, 2)
(chuck, 2)
(woodchuck, 2)
(could, 1)
(how, 1)
(if, 1)
(would, 1)
(much, 1)
⚠️ 问题来了：使用不稳定排序后，三个频率为 2 的单词顺序被打乱了，不再保持字母顺序。
如果我们使用稳定排序来按频率排序，结果如下：
(chuck, 2)
(wood, 2)
(woodchuck, 2)
(could, 1)
(how, 1)
(if, 1)
(much, 1)
(would, 1)
✅ 可以看到，频率相同的单词之间仍然保持了字母顺序。
3.3 基数排序（Radix Sort）与稳定性
基数排序（Radix Sort） 是一种非比较型排序算法，依赖于稳定排序的子过程（通常是计数排序）。
它的工作流程如下：
for 每一位数字 k（从最低位到最高位）:
使用计数排序对当前位进行排序
✅ 正是因为每轮排序都使用了稳定的子排序算法（如计数排序），Radix Sort 才能保证最终结果的正确性。比如在对十位数排序时，虽然 9881 向下移动了，但它仍然保持在 9888 的前面。
4. 常见排序算法的稳定性分类
下面是一些常见排序算法的稳定性分类：
| 排序算法 | 稳定性 |
|---|---|
| Merge Sort | ✅ 稳定 |
| Timsort | ✅ 稳定 |
| Counting Sort | ✅ 稳定 |
| Insertion Sort | ✅ 稳定 |
| Bubble Sort | ✅ 稳定 |
| Quicksort | ❌ 不稳定 |
| Heapsort | ❌ 不稳定 |
| Selection Sort | ❌ 不稳定 |
⚠️ 注意：某些不稳定排序算法也可以通过修改实现稳定排序，比如在 Quicksort 中使用额外信息来记录原始顺序。
5. 总结
- ✅ 稳定排序保留相等元素之间的原始顺序
- ❌ 不稳定排序可能会打乱这些元素的顺序
- 📌 在需要保留数据原有顺序的场景中（如多字段排序、Radix Sort），稳定性非常重要
- 🧠 多数排序算法的稳定性是其固有属性，但也有些可以通过改造实现稳定
理解排序算法的稳定性，有助于我们在实际开发中选择合适的排序策略，避免“踩坑”。