| 类型 | 时间复杂度 | 额外空间复杂度 | 稳定性 |
|---|---|---|---|
| 选择排序 | 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) | 有 |
1. 不基于比较的排序，对样本数据有严格要求，不易改写复用
2. 基于比较的排序，只要规定好两个样本怎么比大小就可以直接复用
3. 基于比较的排序，时间复杂度的极限是O(N*logN)
4. 时间复杂度O(N*logN)、额外空间复杂度低于O(N)、且稳定的基于比较的排序是不存在的。
5. 为了绝对的速度选快排；为了省空间选堆排；为了稳定性选归并；
若有收获，就点个赞吧
0 人点赞
