说了这么久的排序算法，是时候总结一下了。本文总结了排序算法的稳定性，排序算法的常见陷阱，以及排序算法在工程中的改进。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）无（调整为大根堆或小根堆时改变相对顺序）2.排序算法总结1.不基于比较的排序对样本数据要求严格，不易排序改写。2、基于比较的排序只要指定两个样本的比例就可以直接复用。时间复杂度极限为O(N*logN)4，时间复杂度为O(N*logN)，额外空间复杂度低于O(N)，不存在稳定的基于比较的排序。5、绝对速度选择快速排序（时间复杂度常数时间小），堆排序节省空间，合并选择稳定。3.排序算法的常见陷阱。学术研究可以直接忽略，否则对你来说只是浪费时间，到头来你会发现没用。1、归并排序额外的空间复杂度可以变成O(1)，采用“归并排序内部缓存方式”，但是会变得不稳定。2、“原地归并排序”是个垃圾帖，会让时间复杂度变成O(N^2)3、提高快速排序的稳定性，“01稳定排序”，但是会需要更多的样本数据.4.在整数数组中，请将奇数放在数组的左边，偶数放在数组的右边。要求所有奇数原来的相对顺序不变，所有偶数原来的相对顺序不变。时间复杂度为O(N)，额外的空间复杂度为O(1)。这是不可能的。这就是将快速排序的分区划分为小于、等于、大于区域的过程。这个过程的标准和parity、odd一样，而quicksort的时间复杂度是O(N*logN)，额外的空间复杂度是O(logN)，所以不可能，否则quickrow本来可以改进的。4.工程上对排序的改进1.稳定性的考虑例如：Java中的Arrays.sort()方法中，如果传入基本类型，则系统使用快速排序进行排序（因为此时的稳定性是没有意义的，并且快速排序比堆快）；如果输入是非基本类型，系统使用归并排序进行排序（因为此时可能需要稳定性）。2、充分利用O(N*logN)和O(N^2)排序算法各自的优势。插入排序是O(N^2)，但是常数项很小。快速排序是O(N*logN)，但是常量项高。当N很大时，使用fastrow；当N比较小时（小于60，通过实验得出），使用插件行。
