算法：稳定排序 作者：马育民 • 2026-02-01 21:45 • 阅读：10000 # 介绍 在算法与数据结构中，**稳定排序（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 前面**，原始相对顺序被改变。 这就是“稳定”与“不稳定”的本质区别。 --- # 为什么要关心稳定性？ 很多时候我们不只按一个关键字排序，而是 **多关键字排序**，稳定性就非常关键。 ### 典型场景：先按班级排序，再按成绩排序 1. 先按**班级**排序（稳定） 2. 再按**成绩**排序（稳定） 如果排序算法稳定，那么： - 成绩相同的学生，会保持**班级排序后的相对顺序** - 最终结果是：先按成绩，成绩相同再按班级，完全符合需求 如果排序不稳定，成绩相同的学生班级顺序会被打乱，多关键字排序就失效。 --- # 常见排序算法的稳定性 ### 稳定排序 - 冒泡排序（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²) 是不稳定的） 工程选择时： - 需要**多关键字排序 / 保留原始顺序** → 优先稳定排序 - 只关心速度、内存，不关心等值顺序 → 快排、堆排序更常用 --- # 总结 稳定排序：等值元素的原始相对顺序，在排序后保持不变。 不稳定排序：等值元素的原始相对顺序，在排序后可能被打乱。 原文出处：http://www.malaoshi.top/show_1GW2hTuT8gNG.html