重要排序算法总结
一、排序算法的稳定性
定义：
排序算法的稳定性是指：对于原始序列中两个相等的元素，在排序后它们的相对顺序不发生改变。
- ✅ 稳定：相等元素的相对位置在排序前后保持一致。
- ❌ 不稳定：相等元素的相对位置可能被颠倒。
稳定性的重要性：
- 对基础类型（如 int、double）无意义：因为值相同就无法区分，顺序无关紧要。
- 对非基础类型（如对象、结构体）有意义：可保留多关键字排序中的前序结果，例如先按语文成绩排序，再按总分稳定排序。
二、主要排序算法对比总结
| 排序算法 | 时间复杂度（平均） | 时间复杂度（最坏） | 空间复杂度 | 是否稳定 | 备注 |
|---|---|---|---|---|---|
| SelectionSort | O(N²) | O(N²) | O(1) | ❌ 不稳定 | 每次选最小值交换，会打乱相等元素顺序 |
| BubbleSort | O(N²) | O(N²) | O(1) | ✅ 稳定 | 相邻比较，相等时不交换可保持稳定 |
| InsertionSort | O(N²) | O(N²) | O(1) | ✅ 稳定 | 适合小规模或近有序数据 |
| MergeSort | O(N log N) | O(N log N) | O(N) | ✅ 稳定 | 归并过程合并时控制顺序可保持稳定 |
| QuickSort | O(N log N) （期望） | O(N²) | O(log N) | ❌ 不稳定 | 随机化快排应以期望时间复杂度为准，最坏情况概率极低 |
| HeapSort | O(N log N) | O(N log N) | O(1) | ❌ 不稳定 | 堆调整过程会破坏相等元素顺序 |
| CountSort | O(N + K) | O(N + K) | O(K) | ✅ 稳定 | K 为数据范围，适用于整数且范围小 |
| RadixSort | O(N * D) | O(N * D) | O(K) | ✅ 稳定 | D 为位数，K 为辅助空间，常用于字符串或整数 |
⚠️ 注意：
- 随机快速排序的复杂度必须按照概率期望来评估，其期望时间复杂度为 O(N log N)。若仅看最坏情况 O(N²)，则无法体现其实际高效性。
- 计数排序（CountSort）和基数排序（RadixSort）是非比较排序，突破了 O(N log N) 的比较下界。
三、补充说明
1. 时间复杂度说明
- O(N²)：适用于小数据量或部分有序场景（如冒泡、插入、选择）。
- O(N log N)：通用高效排序，如归并、快排、堆排。
- O(N + K) / O(N × D)：线性时间排序，需满足特定条件（如整数、固定位数）。
2. 空间复杂度说明
- O(1)：原地排序，仅使用常数额外空间。
- O(log N)：快排递归栈深度（随机化下期望值）。
- O(N)：归并排序需要辅助数组。
- O(K)：计数排序需要大小为 K 的计数数组。
3. 实际应用建议
| 场景 | 推荐算法 |
|---|---|
| 通用排序，追求平均性能 | 随机快排（QuickSort） |
| 要求稳定排序 | 归并排序（MergeSort） |
| 小规模或近有序数据 | 插入排序（InsertionSort） |
| 整数且范围较小 | 计数排序（CountSort） |
| 多位数字或字符串排序 | 基数排序（RadixSort） |
| 内存受限，不要求稳定 | 堆排序（HeapSort） |
四、结语
掌握各排序算法的时间/空间复杂度与稳定性是算法设计与工程实践的基础。在实际开发中，应根据数据特征（规模、类型、有序性、稳定性需求）选择合适的排序策略。
📚 提示：JDK 中
Arrays.sort()对基本类型用双轴快排，对对象类型用稳定归并排序（Timsort 变种），正是综合考虑了性能与稳定性的体现。
