稳定排序 (Stable Sort)
排序算法的一种特性：相等元素的相对顺序在排序后保持不变。
定义
稳定排序（Stable Sort） 是指：如果两个元素比较相等（或关键字相同），那么在排序前和排序后，这两个元素的相对位置保持不变。
例如：对 (value, originalIndex) 对进行排序，初始为 [(5,0), (2,1), (5,2), (1,3)]，稳定排序后结果为 [(1,3), (2,1), (5,0), (5,2)]，两个值为 5 的元素保持了原有的相对顺序（index 0 在 index 2 前面）。
核心特性
| 特性 | 说明 |
|---|---|
| 稳定性 | 相等元素保持原有相对顺序 |
| 适用场景 | 需要保持原始顺序的多关键字排序 |
| 实现难度 | 部分算法天然稳定，部分需要额外处理 |
稳定 vs 不稳定排序
| 排序算法 | 是否稳定 | 说明 |
|---|---|---|
| 冒泡排序 | ✅ 稳定 | 相邻交换，相等时不交换 |
| 插入排序 | ✅ 稳定 | 从后向前插入，相等时停止 |
| 归并排序 | ✅ 稳定 | 合并时相等取左半部分元素 |
| 计数排序 | ✅ 可稳定 | 使用前缀和+从后向前遍历可保证稳定 |
| 基数排序 | ✅ 稳定 | 每一位的排序必须使用稳定排序 |
| 选择排序 | ❌ 不稳定 | 跨位置交换可能破坏顺序 |
| 快速排序 | ❌ 不稳定 | 分区操作可能改变相等元素顺序 |
| 堆排序 | ❌ 不稳定 | 堆调整可能改变相等元素顺序 |
| 希尔排序 | ❌ 不稳定 | 增量分组可能跨位置移动 |
为什么稳定性重要
- 多关键字排序：先按主键排序，再按次键排序，需要次键排序是稳定的
- 保持原始顺序：某些应用场景需要保留数据的原始顺序信息
- 基数排序的基础：基数排序依赖每一位的稳定排序
如何实现稳定排序
计数排序的稳定版本
关键点：使用前缀和 + 从后向前遍历
// 稳定计数排序的核心步骤
// 1. 计算前缀和
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
// 2. 从后向前遍历原数组（保证稳定性）
for (int i = nums.length - 1; i >= 0; i--) {
int num = nums[i];
result[--count[num - min]] = num;
}
应用场景
- 基数排序：必须每一位都使用稳定排序
- 数据库排序：ORDER BY 多个字段时，需要稳定排序
- 对象多关键字排序：先按年龄排序，再按姓名排序