【排序】快速排序算法

特别说明：

对于算法，重在理解其思想、解决问题的方法，思路。因此，以下内容全都假定待排序序列的存储结构为：顺序存储结构。

快速排序介绍

快速排序算法相较于插入、冒泡、选择排序来说而言要稍微复杂些。其主要用的是分治思想，将问题划分为更小的子问题来解决。因此，快速排序的思想其实很简单。在(目前的)时间复杂度为 $O(knlg^{n})$ 的排序算法中，快速排序的系数是最小的。因此，在平均情况下，快速排序算法是被认为最快的一种排序算法(要不怎么称之为快速排序呢？)。

快速排序算法在大数据量情况下，实践证明在平均情况下的排序算法能相较于其他排序算法更好地工作、排序更为高效，且其平均情况下的时间复杂度为 $O(nlg^{n})$ ，如果在数据规模较小的情况下，反而不一定能胜过其他的简单排序算法。而且由于使用分治递归的思想，其空间复杂度也要求较高。

快速排序思想

如前所述，快速主要应用分治递归思想，将原始问题逐渐划分为更小规模的子问题解决。假设待排序数据为 $R_{1..n}$ ，则算法的思想描述如下：

01.设置标记 $l$ = 0; $h$ = n - 1;

// 说明：下面 02、03、04 是一次完整的划分处理

02.如果 $l$ $<$ $h$ ，则执行后面的 03 步骤；否则退出该层递归；

03.在序列 $R_{l..h}$ 中，选定一个元素 $x$ (其实该元素称为主元元素)；

04.将序列 $R_{l..h}$ 划分为两个子序列 $R_{l..m}$ 与 $R_{m + 1..h}$ ，使得满足如下条件：

对于任何 $R_{i}$ $<$ $x$ ( $l$ $\leqslant$ $i$ $\leqslant$ $m$ ) 且对于任何 $R_{j}$ $\geqslant$ $x$ ( $m + 1$ $\leqslant$ $j$ $\leqslant$ $h$ )；

注意：其实划分完成后， $x$ 元素将处在 $m$ 索引处。即： $R_{m}$ = $x$ ；

05.将 $m$ 位置索引返回；

06.设置 $h$ = $m$ ，跳转并执行 02 步骤；

07.设置 $l$ = $m$ + 1，跳转并执行 02 步骤；

以上便是快速排序算法的思想，其实真的很简单，就是不断地拆分，将较大规模的待排序序列分成规模更小一些的两段子序列。随着拆分的不断进行，最终都会被拆分到只有一个或0个元素的两个子序列，对于这两种子序列，它们都是有序的，因此最终实现原始数据的正确排序。

根据以上思想描述，有两个问题需要解决：

a) 划分子序列的终止条件是什么？

由上述描述明显可知，只要 $l$ = $h$ 时，则就不需要再划分了。(这边其实是不可能出现 $l$ $>$ $h$ 的情况的，不明白的自己好好想想)

b) 如果选定第 03 步骤的元素？

很明显，最简单的办法就是在序列 $R_{l..h}$ 中，随机选择一个即可。比如：都是直接取第一个元素 $R_{l}$ ，又或都是直接取最后一个元素 $R_{h}$ 。其实快速排序对该主元元素的选取，并没有严格的要求，但这种选取方案一般不被推荐。取个例子来说明为什么一般不使用该方案。此处假设我们每次都是选取 $R_{l}$ (其实选 $R_{h}$ 是一样的效果) 元素作为主元元素，并且待排序序列已经是有序的情况下，则每次执行完 04 步骤后，发现划分的两个子序列永远都是一个为0个元素，一个为 $h$ - $l$ - 1 个元素。出现这种情况的话，则快速度排序的效率是非常低的，其时间复杂度退化到 $O(n^{2})$ ，即已经退化到了像冒泡排序的效率了，甚至还比不过冒泡排序(因为冒泡排序对已经有序的序列只需要 $O(n)$ 即可完成排序工作)。

因此，在选取主元元素时，多会采用三数取中法来确定主元元素。即：取 $R_{l}$ 、 $O(\left \lfloor (l + h)/2 \right \rfloor)$ 、 $R_{h}$ ，三个元素中的中间那个元素作为主元元素。经过实践证明，该方法确定主元元素后，一般都能很好的避免快速排序最坏情况的出现。其平均时间复杂度也都能靠近 $O(nlg^{n})$ 。

对于上面第 04 步骤的处理，则方法也是有多种，只要执行完该步骤后，能满足其后的条件即可。下面的编码实现中，就描述了3种实现方法来划分序列，具体可参阅具体编码。

快速排序算法编码实现

下面是C++实现版本的快速排序算法编码，仅供参考。以下面算法中，用了三种不同的划分序列的方法(即：上面算法思想问题的第 03、04 两个步骤的具体实现)。

  1 // 
  2 // summary     : 交换两个元素.
  3 // in param    : seqlist 序列列表
  4 // in param    : nIndexA 节点A索引.值范围 [0, nLen)
  5 // in param    : nIndexB 节点A索引.值范围 [0, nLen)
  6 // return      : --
  7 // !!!note       : 01.以下实现均假设一切输入数据都合法.即:内部不对参数全法性进行校验,默认它们全都合法有效.
  8 void swapTwoItems(int seqlist[/*nLen*/], const int nIndexA, const int nIndexB) {
  9     const auto nTemp = seqlist[nIndexA];
 10     seqlist[nIndexA] = seqlist[nIndexB];
 11     seqlist[nIndexB] = nTemp;
 12 }
 13 
 14 // 
 15 // summary     : 快排确定主元元素(索引)
 16 // in param    : seqlist 待排序列表.同时也是排完序列表.
 17 // in param    : nLowBound 当前趟的下界.值 [0, nLen)
 18 // in param    : nHighBound 当前趟的上界.值 [0, nLen)
 19 // out param   : --
 20 // return      : 当前趟主元元素的索引.值 [0, nLen)
 21 // !!!note       : 01.以下实现均假设一切输入数据都合法.即:内部不对参数全法性进行校验,默认它们全都合法有效.
 22 //               02.调用该接口,则必定要求 nLowBound < nHgihBound.
 23 int getQuickSortPivotIndex(int seqlist[/*nLen*/], const int nLowBound, const int nHighBound) {
 24     auto nPivot = (nLowBound + nHighBound) >> 1;
 25     if (seqlist[nPivot] < seqlist[nLowBound]) {
 26         if (seqlist[nPivot] < seqlist[nHighBound]) {
 27             nPivot = seqlist[nLowBound] < seqlist[nHighBound] ? nLowBound : nHighBound;
 28         }
 29     } else {
 30         if (seqlist[nPivot] > seqlist[nHighBound]) {
 31             nPivot = seqlist[nLowBound] > seqlist[nHighBound] ? nLowBound : nHighBound;
 32         }
 33     }
 34     return nPivot;
 35 }
 36 
 37 // 
 38 // summary     : 快速排序的Partition函数.
 39 // in param    : seqlist 待排序列表.同时也是排完序列表.
 40 // in param    : nLowBound 该趟处理的下界.值 [0, nLen)
 41 // in param    : nHighBound 该趟处理的上界.值 [0, nLen)
 42 // out param   : --
 43 // return      : 当前该趟处理后的分隔元素位置.即:主元元素位置.值 [0, nLen)
 44 // !!!note       : 01.以下实现均假设一切输入数据都合法.即:内部不对参数全法性进行校验,默认它们全都合法有效.
 45 //               02.调用该接口,则必定要求 nLowBound < nHgihBound.
 46 int quick_partition(int seqlist[/*nLen*/], const int nLowBound, const int nHighBound) {
 47     auto nPivot = getQuickSortPivotIndex(seqlist, nLowBound, nHighBound);
 48     if (nPivot != nHighBound) {
 49         swapTwoItems(seqlist, nPivot, nHighBound);
 50     }
 51 
 52     auto nIndex = nLowBound;
 53     auto nTemp = seqlist[nHighBound];
 54     auto nLower = nLowBound - 1;
 55     for (; nIndex < nHighBound; ++nIndex) {
 56         if (seqlist[nIndex] < nTemp) {
 57             swapTwoItems(seqlist, ++nLower, nIndex);
 58         }
 59     }
 60     swapTwoItems(seqlist, ++nLower, nIndex);
 61     return nLower;
 62 }
 63 
 64 int quick_partition_2(int seqlist[/*nLen*/], const int nLowBound, const int nHighBound) {
 65     auto nPivot = getQuickSortPivotIndex(seqlist, nLowBound, nHighBound);
 66     if (nPivot != nHighBound) {
 67         swapTwoItems(seqlist, nPivot, nHighBound);
 68         nPivot = nHighBound;
 69     }
 70 
 71     auto nLower  = nLowBound;
 72     auto nHigher = nHighBound;
 73     while (nLower < nHigher) {
 74         while (nLower != nPivot && seqlist[nLower] < seqlist[nPivot]) ++nLower;
 75         if (nLower != nPivot) {
 76             swapTwoItems(seqlist, nLower, nPivot);
 77             nPivot = nLower;
 78         }
 79         while (nHigher != nPivot && seqlist[nHigher] >= seqlist[nPivot]) --nHigher;
 80         if (nHigher != nPivot) {
 81             swapTwoItems(seqlist, nHigher, nPivot);
 82             nPivot = nHigher;
 83         }
 84     }
 85 
 86     return nPivot;
 87 }
 88 
 89 int quick_partition_3(int seqlist[/*nLen*/], const int nLowBound, const int nHighBound) {
 90     auto nPivot = getQuickSortPivotIndex(seqlist, nLowBound, nHighBound);
 91 
 92     auto nLower = nLowBound;
 93     auto nHigher = nHighBound;
 94     while (nLower < nHigher) {
 95         while (nLower < nHigher && seqlist[nLower] < seqlist[nPivot]) ++nLower;
 96         swapTwoItems(seqlist, nLower, nPivot);
 97         nPivot = nLower;
 98         while (nLower < nHigher && seqlist[nHigher] >= seqlist[nPivot]) --nHigher;
 99         swapTwoItems(seqlist, nPivot, nHigher);
100         nPivot = nHigher;
101     }
102 
103     return nPivot;
104 }
105 
106 // 
107 // summary     : 快排递归实现.
108 // in param    : seqlist 待排序列表.同时也是排完序列表.
109 // in param    : nLow 该趟处理的下界.值 [0, nLen)
110 // in param    : nHigh 该趟处理的上界.值 [0, nLen)
111 // out param   : --
112 // return      : 当前该趟处理后的分隔元素位置.即:主元元素位置.值 [0, nLen)
113 // !!!note       : 01.以下实现均假设一切输入数据都合法.即:内部不对参数全法性进行校验,默认它们全都合法有效.
114 //               02.调用该接口,则必定要求 nLow < nHigh.
115 void q_sort(int seqlist[/*nLen*/], const int nLow, const int nHigh) {
116     if (nLow < nHigh) {
117         //auto pivot = quick_partition(seqlist, nLow, nHigh);
118         //auto pivot = quick_partition_2(seqlist, nLow, nHigh);
119         auto pivot = quick_partition_3(seqlist, nLow, nHigh);
120         q_sort(seqlist, nLow, pivot - 1);
121         q_sort(seqlist, pivot + 1, nHigh);
122     }
123 }
124 
125 // 
126 // summary     : 快排对外接口.(方便外部使用.其实效果与直接使用 q_sort() 接口是一样的)
127 // in param    : seqlist 待排序列表.同时也是排完序列表.
128 // in param    : nLen 列表长度
129 // out param   : --
130 // return      : --
131 // !!!note       : 01.以下实现均假设一切输入数据都合法.即:内部不对参数全法性进行校验,默认它们全都合法有效.
132 //               02.排序开始前 seqlist 是无序的,排序结束后 seqlist 是有序的.
133 void quick_sort(int seqlist[/*nLen*/], const int nLen) {
134     q_sort(seqlist, 0, nLen - 1);
135 }

快速排序算法C++编码实现参考

快速排序算法分析

由前面的算法思想可知，快排其实不难理解，但真要实现起来，也是要挺多编码的。在算法思想部分已说明，如果待排序序列是已经有序的情况下，并且主元元素的选取使用最直接的头或尾元素时，则算法的效率是降至最低效。此时，快速排序的时间复杂度为多少？

最坏情况下的时间复杂度分析

假设待排序序列有 $n$ 个元素，最坏情况下，每次划分的两个子序列的元素个数将分别为 0 个与 $n$ - 1 个元素。因此，要想将所有 $n$ 个元素排序完成，将需要执行 $n$ - 1 次拆分 (因为 0 个元素的那个子序列永远都不需要再划分了，这边的 $n$ 次拆分都是针对非 0 个元素的那个子序列)，而 04 步骤的比较与数据移动操作都是在常数时间内完成，设为该操作数据时间为 $c$ (注意：每次执行 04 步骤时， $c$ 的值可能会有所不同，但都是一个个常数。因此，此处所有 $n$ 次拆分中的最大的那个常量即可)。所以最坏情况下的操作耗时为： $T(n)$ = $c$ $n$ + $c$ ( $n$ - 1) + $c$ ( $n$ - 2) + ... + $c$ 2 + $c$ 1 = $c(\frac{n(n + 1)}{2})$ 。因此最坏情况下时间复杂度为 $O(n^{2})$ 。

最佳情况下的时间复杂度分析

由上述算法思想描述可知，如果每次划分都能平分序列，即：每次划分后的两个子序列 $R_{l..m}$ 与 $R_{m + 1..h}$ 中的元素个数都是 $R_{l..h}$ 的一半个数时(当然其中有一个可能是会少1个，但这不根本不影响)，此种情况下，算法执行的时间复杂度将最多只需要 ${log_{2}}^{n}$ 次拆分处理即可，且每次处理的耗时为 $T(n) = 2T(\frac{n}{2}) + cn$ ，该递归式的解为 $T(n)$ = $O(nlg^{n})$ 。因此，在最佳情况下，快速排序算法的时间复杂度是 $O(nlg^{n})$ 。

是不是有同学不解该递归式的解是如何而来的？这边给大家简要说明一下：上述递归式其实就是一棵递归树，树的每个节点下的两个子节点都分别是该节点的一半。因此，树的高度最高只会有 ${log_{2}}^{n}$ ，而最高节点(即：树根节点)的解为 $c$ $n$ ，其下两个子节点的解为 $c\frac{n}{2}$ ，再下一层的每个节点的解为 $c\frac{n}{4}$ ，再下一层 $c\frac{n}{8}$ ，...， $c(\frac{n}{2^{{log_{2}}^{n} - 1}})$ ， $c(\frac{n}{2^{{log_{2}}^{n}}})$ 。故 $T(n) = {log_{2}}^{n}\times cn(\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + ... + \frac{1}{n})$ = $cn{log_{2}}^{n}$ 。所以 $T(n) = O(nlgn)$ 。

其实在所有 $O(cnlgn)$ 时间复杂度的排序算法中，快速排序的系数是最小的。并且在平均情况下，性能也都是接近最佳情况下。或许还有同学会问这边只是分析了它的最佳情况，而最佳情况下的序列划分是对称划分(即：平分的)，在实际中并不能够一定做到这点。的确如此，假如划分后的两个子序列中的元素个数比例不是为 5 : 5，设为 $x$ : $y$ (不妨进一步假设为 2 : 8 或 3 : 7 甚至 9 : 1 其实都一样)，对于上面递归式的解都是为 $cn{log_{2}}^{n}$ 。当然不难想象，如果 $x$ ， $y$ 越不对称，算法的效率肯定会越来越肯定也是越为越低，比如：从头到尾一直都是 9 : 1 划分，那明显的递归解的递归树的深度将越来越深。但是在选取适当的主元元素后，实践证明，算法的平均时间复杂度是比较接近最佳时间复杂度的。

主元元素的选取

前面已经讲过，一般情况下，主元元采用三数取中法即可，因为三数取中法一般情况下是能大大改善快速排序算法的性能的。在 STL 中，也是采用该方法确定主元元素。当然，如果有发现其他更好的取主元法的话，亦是可以采纳的。建议有兴趣的人，可查阅相关文档、资料。

空间复杂度分析

由前面的最坏情况与最佳情况下的时间复杂度分析可知，在最好情况下算法的递归深度是 ${log_{2}}^{n}$ ，此时需要的栈深度将是 ${log_{2}}^{n}$ + 1，因此辅助空间为 ${log_{2}}^{n}$ + 1。而最坏情况下，需要递归深度将达到最深 $n$ ，因此辅助空间将为 $n$ 。所以快速排序的空间复杂度为 $O({log_{2}}^{n})$ ~ $O(n)$ 。

不过，该空间复杂度是可以优化的。有兴趣的话，具体可查阅相关资料。

结尾

快速排序算法在适合对大规模数据情况下，效率相对其他排序算法来说，平均速度算是最快的。在数据规模中、小时，其效率反而不一定会比其他的一些排序算法来有高效，特别在数据基本有序的情况下，效率反而还不如一些简单的排序算法，比如：插入排序算法等。另外，快速排序算法是不稳定排序算法。在 STL 中的 sort 算法 (其实应该称之为 introsort 算法)，就用了快速排序算法，有兴趣者也可自行查阅相关资料。