共计 1162 个字符，预计需要花费 3 分钟才能阅读完成。
说了这么久的排序算法，是时候进行总结一下了。本文总结了 排序算法的稳定性 、 排序算法常见的坑 、 工程上对排序算法的改良等。
一、排序算法的稳定性
稳定性定义：稳定性是指样本在排序之后不会扭转绝对程序。
对于根底类型来说，稳定性毫无意义
对非根底类型来说，稳定性有重要意义
| 排序算法 | 工夫复杂度 | 额定空间复杂度 | 稳定性 |
|---|---|---|---|
| 抉择排序 | 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，试验得出）的时候，采纳插排。
