快速排序的四种优化方式

本文只讲述概念。

选用基准值（不在四种优化方式中）

选用基准值有三种方式，选用的基准值较好，快速排序的性能也会较好。

• 固定基准（也就是从begin的位置，作为排序的基准，没有一点优化，简单的快排方式都是这样）
• 随机基准（和固定基准差不多）
• 三数取中，这个基准就稍微优化了一些，从一堆数据中随机找出三个数据，把中间数据作为基准值，可以说是进行了稍微的优化。

下面讲一下四种优化方式

1. 当数据量到达一定大小是，选择使用插入排序或者堆排序

插入排序

当递归之后序列到达某一大小时，相对每个递归数组中的数据元素较少（一般<=16时），在使用递归显然会增加递归的深度，所以可以选用直接插入排序，降低递归深度，提高运算效率。

堆排序

当递归进行了较深的深度之后，但是每个递归数组中的元素还是较多，这是可以采用堆排序，从而降低递归深度，提排序性能。

2. 使用尾递归的方式进行内存优化

尾递归：简单理解就是，本次递归调用不会对主调函数中的任何变量数据产生影响。尾递归就是在主调函数的堆栈空间上重新使用该块空间，进行递归调用。
可以将快速排序的递归调用改为尾递归的方式，提高效率。

3. 聚集元素

在每次排序排完之后，可以将与基准值相同的元素放在基准值的左右两边，这样就可以是下次排序直接从这些基准值的左边和右边进行排序即可。
第一趟：[7] [2] [3] [1] [7] [4] [7] [9] [7] [8]
可以将其更改为：[4] [2] [3] [1] [7] [7] [7] [7] [9] [8]
第二趟就可以左边直接从1开始，右边直接从9开始，这样大大降低了重复元素在快排中消耗时间的额外开销。

4. 多线程排序