第十四节-排序优化

优化快速排序

• 三数取中法，九数取中法
• 随机法
• 限制递归深度
• 自己实现函数调用栈，手动模拟入栈出栈

举例分析排序函数

Glibc 中的 qsort()

小规模排序使用归并排序，空间换时间。
数据规模大时，使用快排。
快排采用三数取中法。
并采用自己实现堆上的栈，手动模拟递归来解决。
在快排中，当元素规模小于 4 时，不再递归，使用插入排序。
插入排序使用哨兵优化。

Java 中的基本元素排序

对基本元素类型，使用双轴快排

Java 中的引用元素排序

在 jdk 8 中，保留一个参数，若是开启，会使用归并排序。
默认使用 TimSort。大致思路如下：

1. 元素个数 < 32，采用二分查找插入排序(Binary Sort)。
2. 元素个数 >= 32，采用归并排序，归并的核心是分区(Run)。
3. 找出连续升或降的序列作为分区，分区最终倍调整为升序后压入栈。
4. 如果连续分区长度太小，通过二分插入排序扩充长度到分区最小阈值。
5. 每次压入栈，都要检查已存在的分区是否满足合并条件，满足则进行合并。
6. 最终栈内的分区倍全部合并，得到一个排序好的数组。

TimSort 的算法非常巧妙：

1. 找出左分区最后一个元素（最大）及在右分区的位置
2. 找出右分区第一个元素（最小）及在左分区的位置
3. 仅针对这两个位置进行合并，之外的元素元素本身就是有序的。