s005-排序算法的稳定性及排序总结
稳定性
如果一个数组[1,1,0,0,0,2,3,2]
最终排序后结果肯定是[0,0,0,1,1,2,2,3]
如果排在前面的0在排序后也放在前面，如果排在前面的1在排序后也放在前面...
即排序后值相等的数保持了排序前的顺序，认为该排序是稳定排序
例如学生类有班级和年龄两个字段
先将所有学生按照年龄排序，再按照班级排序
如果是稳定排序，则最后的顺序是按照班级排序，并且在班级内部学生是按照年龄排序的。
桶排序是有序的
排序总结
基于比较的排序
| 排序算法 | 时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|
| 选择排序 | $O(n^2)$ | $O(1)$ | no |
| 冒泡排序 | $O(n^2)$ | $O(1)$ | yes |
| 插入排序 | $O(n^2)$ | $O(1)$ | yes |
| 归并排序 | $O(nlogn)$ | $O(n)$ | yes |
| 快速排序（荷兰国旗问题） | $O(nlogn)$ | $O(logn)$ | no |
| 堆排序 | $O(nlogn)$ | $O(1)$ | no |
用哪一个？
不考虑稳定性的情况下，优先选择快速排序，在实验证明下，快排的时间最快，因为它时间复杂度的常数项比较低
如果额外空间要求很高，使用堆排序
如果要求稳定性，使用归并排序
常见的坑
- 归并排序的额外空间复杂度可以变成O(1),但是非常难，不需要掌握，又想去可以搜“归并排序 内部缓存法”，但是实现后排序不再稳定
- “原地归并排序”的帖子都是垃圾，因为归并排序的时间复杂度变为$O(n^2)$
- 快排可以变成稳定的，但非常难，不需要掌握，可以搜论文“0-1 stable sort”，但是稳定后快排的空间复杂度变成$O(n)$
- 所有的改进都不重要，因为目前没有找到时间复杂度是$O(nlogn)$,额外空间复杂度是$O(n)$,又稳定的排序
- 有一道题目，是奇数放在数组左边，偶数放在数组右边，还要求原始的相对次序不变，时间复杂度$O(n)$,额外空间复杂度是$O(1)$，无解，这跟快排一样是0-1 stable sort问题，非常难
工程上对排序的改进
- 充分利用$O(nlogn)$和$O(n^2)$排序的各自优势，有的时候会看到在快排中当数组的长度小组60的时候，会采用插入排序，在数组长度较大的时候会采用快排。
- 稳定性的考虑，在Arrays.sort()的源码中可以看到，如果是基本类型，采用快排，如果是非基本类型，采用归并排序
- c/c++/java底层的排序代码都非常长，利用各种排序的优势做结合