# 排序总结&避坑指南
| 时间复杂 | 额外空间复杂 | 稳定性 | |
|---|---|---|---|
| 选择排序 | O(N^2) | O(1) | 无 |
| 冒泡排序 | O(N^2) | O(1) | 有 |
| 插入排序 | O(N^2) | O(1) | 有 |
| 归并排序 | O(N*logN) | O(N) | 有 |
| 随机快排 | O(N*logN) | O(logN) | 无 |
| 堆排序 | O(N*logN) | O(1) | 无 |
| ========== | ========== | ========== | ========== |
| 计数排序 | O(N) | O(M) | 有 |
| 基数排序 | O(N) | O(N) | 有 |
# 排序算法的稳定性
- 稳定性，是指在排序后，同样大小的样本之间的相对顺序不会发生变化。
- 对于基础类型而言，稳定性似乎毫无意义。
- 但是，对于那些非基础类型，稳定性却蕴含着深刻的含义和价值。
- 有一些排序算法被设计成可以保持相对顺序的稳定状态，然而，也有一些排序算法，无论如何都无法达到稳定。🎭
# 场景展示
在排序的大舞台上，稳定性是一种珍贵的品质，如同排序算法的黄金标志。让我们深入探索一下为什么在各种场景中都需要排序的稳定性。
购物之旅：价格与好评度的完美组合
想象一下购物时，你希望按照价格排序，但同时也希望在同一价格范围内按照好评度排序。如果排序不稳定，先按价格排序可能会打乱原本按好评度有序的商品顺序。排序的稳定性就像是购物清单的魔法符咒，确保了你的排序需求不会互相干扰。
班级秩序：年龄与班级的和谐共舞
在学生大家庭中，我们可能需要按照年龄排序，然后再按照班级排序。如果排序不稳定，可能导致同年龄的学生在排序后位置发生变化，打破了原有的年龄序列。排序的稳定性就像是班级里的年龄秩序守护者，确保了排序的和谐进行。
为什么需要排序的稳定性？
维护相对顺序关系：
- 稳定性确保了相等元素在排序后仍然保持原有的相对顺序。这对于多级排序场景非常关键，比如购物时的价格与好评度。
不破坏先前排序：
- 排序稳定性意味着如果两个元素相等，排序的结果不会改变它们之间的相对位置。这对于多次排序操作非常重要，比如先按年龄排序再按班级排序。
提高排序的可控性：
- 稳定性让我们能够更加精确地控制排序的结果，确保在不同排序阶段的需求都能得到满足。
# 总结
- 不基于比较的排序，对样本数据有严格要求，不易改写
- 基于比较的排序，只要规定好两个样本怎么比大小就可以直接复用
- 基于比较的排序， 时间复杂度的极限是O(N*logN)
- 时间复杂度O(N*logN) 、额外空间复杂度低于O(N) 、且稳定的基于比较的排序是不存在的。
- 为了绝对的速度选快排、为了省空间选堆排、为了稳定性选归并
# 常见的坑
- 归并排序的额外空间复杂度可以变成O(1)，“归并排序内部缓存法”，是将变得不再稳定。
- “原地归并排序”是垃圾贴，会让时间复杂度变成O(N^2)
- 快速排序稳定性改进，“01 stable sort"， 但是会对样本数据要求更多。
# 工程上对排序的改进
- 稳定性的考虑
- 充分利用 O(N*logN) 和 O(n^2) 排序各自的优势