2.6.1　快速排序算法

快速排序是一种最坏情况为O(n^2)的排序算法，虽然这个最坏情况比较差，但快速排序通常是用于排序的最佳实用选择，这是因为它的平均性能比较好，其排序期望运行时间为O(nlgn)，且O(nlgn)记号中隐含的常数因子很小。另外，它还不消耗额外的内存空间，在嵌入式环境中也能很好工作，因此广受人们欢迎，是最常用、最好用的排序算法。

快速排序算法的排序步骤如下。

1）从序列中选一个元素作为基准元素。

2）把所有比基准元素小的元素移到基准元素的左边，把比基准元素大的移到右边。

3）对分开来的两个（一大一小）区块依次进行递归、筛选后，再对这两个区块进行前两个步骤的处理。

简单来说，就是选取一个区域里的数字，把这个区域按这个数字分成两半，一半小一半大，然后继续对这两部分执行同样的操作，直到所有筛选都完成，就完成了排序。

该排序算法最差的情况是，每次都选到一个最小的或最大的数字，这样每次筛选时都要充分移动，不过这种排列方式的相对概率低。快速排序是最常用的排序方法，所以我们要着重优化此算法。

下面就来看看如何优化快速排序算法。

1.随机选择中轴数

在快速排序时，选择以哪个元素作为中轴数比较关键，因为这会影响算法的排序效率，如果选中的数字不是中间的数字，而是一个偏小或偏大的数字，那么排序的速度就会大大降低。如果选中的刚好是最大的或最小的数字，则更糟糕，左边或右边完全没有数字可以排，相当于一次完整的遍历只排序了一个元素。

因为我们查找区间那个准确的中轴数会花费很多精力，所以只能减小得到最坏情况的概率，随机获取列表中的元素作为基准元素。虽然随机是为了减小选到最大值和最小值的概率，但随机也会选到不好的基准元素，实际上，随机数并没有对排序提供多大的帮助。

2.三数取中

为了让选择的中轴数更接近中位数，可以将头、中、尾3个数字先进行排序，最小的数字放在头部，中间的数字放在中部，最大的数字放在尾部，然后用3个数字去提高有效接近中位数的中轴元素。

在每个区间的头、中、尾排序前都先执行这个操作，也就是说，每次排序前，中轴数都不可能是最小的，起码是区间里第二小的或者第二大的，这样选出来的中轴数靠近中位数的概率就很大。

那么是否可以把3个数扩大到4个或M个数？其实过多数字的选择就相当于多出了一个排序算法，降低了二分排序的效果，实际效果不如3个数字来得快。虽然可以用随机选取3个数字的方式，但实际上这对中轴数的选择并没有什么帮助，况且伪随机数的计算和冲突的解决也是需要消耗CPU空间的，因此三数取中是选择接近中位数的元素比较有效的办法。

3.小区间使用插入排序

排序算法有各自的使用量级，当量级不同时，排序效率可能不一样。插入排序就依赖于序列的有序性和排序元素的数量，即排序的效率由排序列表的有序程度决定，也与排序的元素数量有关，如果序列的排序刚好是反序的，则排序效率最低，反之，如果是有序序列，则效率最高。

插入排序的特点是排序序列越长，效率越差。短序列的排序效果很好，高效排序序列长度为8左右。于是我们可以用这个特点来改善快速排序中的效率，即当切分的区块小于或等于8个时，就采用插入排序来替代快速排序，因为8个以下的元素排序时，插入排序能达到更好的效率，因此我们可将它与快速排序混合使用，这样的排序效率更高，其他时候仍然采用快速排序算法。

4.缩小分割范围，与中轴数相同的合并在一起

除了选择更加靠近中位数的数字作为中轴数，以及小范围使用更快的排序方式外，我们还可以通过缩小排序范围的方法来提高排序效率。

可以把与中轴数相同的数合并到中轴数左右的位置，这样分割后两边的范围就会缩小，范围越小，排序的速度就越快，刨去了更多不需要排序的元素。具体操作步骤为，在每次的分割比较中，当元素与中轴数相等时，直接将其移动到中轴数身边，移动完毕后划分范围从中轴数变为最边上相同元素的位置，使用这种方式来缩小范围，后续可减少排序元素。

快速排序是最常用也是使用范围最广的排序算法，铭记于心很有必要。