| 名称 | 时间复杂度 | 额外空间复杂度 | 稳定性 |
|---|---|---|---|
| 选择排序 | O(N2) | O(1) | 无 |
| 冒泡排序 | O(N2) | O(1) | 有 |
| 插入排序 | O(N2) | 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(N2)
- 快速排序稳定性改进，“01 stable sort”，但是会对样本数据要求更多
- 在整型数组中，请把奇数放在数组左边，偶数放在数组右边，要求所有奇数之间原始的相对次序不变，所有偶数之间原始相对次序不变。时间复杂度做到O(N)，额外空间复杂度做到O(1) （快排做不到，此题也做不到（存在一种可能，如描述3））
工程上对排序的改进
稳定性的考虑
若有收获，就点个赞吧
0 人点赞
