为什么说快速排序是最快排序算法？

2019-10-27 06:40发布

站内文章 / 后端开发

363 0

基本思想

2.1 快速排序的一般过程

快速排序的一般过程是，随机选取数组中的一个值，作为比较标准，一般称之为枢值(Pivot)。然后把整个数组中小于枢值的数据分到一个组，把大于枢值的数据分到另一个组，等于枢值的数据分到哪个组都可以。分成两组后，自然不会用其他排序对小数组进行排序，而是重复以上的步骤，把小的数组再细分。这样整个数组就由1个数组变成2个数组，再变成4个数组，再变成8个数组，到最后分无可分，简单比较一下，整个数组就变得有序了。

简单描述一下：

选择枢值。也就是选择一个数据作为标杆。选择枢值其实是最重要的一个步骤，比较推荐的方法是，选择数组中第一个、中间以及最后一个数据中的中值。
分组操作。把大于枢值的数据放到枢值右边，把小于枢值的数据放到左边。与枢值相等的数据放到哪边无所谓。
递归。对左右两边的数据进行枢值选取和分组操作。递归的停止条件是细分数组数据个数为0或者1。

来看一张稍微复杂一点的图，图中阴影部分的数据就是各个阶段的枢值。

From Wikipedia

枢值选取方式和分组操作是快速排序的核心，常见的有两种方案，即Lomuto和Hoare分组方案。

2.2 Lomuto分组方案

最简单也是最常见的分组方式是Lomuto分组方案，该方案直接选取最后一个元素作为枢值，该方案最明显的缺点是，当一个数组已经是有序的或者数组所有数字相同，反而会出现最糟糕的排序情况，即复杂度为O(n²)。

不防看一下1、2、3、4、5这样一个数组。使用该方案首先选择5为枢值，则第一次分组后仅左边有1、2、3、4这四个数字，而右边没有任何数字，第二次选择4为枢值，结果还是一样，这样每次分组都只能使一个数字变得有序，效率自然就退化成O(n²)。

直接上伪码：

2.3 Hoare分组方案

另一个方法则是Hoare的分组方案，通过一定的方法选择一个枢值，一般选择数组中间的值，不妨设数组A首尾元素的下标分别为lo和hi，则枢值

Pivot = A[(lo + hi) / 2]

当然，为了避免整数溢出问题，一般写成

Pivot = A[lo + (hi - lo) / 2]

关于整数溢出有机会再说。其思想是从数组左右两端开始，从左端向右侧查找第一个大于等于枢值的数据，记录下标为i，从右端向左侧查找第一个小于等于枢值的数据，记录下标为j，然后交换A[i]和A[j]。然后继续如上操作，直到i大于等于j结束，这样原来的数组就分成了两个数组，左侧的均小于枢值，右侧均大于等于枢值，然后再对子数组重复如上的操作。

以数组4、5、3、2、1为例：

选取3为枢值，找到左端数据4大于枢值，右端数据1小于枢值，交换数据得到1、5、3、2、4，
继续向内扫描数据，发现需要交换5和2，这样得到1、2、3、4、5
继续对两个子数组1、5和4、5进行如上操作，发现已经完成排序。

老规矩，上伪码：

2.4 其他分组方案

此外，《算法导论》中还提到随机化，也就是随机的选择枢值，可能你不信，很多排序算法都会用到随机化这个概念，因为很多时候，随机化带来的结果往往意想不到的好。这里暂不赘述，有机会单独讲一讲。Sedgewick推荐一种选取枢值的方法被称为三数取中(median-of-three)，即从数组第一个数据、正中间数据以及最后一个数据中选取中间值为枢值。三数取中的升级版本也被称为ninther，不妨定义函数median-of-three (Mo3)：

Mo3(A) = median(A[1], A[n/2], A[n])

ninther(a) = median(Mo3(first ⅓ of a), Mo3(middle ⅓ of a), Mo3(final ⅓ of a))

即取数组前三分之一找出中值，然后取数组中间三分之一找出中值，再取数组最后三分之一找出中值，最后选择这三个中值中的中值。

复杂度

3.1 时间复杂度

快速排序对于已经有序的数组或者所有数据都相等的数组排序的复杂度是O(n²)，这种情况有多种方法优化，比如，可以尝试把数据分成3组，即大于枢值为一组，等于枢值为一组，小于枢值为一组，其原因很好理解，这里就不赘述了。也可以评估数据的个数，对于较少的数据，完全不需要使用快速排序，可以直接使用选择排序或者希尔排序。

快速排序的平均复杂度是O(n*log n)，除了快速排序还有归并排序和堆排序的复杂度也是O(n*log n)，那为什么一般都说快速排序是最快的排序算法呢？其实读过我之前关于复杂度的文章的读者应该都知道，对于复杂度为O(C*n*log n)的算法，其复杂度都是O(n*log n)，这里的C为常数。快速排序之所以最快，主要是因为它的常数C比较小，在具体应用中，快速排序的表现也往往比较好的。

3.2 空间复杂度

快速排序的空间复杂度和具体的实现方式有关。Sedgewick描述的一种方案，针对就地(in-place)排序实现，首先通过递归对元素最少的分组进行排序，最多需要O(log n)的空间，然后使用尾部递归或者迭代的方式对另一部分分组数据排序，这就避免了把这部分排序操作添加到调用栈，也就是说，这样可以限制调用栈的深度不会超过O(log n)，也就保证了空间复杂度为O(log n)。其他一些非就地(not-in-place)排序实现，空间复杂度则为O(n)。

其实也可以换个角度理解快速排序的空间复杂度。快速排序的递归过程可以用二叉树来表示，则调用栈的层次和二叉树的深度保持一致，那么最好的情况树的深度为O(log n)，即此时空间复杂度为O(log n)。而最坏的情况发生在二叉树退化成单链，深度为O(n)，空间复杂度也就是O(n)了。