排序算法优化

前面文章分别讲解了冒泡排序，插入排序，选择排序；快速排序，归并排序；桶排序，计数排序，基数排序，三大类排序算法。

如何识别排序算法优劣，衡量指标为时间复杂度，空间复杂度。

时间复杂度又分为：最好时间复杂度，最坏时间复杂度，平均时间复杂度，以及特别的均摊时间复杂度。

空间复杂度，又引申出了原地排序O(1)。

还有一个维度就是排序算法是否稳定。

由于快速排序和归并排序都使用了递归，为了避免堆栈溢出，需要限制递归的深度。一是通过设置阈值防止递归过深，二是通过手动模拟递归出栈和进栈的过程。

还有一点是快速排序算法，防止恶化为时间复杂度为O(n^2)，需要选择合适的分区点，一般采用的方法有：1，三数取中法。从数组头，尾，中间，分别取出一个数，比较大小，获取三个数的中间值作为分区点。2，随机法。从数组中每次都通过随机函数获取一个值。

目前使用排序算法，都不会只使用一种，基本都会根据不同的情况来选择不同的排序算法。在JDK1.8中java.util.Arrays中sort()的排序，就分为如下几种情况：

1，元素个数小于47的时候，选择插入排序。

2，元素个数大于47小于286的时候，使用双轴快排。

3，元素个数大于286的时候，则用timesort归并排序。