Question

快速排序精讲——需要重点处理的三种特殊情况

Answer 1

快速排序是一种O(nlogn）级别的排序，其主要思想是将一个待排序的数组，根据指定的标定点进行划分，一次划分结束之后，分成两部分，一部分元素比标定点都小，另一部分元素比标定点都大。然后再利用递归原理，分别对两部分的元素进行快速排序。一般情况下，标定点的选择都是数组中的第一个元素。此时，快速排序的详细图例如下：

对于一个普通的数组，这种快速排序的效率是非常高，比我们之前讲的插入排序，选择排序至少快出一个数量级。快速排序为什么效率能够这么高呢？通过上面的分析我们知道，快速排序是通过一个标定点将一个待排序数列分成两部分，然后依次递归。关键就在这两个部分能不能大小接近一致，只要我们能够保证这个要求，快速排序就能够达到O(nlogn)的算法复杂度（具体的计算过程，请参考《算法导论》中的详细推到过程）。

但是，凡事就怕特殊，如果我们的数组，是一个基本接近有序的数组呢？这个时候，如果你还是把第一个元素作为标定点，这时快速排序的效率如何呢？我们可以先看一个示意图（假设数组是完全有序的）。

这个时候，通过标定点区分两个部分的数组序列是极为不平衡的，一个元素个数是0，另一个元素个数是n-1。这个时候，快速排序的算法复杂度已经是O(n2)了。那我们该如何避免这个问题呢？

这就是我们要优化快速排序的第一个问题：

方法也很简单，在选择标定点的时候，不是指定待排序数组的第一个元素，而是先产生一个数组大小范围内的随机数，然后通过这个随机数确定标定点。聪明的你也许已经想到了，接近有序的数组会有这个问题，如果有大量重复元素的数组，是不是也有这个问题？

对的，这就是我们要优化的快速排序的第二个问题，这也是影响快速排序效率的一个非常关键的要素。在我们的第一个示意图中可以看出来，如果有非常多的重复元素，那e>=v的那部分的待排序序列就会非常多，从而又导致标定点区分出的两部分待排序数组大小非常不平衡，最后导致快速排序的效率下降，乃至跌至O(n2)。那如何解决这个问题呢？

这就是我们下面要说的一种快速排序的改进：

顾名思义，双路快速排序的要点是从待排序数组的两侧分别进行和标定点的比较，然后保证两侧中待排序的数组均分重复的元素。示意图如下：

双路快速排序很好解决了重复元素导致标定点区分的两部分待排序序列不均衡的情况。但这种改进还是有一些不完美，哪里不完美呢？

您仔细想想，这个时候，那些等于v的元素是均分在两个待排序序列中的，这就导致下一次快速排序时还要对这些等于v的元素进行排序。那我们可不可以把等于v的那些元素单独组成一个分区呢？这样在有很多重复的待排序数组中，每次通过标定点区分出的两部分待排序数组，就会少很多元素，从而又能够一定程度上提高快速排序的效率。

当然可以，这就是我们要说的对快速排序的第三个改进：

三路快速排序是在双路快速排序的基础之上，把等于v的那部分元素单独组成一个分区，进行完一次快速排序之后，只对小于v和大于v的两部分待排序数组进行递归快速排序。示意图如下：

三路快速排序基本上是快速排序改进之后，最优化的一种实现方案。因为在普通的序列中，虽然可能这种优化的排序方法增加了一定的计算量，但算法复杂度还是在一个数量级之内的，而对于数组接近有序或者是数组中有大量重复元素的时候，三路快速排序的效率就会非常高。所以在系统级别的排序中，三路排序往往都是最佳选择。

我是徐建航， 这是我写的第51篇文章，欢迎你加入007社群，七天写一篇，一起写七年，七年之后一起去南极。