偶然看到了一篇讲快排文章, 发现那里有点小错, 于是自己也想写一篇记录一下.

基本思想

快排的基本思想就是选取一个 pivot, 该 pivot 用作比较的基准, 将整个数组分成两个部分, 一个部分全部小于该 pivot, 另一部分全部大于该 pivot. 这样对两个子数组再次进行排序操作, 就完成了对整个数组的排序.

理论复杂度分析

在这里我们不关心这个 pivot 究竟是怎么选出来的, 直接认为在至多常数的时间内可以得到该 pivot, 而比较该 pivot 和各元素得到子数组至少是\( O(n) \)的, 因为至少所有元素都需要比较一次. 加上对两个子数组的递归调用开销, 整个快速排序对于长度为n的数组的时间复杂度为

\[ T(n) = T(u) + T(v) + O(n), where \ u + v = n - 1 \]

这个式子构成了复杂度分析的基础.

基于比较的排序算法复杂度下界

在正式开始对于快速排序的分析之前, 先介绍一下基于比较的排序算法复杂度下界.

假设有\( n \)个两两不同的数, 任选其中两个, 假设为 \( x_1, x_2 \), 比较大小之后, 假设我们可以确定\( x_1 < x_2 \), 这样全部可能的排列种数就从\( n! \)降到了\( \frac{n!}{2} \). 很直接的分析告诉我们, 全排列中\( x_1 > x_2 \)的和\( x_1 < x_2 \)的数量相同, 因此在比较后可以减少一半的情况. 当然, 在有之前的比较结果的限制下, 减少的比例会低于\( \frac{1}{2} \), 例如, 在之前已知了\( x_1 < x_2 \)的前提下, 如果再经过比较确定\( x_1 < x_3 \), 此时能从当前结果中排除的比例为\(\frac{1}{3}\). 无论如何, 每一次比较至多使得剩余的可能排列数目减少\( \frac{1}{2} \). 因此获得唯一的排列数(获得排序结果)至少需要的比较次数为

\[ \log(n!) \]

根据 stirling 公式 \( n! \sim \sqrt{2 \pi n} ( \frac{n}{e} )^n \), 上述表达式取主项之后得到\( n\log(n) \). 因此基于比较的排序算法的时间复杂度下界为

\[ \Omega ( n \log (n) ) \]

需要注意这是针对基于比较的排序而言的, 不通过比较实现的排序算法(如桶排序)是不受这个限制的. 当然了, 线性排序算法都有其局限性, 真正能广泛使用的排序算法还是基于比较的.

快速排序的最差情况复杂度

最差的情况, 就是当 pivot 总是取到了当前数组的最大值或最小值, 经过比较之后得到的两个子数组一个是空数组, 另一个是包含了 \( n - 1 \)个元素的数组(不仅仅是当前这一次这样差, 而是递归调用中的每一次拆分都这样差). 这样的情况下, 复杂度表达式退化为

\[
\begin{aligned}
T(n) &= T(n-1) + O(n) \\
&\le T(n-1) + Cn \\
&= T(n-k) + C\sum_{i=n-k+1}^{n} i \\
&= T(1) + O(n^2) \\
&= O(1) + O(n^2) \\
&= O(n^2)
\end{aligned}
\]

快速排序的平均复杂度

对解递归式稍微有点经验就很容易发现, 上面的原始式子, 如果 \(u, v\)能尽可能相等, 就可以得到最优的情况. 这里我们来考虑平均情况. 无论使用什么选取 pivot 的方法, 由于输入数据的任意性, 仍然可能选取到任何一个值. 因此平均意义下的复杂度为

\[
T(n) = \frac{1}{n} \sum_{i=0}^{n-1} T(i) + T(n-1-i) + O(n)
\]

为了简便, 我们不用\( T(n) \)表示实际的时间复杂度, 而用来表示时间复杂度的上界, 这样可以避免上式的\( O \)干扰分析

\[ T(n) = \frac{1}{n} \sum_{i=0}^{n-1} T(i) + T(n-1-i) + Cn \]

这样我们得到

\[
\begin{aligned}
nT(n) &= \sum_{i=0}^{n-1} [T(i) + T(n-1-i) + Cn] \\
(n-1)T(n-1) &= \sum_{i=0}^{n-2} [T(i) + T(n-2-i) + C(n-1)] \\
\end{aligned}
\]

做差得到

\[
\begin{aligned}
nT(n) - (n+1)T(n-1) &= C(2n-1) \\
\frac{T(n)}{n+1} - \frac{T(n-1)}{n} &= C\frac{2n-1}{n(n+1)} \\
&= C(\frac{3}{n+1} - \frac{1}{n})
\end{aligned}
\]

进一步求和, 得到了

\[
\frac{T(n)}{n+1} = C' \ln (n) + C''
\]

上式中用到了调和级数的渐进估计

\[ \sum_{i=1}^{n} \frac{1}{i} - \ln (n) \rightarrow constant \]

因此

\[ T(n) = O(n \ln (n) ) \]

实现

思路

这里就直接简单地选取数组的第一个元素作为 pivot, 然后从第二个元素开始, 放置小于该元素的项, 使用两个指标, 一个表示当前比较到数组中的哪一个数, 另一个表示已经比较过的部分里面, 存放的大于 pivot 和小于 pivot 的分界点.

C

void swapC(int* a, int* b) {
        int tmp = *a;
        *a = *b;
        *b = tmp;
}

void quickSortC(int a[], int _begin, int _end) {
        if (_begin >= _end) {
                return;
        }
        int last = _begin;
        for (int i = _begin; i < _end; ++i) {
                if (a[i] < a[_begin]) {
                        swapC(&a[++last], &a[i]);
                }
        }
        swapC(&a[_begin], &a[last]);
        quickSortC(a, _begin, last);
        quickSortC(a, last + 1, _end);
}

C++

template<class _Iterator>
void quickSortCpp(_Iterator begin, _Iterator end) {
        if (begin >= end) {
                return;
        }
        auto last = begin;
        for (auto it = begin; it < end; ++it) {
                if (*it < *begin) {
                        iter_swap(it, ++last);
                }
        }
        iter_swap(last, begin);
        quickSortCpp(begin, last);
        quickSortCpp(last + 1, end);
}

测试

int main() {
        const int len = 1000;
        const int round = 10000;
        int origin[len], test[len],test2[len], check[len];
        for (int i = 0; i < len; ++i) {
                test[i] = test2[i] = check[i] = origin[i] = rand();
        }
        sort(check, check + len);
        quickSortC(test, 0, len);
        quickSortCpp(test2, test2 + len);
        bool flag = true;
        for (int i = 0; i < len && flag; ++i) {
                flag = check[i] == test[i] && check[i] == test2[i];
        }
        if (flag) {
                cout << "Passed" << endl;
        }
        return 0;
}

简单说说 std::sort

STL里面的 sort, 基本上是快排, 但是它是不会退化的. 在函数参数里面设置一个迭代层数, 初始值设置在\( C\log_{2} (n) \), 每次递归调用将这个值减一, 如果到了0排序还没有结束, 表明快速排序很有可能遇到了退化的情况, 于是开始进行归并排序. 当然了这只是大概思路, STL里面还有很多细节的优化. 总之在sort这个领域, 想要写出比 std::sort 还快的排序基本上是不可能了.