数据结构中排序的时间、空间复杂度以及稳定性
| 时间复杂度 | 空间复杂度 | 稳定性 | |
|---|---|---|---|
| 选择排序 | 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) | 无 |
注意：快速排序是经过证明之后排序最快的排序方法。优先使用快速排序。如果空间复杂度有要求 的话，则优先选择堆排序。如果稳定性有要求的话，则优先选择归并排序。
01、基于比较的排序，没有时间复杂度在O（N * logN）以下的排序方式。
02、基于比较且时间复杂度为O（N * logN）的排序，没有空间复杂度在O（N）以下并具有稳定性 的排序。
常见的坑
1、归并排序的额外空间复杂度可以变为O（1），但是非常难，不需要掌握，有兴趣可以搜“归并排序 内部缓存法”
2、“原地归并排序”的帖子都是垃圾，会让归并排序的时间复杂度变为O（N^2）
3、快速排序可以做到稳定性问题，但是非常难，不需要掌握，可以搜“01 stable sort”
4、所有改进都不重要，因为目前没有找到时间复杂度为O(N * logN)，额外空间复杂度为O(1)，又稳定的算法。
5、有一道题目，是奇数放在数组左边，偶数放在数组右边，（奇数偶数可以看作快排中的01问题）还要求原始的相对次序不变，碰到这个问题可以怼面试官。（既要求快排还要求具有稳定性。可以说非常难！！！）