复习数据结构笔记之归并&快速排序
数据结构篇-10-排序算法小结
总结：如何实现一个通用的高性能的排序函数？
一、如何选择合适的排序算法？
1.排序算法一览表
时间复杂度 是稳定排序？ 是原地排序？
冒泡排序 O(n^2) 是 是
插入排序 O(n^2) 是 是
选择排序 O(n^2) 否 是
快速排序 O(nlogn) 否 是
归并排序 O(nlogn) 是 否
桶排序 O(n) 是 否
计数排序 O(n+k)，k是数据范围 是 否
基数排序 O(dn)，d是纬度 是 否
2.为什选择快速排序？
1）线性排序时间复杂度很低但使用场景特殊，如果要写一个通用排序函数，不能选择线性排序。
2）为了兼顾任意规模数据的排序，一般会首选时间复杂度为O(nlogn)的排序算法来实现排序函数。
3）同为O(nlogn)的快排和归并排序相比，归并排序不是原地排序算法，所以最优的选择是快排。
二、如何优化快速排序？
导致快排时间复杂度降为O(n)的原因是分区点选择不合理，最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。如何优化分区点的选择？有2种常用方法，如下：
1.三数取中法
①从区间的首、中、尾分别取一个数，然后比较大小，取中间值作为分区点。
②如果要排序的数组比较大，那“三数取中”可能就不够用了，可能要“5数取中”或者“10数取中”。
2.随机法：每次从要排序的区间中，随机选择一个元素作为分区点。
3.警惕快排的递归发生堆栈溢出，有2中解决方法，如下：
①限制递归深度，一旦递归超过了设置的阈值就停止递归。
②在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈过程，这样就没有系统栈大小的限制。
三、通用排序函数实现技巧
1.数据量不大时，可以采取用时间换空间的思路
2.数据量大时，优化快排分区点的选择
3.防止堆栈溢出，可以选择在堆上手动模拟调用栈解决
4.在排序区间中，当元素个数小于某个常数是，可以考虑使用O(n^2)级别的插入排序
5.用哨兵简化代码，每次排序都减少一次判断，尽可能把性能优化到极致
四、思考
1.Java中的排序函数都是用什么排序算法实现的？有有哪些技巧？
\1. 对于基本类型的数组，Java 采用的是双枢轴快速排序（Dual-Pivot Quicksort），这个算法是 Java 7 引入的。在此之前，Java 采用的是普通的快速排序，双枢轴快速排序是对普通快速排序的优化，新算法的实现代码位于类 java.util.DualPivotQuicksort 中。
\2. 对于对象类型，Java 采用的算法是 TimSort，TimSort 算法也是 Java 7 引入的。在此之前，Java 采用的是归并排序。TimSort 算法实际上是对归并排序的一系列优化，TimSort 的实现代码位于类 java.util.TimSort 中。
\3. 在这些排序算法中，如果数组长度比较小，它们还会采用效率更高的插入排序。
1，如何实现一个通用的，高性能的排序函数？
（1）线性排序算法的时间复杂度比较低，适用场景比较特殊。所以通用的排序函数不能使用线性排序算法。
（2）小规模数据排序，可以使用时间复杂为O(n^2)的算法；对大规模数据进行排序，时间复杂度是O(nlogn)的算法更加高效。所以为了兼顾任意数据规模的排序，一般都首选时间复杂度是O(nlogn)的排序算法。
（3）时间复杂度是O(nlogn)的排序算法不止一个，归并排序，快速排序，堆排序。但堆排序和快速排序使用较多。
（4）归并排序使用的不多是因为，空间复杂度是O(n)。
2，如何优化快速排序？
（1）O(n^2)的时间复杂度出现的主要原因是因为我们的分区点选的不够合理
在最坏情况下快速排序的时间复杂度是O(n^2)。如果数据原来是有序的或者是接近有序的，每次分区都选择最后一个数据，那快速排序算法就会变得很糟糕，时间复杂度就会退化为O(n^2)。
（2）最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。
（3）分区算法：
<1>：三数取中法：
从区间的首，尾，中间分别取出一个数，然后对比大小，取这3个数的中间值作为分区点。
这样每间隔某个固定的长度，取数据出来比较，将中间值作为分区点的分区算法，会好于单纯取某个数据。在要排序的数组比较大时，需要取更多的数。
<2>：随机法：
随机法就是每次从要排序的区间中，随机选择一个元素作为分区点。这种方法并不能保证每次分区点都选的比较好，但是从概率的角度看，也不大可能会出现每次分区点都选的很差的情况。
Arrays.sort
java8的排序
长度小于47：插入排序，包含普通插入排序和成对插入排序
长度小于286:快排，选择了两个pivote
长度大于286:检查数据是否有序，使用TimeSort或者快排
关于快排递归过深的处理的疑惑，以及关于 STL 里的 std::sort 是怎么实现的，可以看我这篇博客：https://liam.page/2018/09/18/std-sort-in-STL/