排序算法稳定性到底是什么意思？
你有没有遇到过这种情况：给学生成绩排序，分数一样的人，原本按姓名字母排好的顺序，结果一排序，顺序全乱了？这很可能是因为你用的排序算法是“不稳定”的。
所谓排序算法的“稳定性”，指的是当两个元素的值相等时，排序后它们的相对位置是否保持不变。比如有两个学生，分数都是90分，A同学在B同学前面，稳定排序后，A依然在B前面；而不稳定排序可能就会把B排到A前面。
常见排序算法稳定性一览
下面这张对比表列出了常用排序算法的稳定性、时间复杂度和典型应用场景：
| 排序算法 | 是否稳定 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 |
|---|---|---|---|---|
| 冒泡排序 | 是 | O(n²) | O(n²) | O(1) |
| 插入排序 | 是 | O(n²) | O(n²) | O(1) |
| 归并排序 | 是 | O(n log n) | O(n log n) | O(n) |
| 计数排序 | 是 | O(n + k) | O(n + k) | O(k) |
| 基数排序 | 是 | O(nk) | O(nk) | O(n + k) |
| 选择排序 | 否 | O(n²) | O(n²) | O(1) |
| 快速排序 | 否 | O(n log n) | O(n²) | O(log n) |
| 堆排序 | 否 | O(n log n) | O(n log n) | O(1) |
为什么稳定性有时候很重要？
举个实际例子：你在处理电商订单，先按下单时间排序好，然后想按金额从高到低排。如果用了不稳定的排序，相同金额的订单可能会把原来的时间顺序打乱，导致分析出错。
再比如，你导出了一份员工名单，已经按部门排好了序，现在想按工号排序，但希望同部门的人尽量保持原有次序。这时候就得选稳定的排序算法。
怎么自己实现一个稳定排序？
如果你手写的排序不能保证稳定性，一个取巧的办法是：在排序键上加上原始索引。比如对数组排序时，把每个元素变成 [value, original_index]，排序时如果值相等，就比较索引。这样即使算法本身不稳定，也能靠索引“强制”稳定。
例如 Python 中可以用：
sorted(data, key=lambda x: (x.value, data.index(x)))不过更推荐直接使用内置的稳定排序，比如 Python 的 sorted() 和 list.sort() 都是基于归并排序的思想，是稳定的。
快速排序能变稳定吗？
标准的快速排序是不稳定的，因为它在分区过程中可能把相等元素的相对位置交换。但如果额外使用更多空间，比如把相等元素单独存起来，是可以改造成稳定的，只是代价高，一般没人这么做。
相比之下，归并排序天生稳定，因为合并两个有序数组时，相等元素优先取左边的，自然就保留了原顺序。