- 一、排序算法的稳定性
- 二、排序算法总结
- 三、排序算法常见的坑
- 四、工程上对排序的改进
- 1、稳定性的考虑
- 2、充分利用O(N*logN)和O(N^2)排序算法各自的优势
说了这么久的排序算法，是时候进行总结一下了。本文总结了排序算法的稳定性、排序算法常见的坑、工程上对排序算法的改进等。
一、排序算法的稳定性稳定性定义：稳定性是指样本在排序之后不会改变相对顺序。
对于基础类型来说，稳定性毫无意义
对非基础类型来说，稳定性有重要意义
| 排序算法 | 时间复杂度 | 额外空间复杂度 | 稳定性 |
|---|---|---|---|
| 选择排序 | 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) | 无（调整为大根堆或小根堆时就改变了相对顺序） |
1、不基于比较的排序，对样本数据有严格要求，不易改写
2、基于比较的排序，只要规定好两个样本怎么比大小就可以直接复用
3、基于比较的排序，时间复杂度的极限是O(N*logN)
4、时间复杂度O(N*logN)、额外空间复杂度低于O(N)、且稳定的基于比较的排序是不存在的。
5、为了绝对的速度选快排（时间复杂度的常数时间小）、为了省空间选堆排、为了稳定性选归并
三、排序算法常见的坑在网上见到以下相关的文章，如果不是做学术研究的，可以直接忽略，不然对于你而言只是浪费时间，最后发现毫无用处。
1、归并排序的额外空间复杂度可以变成O(1)，采用“归并排序 内部缓存法”，但是将变得不再稳定。
2、”原地归并排序"是垃圾贴，会让时间复杂度变成O(N^2)
3、快速排序稳定性改进， “01 stable sort" ，但是会对样本数据要求更多。
4、在整型数组中，请把奇数放在数组左边，偶数放在数组右边，要求所有奇数之间原始的相对次序不变，所有偶数之间原始相对次序不变。时间复杂度做到O(N)，额外空间复杂度做到O(1)。
这是不可能的。
这就是快排的partition分成小于、等于、大于区的过程，在此过程的标准和分奇偶一样是01标准，而快排的时间复杂度是O(N*logN)，额外空间复杂是O(logN)，所以是不可能的，不然快排早就改进了。
四、工程上对排序的改进 1、稳定性的考虑例如：Java中Arrays.sort()方法，如果传入的是基础类型，系统是采用快排进行排序的（因为此时的稳定性是无意义的，而快排比堆排更快）；如果传入的是非基础类型，系统是采用归并排序进行排序的（因为此时可能是需要稳定性的）。
2、充分利用O(N*logN)和O(N^2)排序算法各自的优势插入排序O(N^2)，但是常数项小
快速排序O(N * logN)，但是常数项高
也就是N很大的时候，采用快排；当N比较小（小于60，实验得出）的时候，采用插排。
