P1177【模板】排序题解

__Allen_123__ · 2023-05-03 15:24:44 · 题解

本题解专门讲述快速排序，如果想了解其他做法请移步。

对于一些评论的回复：

虽然 C++ 确实提供了 sort 这个可以大幅简化代码的函数，但是如果想要理解排序方式的内部逻辑，请不要在模板题上耍小聪明（除非想要练习 sort）。其他题 sort 想怎么用就怎么用。
如果使用本题解中提供的代码无法通过此题，请设置随机种子，例如在主函数最前面加上 srand(time(0))。

2023.12.15：修改了一些笔误和可能引起误解的内容。

2024.8.16：优化了一些表述，使描述更加严谨。

2024.11.26：修改了一些 typo 和小错误，增加后记。

2025.8.10：修改关于时间复杂度的表述，修改后记。

2025.10.25：根据相关题解规范进行格式调整；删繁就简，增删小部分内容。

快速排序是 OI 中常用的算法。这篇题解/笔记将会详细地讲解快速排序的原理、实现过程，也会拓展 STL sort 函数的使用和快排复杂度及其证明。

快速排序简介

本部分讲述的是常用的三路快速排序。如果想了解快速排序的更多变种实现方式可以在 OI Wiki 中了解。

我们设待排序的序列为一个长度为 n 的序列 a。快速排序的具体原理如下：

首先，在 a 中随机选择一个数 x（随机选择的原因见【时空复杂度及证明】一节），之后我们进行如下操作：

如果 n=0 或 n=1，此时根本无需排序，直接退出；
定义三个新的序列 b, c, d；
遍历整个序列 a，将比 x 小的放在 b 内，比 x 大的放在 d 内，和 x 相等的放在 c 内；
将 b, d 按如上过程继续排序。序列 c 中的数由于都相等所以不必排序。

例如，我们定义一个未排序序列 a=\{3, 2, 4, 1\}。

我们从序列中选择第一个数 a_1=3，根据上面的过程可知，b=\{2, 1\}, c=\{3\}, d=\{4\}。

此时因为 c, d 长度已经为 1，所以不必再排序；而同理，在序列 b 中，我们可以将两个数分为两个序列（相当于把它们交换位置），最终就可以完成排序。排序结果为 a=\{1, 2, 3, 4\}。

快速排序的实现

提供两种方式。推荐在练习模板题时使用第一种，实际应用时使用第二种（更为方便）。

自定义函数

首先，我们看完如上所示的实现方法与过程后，可以发现：实际上每一次的排序之后都会通过调用本身来继续排序，这明显运用了递归的思想。

递归是快速排序的主要思想，通过递归，我们将一个完整的序列经过不断的分解来变成很多小序列，直到只有一个或没有数为止。快速排序就是在不断的递归和分解当中来慢慢实现与完成排序。

这里提供这个函数的参考代码：

// 注：四个数组的下标均从 0 开始。
// 请在主函数内设置随机种子，例如 srand(time(0))，否则可能会超时。
int randint(int l, int r){ // 生成在 [l, r] 之间的随机数
    return rand() % (r - l + 1) + l;
}
void qsort(int l, int r){ // l 为左端点，r 为右端点
    if(l >= r){ // 如果长度为 0 或 1 就返回
        return;
    }
    int num = randint(l, r), ind1 = 0, ind2 = 0, ind3 = 0; // 随机选择一个数，并定义三个作为下标的变量来记录长度、存放数据
    for(int i = l;i <= r;i++){ // 将 a 中的数分别分到 b, c, d（如上所述）
        if(a[i] < a[num]){
            b[ind1++] = a[i];
        }
        else if(a[i] == a[num]){
            c[ind2++] = a[i];
        }
        else{
            d[ind3++] = a[i];
        }
    }
    for(int i = 0;i < ind1;i++){ // 将 b, c, d 中的数重新放回 a
        a[i + l] = b[i];
    }
    for(int i = 0;i < ind2;i++){
        a[i + ind1 + l] = c[i];
    }
    for(int i = 0;i < ind3;i++){
        a[i + ind1 + ind2 + l] = d[i];
    }
    qsort(l, l + ind1 - 1); // 继续递归，排序原来的 b 和 d
    qsort(l + ind1 + ind2, r);
}

使用 STL sort 函数

（自定义比较方式时，除了下文所述的比较函数仍然有其他方法，感兴趣的读者可以自行了解，此处不再赘述。）

除了如上的快排模板外，我们还可以使用 C++ algorithm 头文件中的 sort 函数来直接完成排序。其使用方法如下：

我们设我们排序的数组为 a，排序区间为 [l, r)（即所有满足 l\le x<r 的整数 x），且从小到大排序。则调用方法为：sort(a + l, a + r)。对于本题，就可以通过 sort(a + 1, a + n + 1) 自动完成排序。如果要使用这个函数，应当包含 <algorithm> 头文件。

如果想从大到小排序，或者以其他方式进行排序，那么我们就应该写一个比较函数来改变排序方法。例如我们想要把一个类型为 int 的数组从大到小排序，应这么定义这个比较函数（假设比较函数名为 cmp）：

bool cmp(int a, int b){
    return a > b;
}

如果是从小到大排序，就用小于号连接两数；如果是从大到小排序，就用大于号连接两数。写完这个函数，我们只需要在调用 sort 函数时在第三个参数写上函数名（例如 sort(a + l, a + r, cmp);）就可以了。这种比较函数的实现方式在结构体中同样适用，只需要把比较对象修改为结构体中对应元素即可。值得一提的是，简单的比较函数（例如 less<int>()、greater<int>()）在 C++ 中是自带的，如果要从大到小排序，就可以直接将第三个参数替换为 greater<int>()。

在排序时，可以通过以上所述的比较函数、重载运算符或者其他方式进行自定义比较，但是在比较方式不明确的情况下就无法排序，导致编译失败。故在排序时需要确认比较方式明确。

正确性证明

算法正确性证明

假设上文中，对于待递归排序的数组 b,d，此算法正确性成立。

因我们把所有大于 x 的数放入 d 数组，小于 x 的数放入 b 数组，故在本轮处理时所有 b 中的元素会小于所有 c 中的元素，并小于所有 d 中的元素，不会产生逆序对（即一个数大于另一个数，下标却靠前的情况，出现这种情况说明排序失败）。

对 |b|,|d|\le 1 的情况，此排序方式处理 a 的结果显然正确；故由归纳假设，此算法在处理 a 时的正确性成立。

故对于一切 a，快速排序的正确性成立。

时空复杂度及证明

快速排序最好情况下的时间复杂度为 \mathrm O(n\log n)，一般情况下的复杂度为 \mathrm O(n\log n)，最坏时间复杂度为 \mathrm O(n^2)。如下是其证明[^1]：

根据快速排序的实现过程和如上代码可以发现，每一次将原序列分为 3 个序列的过程的时间复杂度是 \mathrm O(n)。

对于最优情况，当每一次随机选择的都是序列的中位数时，我们要排序的序列将被分成两个长度相差不多的两个序列。此时时间复杂度的递推式满足 T(n)=2T(\frac{n}{2})+\mathrm O(n)=\mathrm O(n\log n)，所以其最好情况为 \mathrm O(n\log n)；

对于最坏情况，当每一次选择的都是数列的最值（一个典型的例子就是数列已经有序），此时除了与选定的数相等的数以外，剩下的数仍然需要排序（一个序列为空，另一个包含了除与选定的数相等的数以外的所有数），此时的复杂度递推式为 T(n)=T(n-1)+n=\mathrm O(n^2)，所以快速排序的最坏时间复杂度为 \mathrm O(n^2)。通过随机选择，我们能很有效地降低多次选出最值导致复杂度退化的情况，所以带随机化的快速排序复杂度几乎不会达到 \mathrm O(n^2)。在日常训练和比赛中，我们一般都认为快排的时间复杂度为 \mathrm{O}(n\log n)。

篇幅所限，这里无法提供一般情况下快排时间复杂度的证明，感兴趣的读者可以参考《算法导论》第 7 章第 4 节或查看 OI Wiki 中的相关内容。

由于快速排序只需要一个序列来储存序列中的数，所以其空间复杂度为 \mathrm O(n)。如果进行了一些优化可以降低额外的空间复杂度，但不影响总体的空间复杂度。

尾声

排序虽是最基本的普及组算法，但在信息学竞赛中往往有着无比重要的辅助作用，也是在思考题目时的重要思维支柱。未来的路还有很长，无论结局如何，愿大家在 OI 中付出的每一份努力都无愧最初的决定。

祝大家 OI 旅途好运。

[^1]: 部分引用 OI Wiki 中有关快速排序-时间复杂度的内容。

P1177【模板】排序 题解