快速排序

2020-03-31 1438 words 3 minutes

Contents

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

基本思想

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

理论复杂度分析

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

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

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

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

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

根据 Stirling 公式 , 上述表达式取主项之后得到. 因此基于比较的排序算法的时间复杂度下界为

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

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

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

快速排序的平均复杂度

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

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

这样我们得到

做差得到

进一步求和, 得到了

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

因此

实现

思路

这里就直接简单地选取数组的第一个元素作为 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, 基本上是快排, 但是它是不会退化的. 在函数参数里面设置一个迭代层数, 初始值设置在 , 每次递归调用将这个值减一, 如果到了 0 排序还没有结束, 表明快速排序很有可能遇到了退化的情况, 于是开始进行归并排序. 当然了这只是大概思路, STL 里面还有很多细节的优化. 总之在 sort 这个领域, 想要写出比 std::sort 还快的排序基本上是不可能了.