介绍
在算法与数据结构中，稳定排序（Stable Sort） 指的是：对于值相等的元素，排序后它们的相对原始顺序保持不变。
简单来说：如果两个元素的值一样，排序前谁在前，排序后谁还在前。
例子
假设有一组待排序的对象，按 年龄 排序：
原始顺序（编号 | 年龄）：
1. A → 25
2. B → 23
3. C → 25
4. D → 22
按年龄从小到大排序后：
如果是 稳定排序 的结果：
4. D → 22
2. B → 23
1. A → 25
3. C → 25
A 和 C 年龄都是 25，排序后仍然保持 A 在 C 前面（与原始顺序一致）。
如果是 不稳定排序 的结果：
4. D → 22
2. B → 23
3. C → 25
1. A → 25
A 和 C 年龄都是 25，但排序后 C 跑到 A 前面，原始相对顺序被改变。
这就是“稳定”与“不稳定”的本质区别。
为什么要关心稳定性？
很多时候我们不只按一个关键字排序，而是 多关键字排序，稳定性就非常关键。
典型场景：先按班级排序，再按成绩排序
- 先按班级排序（稳定）
- 再按成绩排序（稳定）
如果排序算法稳定，那么：
- 成绩相同的学生，会保持班级排序后的相对顺序
- 最终结果是：先按成绩，成绩相同再按班级，完全符合需求
如果排序不稳定，成绩相同的学生班级顺序会被打乱，多关键字排序就失效。
常见排序算法的稳定性
稳定排序
- 冒泡排序（Bubble Sort）
- 插入排序（Insertion Sort）
- 归并排序（Merge Sort）
- 基数排序（Radix Sort）
- 桶排序（Bucket Sort）
- 计数排序（Counting Sort）
不稳定排序
- 快速排序（Quick Sort）
- 选择排序（Selection Sort）
- 希尔排序（Shell Sort）
- 堆排序（Heap Sort）
为什么快排、选择排序不稳定？
1. 快速排序为什么不稳定？
快排的分区过程中，会进行跨位置的交换，很容易把原本在前面的等值元素换到后面。
例如数组：[2a, 2b, 1]（a、b 表示两个 2，原始顺序 a 在前）
- 选 1 作为基准，分区后会把 1 换到最前面，变成
[1, 2b, 2a] - 两个 2 的相对顺序被颠倒，所以快排不稳定。
2. 选择排序为什么不稳定？
选择排序每次找最小值，直接与当前位置交换，同样会跨位置交换，破坏等值元素顺序。
例如：[3a, 3b, 2]
- 找到最小值 2，与 3a 交换 →
[2, 3b, 3a] - 3a 和 3b 顺序颠倒，不稳定。
稳定 vs 不稳定，性能上有区别吗？
稳定性不影响时间复杂度，只影响“相等元素的相对顺序”。
- 稳定排序不一定慢（归并排序 O(n log n) 是稳定的）
- 不稳定排序也不一定快（选择排序 O(n²) 是不稳定的）
工程选择时：
- 需要多关键字排序 / 保留原始顺序 → 优先稳定排序
- 只关心速度、内存，不关心等值顺序 → 快排、堆排序更常用
总结
稳定排序：等值元素的原始相对顺序，在排序后保持不变。
不稳定排序：等值元素的原始相对顺序，在排序后可能被打乱。