image.png
归并排序需要临时空间O(n),由于是递归实现，所以应该是O(n+logn)，但是logn比n小，所以是O(n)
快速排序由于递归的关系，栈占O(logn)的空间。
堆 最后一个非叶子节点的索引 (count-1)/2
稳定排序
经过排序以后，3的位置排在前面的依然靠前
image.png
稳定排序：对于相等的元素，在排序后，原来靠前的元素依然靠前，相等元素的相对位置没有发生改变。
例如：
1、订单先按照金额排序，然后再按照时间排序，这样在相同的时间下，金额大的或者小的排在前面，如果不是稳定排序，顺序就会错乱。
2、对于学生成绩单排序，刚开始是按照学生姓名顺序排序的，现在再根据学生分数排序，这样相同成绩的学生就按照学生姓名字典排序。
算法至今为止，还没有发现一种算法支持：能够平均时间复杂度O(nlogn)、原地排序、空间复杂度O(1)、而且稳定排序
对一组数据进行排序 场景分析
可能会选择 “快速排序” 复杂度为 O(nlogn)
1、有没有可能包含大量的重复元素？
如果包含大量的重复元素，“三路快排” 是更好的选择，当最后分割的元素小于286个时，分割元素可能更接近于排序，可以用“插入排序”，因为此时用“插入排序”复杂度趋近于O(n)。Java语言中标准库的快速排序就是使用“三路快排”实现的。
可以参考 Collections.sort() 和 Arrays.sort（）的源码
下面是 Arrays.sort(); 源码
public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
可以看到这里有一个DualPivotQuicksort，DualPivotQuicksort翻译过来就是双轴快速排序（关于双轴快速排序我们后期在讨论，可以认为是对我们普通使用的快排的一种改进，另外还有一种改进是三路快排！），再次点进去，可以发现有这么一段代码：
if (right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right, true);
return;
}
发现如果数组的长度小于QUICKSORT_THRESHOLD的话就会使用这个双轴快速排序，而这个值是286。
那如果大于286呢，它就会判断数组的连续升序和连续降序性好不好，如果好的话就用归并排序，不好的话就用快速排序，看下面这段注释就可以看出：
/*
* The array is not highly structured,
* use Quicksort instead of merge sort.
*/
那现在再回到上面的决定用双轴快速排序的方法上，再点进去，发现又会多一条判断：
// Use insertion sort on tiny arrays
if (length < INSERTION_SORT_THRESHOLD) {
//。。。。
}
即如果数组长度小于INSERTION_SORT_THRESHOLD(值为47)的话，那么就会用插入排序了，不然再用双轴快速排序！
总结，如果数组长度大于等于286且连续性好的话，就用归并排序，如果大于等于286且连续性不好的话就用双轴快速排序。如果长度小于286且大于等于47的话就用双轴快速排序，如果长度小于47的话就用插入排序。示意图如下：
image.png
是否大部分数据距离它正确位置很近？是否近乎排序？
比如我们现在要对银行业务按照银行业务发生的时间进行排序，大多数银行业务是按照业务完成的时间存入库中，如果按照业务发生的时间来看，是近乎有序的，因为大多数业务先发生也是先完成，只有少数极个别的业务可能处理的时间非常长，如果是这样的话，“插入排序法”可能是更好的选择。
是否数据的取值范围非常有限？
比如：对学生成绩排序，北京高考成绩出来了，高考成绩满分是750分，最低分是0分，它的取值范围为0-750，针对北京高考成绩数据进行排序，在这样的情况下，或许计数排序是更好的选择。
对排序有没有什么特殊的要求，是否需要稳定排序？
如果是的话，归并排序是更好的选择。
如果对数据的存储状态有要求，是否是使用链表存储的？
快排对数据随机存取有要求，如果使用的是链表存储的话，“快速排序”就不适用了，“归并排序”是更好的选择。
数据大小是否可以装载在内存里？
如果数据量很大，或者内存很小，不足以装载在内存里，需要使用外排序算法。
网友评论