OI-wiki 快速排序全解析从分治原理到三路快排、内省排序与线性第 k 大查找【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki本文是 OI-wiki 基础算法章节中快速排序一文的完整技术展开。全文围绕分治思想 划分Partition这条主线系统讲解快速排序的定义与过程、递归与非递归实现、复杂度分析及其严格证明并进一步覆盖三路快速排序、内省排序两种成熟优化以及基于快排划分思想的线性时间找第 k 大数与中位数中的中位数确定性优化。读者学完后既能徒手写出可应对毒瘤数据的快速排序也能理解std::sort、std::nth_element等标准库函数背后的算法渊源形成从原理到实战的完整闭环。定义快速排序英语Quicksort又称分区交换排序英语partition-exchange sort简称快排是一种被广泛运用的排序算法。在 OI-wiki 的排序算法导论中排序算法被定义为将一组特定的数据按某种顺序进行排列的算法并指出快速排序属于不稳定的排序算法、其平均时间复杂度为 $O(n\log n)$。快速排序正是这一类算法中最具代表性、在工程与竞赛中应用最广的成员之一。基本原理与实现过程快速排序的工作原理是通过分治的方式来将一个数组排序。它分为三个过程将数列划分为两部分要求保证相对大小关系递归到两个子序列中分别进行快速排序不用合并因为此时数列已经完全有序。与归并排序不同快速排序的第一步并不是直接分成前后两个序列而是在分的过程中要保证相对大小关系。具体来说第一步要把数列分成两个部分然后保证前一个子数列中的数都小于后一个子数列中的数。为了保证平均时间复杂度一般是随机选择一个数 $m$ 来当作两个子数列的分界。之后维护一前一后两个指针 $p$ 和 $q$依次考虑当前的数是否放在了应该放的位置前还是后。如果当前的数没放对比如说如果后面的指针 $q$ 遇到了一个比 $m$ 小的数那么可以交换 $p$ 和 $q$ 位置上的数再把 $p$ 向后移一位。当前的数的位置全放对后再移动指针继续处理直到两个指针相遇。需要特别说明的是快速排序没有指定应如何具体实现第一步不论是选择 $m$ 的过程还是划分的过程都有不止一种实现方法。这也是后续三路快排内省排序中位数中的中位数等众多变体得以存在的根本原因。第三步中的序列已经分别有序且第一个序列中的数都小于第二个序列中的数所以直接拼接起来就好了——这正是快速排序分而治之、无需合并的独特之处。代码实现C 非递归实现非递归版本使用一个显式的区间栈Range来模拟递归过程避免了函数调用栈的开销与溢出风险struct Range { int start, end; Range(int s 0, int e 0) { start s, end e; } }; template typename T void quick_sort(T arr[], const int len) { if (len 0) return; Range r[len]; int p 0; r[p] Range(0, len - 1); while (p) { Range range r[--p]; if (range.start range.end) continue; T mid arr[range.end]; int left range.start, right range.end - 1; while (left right) { while (arr[left] mid left right) left; while (arr[right] mid left right) right--; std::swap(arr[left], arr[right]); } if (arr[left] arr[range.end]) std::swap(arr[left], arr[range.end]); else left; r[p] Range(range.start, left - 1); r[p] Range(left 1, range.end); } }该实现以区间右端点元素作为基准mid通过双指针left/right向中间扫描并交换逆序对最终把基准放到正确位置再将左右两个子区间压栈继续处理。C 递归实现递归实现是教科书中最经典的形态先通过Partition找到一个基准元素的最终位置再递归处理其左右两侧template typename T int Partition(T A[], int low, int high) { int pivot A[low]; while (low high) { while (low high pivot A[high]) --high; A[low] A[high]; while (low high A[low] pivot) low; A[high] A[low]; } A[low] pivot; return low; } template typename T void QuickSort(T A[], int low, int high) { if (low high) { int pivot Partition(A, low, high); QuickSort(A, low, pivot - 1); QuickSort(A, pivot 1, high); } } template typename T void QuickSort(T A[], int len) { QuickSort(A, 0, len - 1); }这里的Partition采用挖坑填数的思路以A[low]为基准挖出坑右侧小于等于基准的值填入左侧坑中左侧大于等于基准的值填入右侧坑中最后基准落位并返回其下标。Python 实现Python 版本的递归实现与上述 C 递归版本逻辑一致def quick_sort(alist, first, last): if first last: return mid_value alist[first] low first high last while low high: while low high and alist[high] mid_value: high - 1 alist[low] alist[high] while low high and alist[low] mid_value: low 1 alist[high] alist[low] alist[low] mid_value quick_sort(alist, first, low - 1) quick_sort(alist, low 1, last)注意 Python 版本在左侧扫描时使用严格小于与 C 递归版的略有差异——这体现了两份代码对相等元素归属处理的不同约定但不影响正确性。性质稳定性快速排序是一种不稳定的排序算法。根据排序算法导论中给出的定义稳定性是指相等的元素经过排序之后相对顺序是否发生了改变。由于快排在划分过程中涉及大量跨越式交换std::swap会直接打乱相等元素的相对次序因此它同选择排序、堆排序、希尔排序一样被归入不稳定排序之列。时间复杂度快速排序的最优时间复杂度和平均时间复杂度为 $O(n\log n)$最坏时间复杂度为 $O(n^2)$。最优情况每一次选择的分界值都是序列的中位数此时算法时间复杂度满足的递推式为 $T(n) 2T(\dfrac{n}{2}) \Theta(n)$由主定理可得 $T(n) \Theta(n\log n)$最坏情况每一次选择的分界值都是序列的最值例如对已有序序列反复取端点元素作基准此时递推式为 $T(n) T(n - 1) \Theta(n)$累加可得 $T(n) \Theta(n^2)$平均情况每一次选择的分界值可以看作是等概率随机的期望时间复杂度为 $O(n\log n)$。平均时间复杂度的严格证明引理 1当对 $n$ 个元素的数组进行快速排序时假设在划分元素时总共的比较次数为 $X$则快速排序的时间复杂度是 $O(n X)$。由于在每次划分元素的过程中都会选择一个元素作为分界所以划分元素的过程至多发生 $n$ 次。又由于划分元素的过程中比较的次数和其他基础操作的次数在一个数量级所以总时间复杂度是 $O(n X)$ 的。设 $a_i$ 为原数组中第 $i$ 小的数定义 $A_{i,j}$ 为 ${ a_i, a_{i1}, \dots, a_j }$$X_{i,j}$ 是一个取值为 $0$ 或者 $1$ 的离散随机变量表示在排序过程中 $a_i$ 是否和 $a_j$ 发生比较。显然每次选取的分界值是不同的而元素只会和分界值比较所以总比较次数$$ \begin{aligned} X \sum \limits _ {i 1} ^ {n - 1} \sum \limits _ {j i 1} ^ n X_{i,j} \end{aligned} $$由期望的线性性$$ \begin{aligned} E[X] E \left[ \sum \limits _ {i 1} ^ {n - 1} \sum \limits _ {j i 1} ^ n X_{i,j} \right] \ \sum \limits _ {i 1} ^ {n - 1} \sum \limits _ {j i 1} ^ n E[X_{i,j}] \ \sum \limits _ {i 1} ^ {n - 1} \sum \limits _ {j i 1} ^ n P(a_i\ \text{和}\ a_j\ \text{比较}) \end{aligned} $$引理 2$a_i$ 和 $a_j$ 比较的充要条件是 $a_i$ 或 $a_j$ 是集合 $A_{i,j}$ 中第一个被选中的分界值。先证必要性即若 $a_i$ 和 $a_j$ 都不是集合 $A_{i,j}$ 中第一个被选中的分界值则 $a_i$ 不和 $a_j$ 比较。若如此则一定存在一个 $x$ 满足 $i x j$使得 $a_x$ 是 $A_{i,j}$ 中第一个被选中的分界值。在以 $a_x$ 为分界值的划分中$a_i$ 和 $a_j$ 被划分到数组的两个不同的子序列中所以之后 $a_i$ 和 $a_j$ 一定不会比较。又因为元素只和分界值比较所以 $a_i$ 和 $a_j$ 在此次划分前和划分中没有比较必要性得证。再证充分性即若 $a_i$ 或 $a_j$ 是集合 $A_{i,j}$ 中第一个被选中的分界值则 $a_i$ 和 $a_j$ 比较。不失一般性地假设 $a_i$ 是集合 $A_{i,j}$ 中第一个被选中的分界值。由于 $A_{i,j}$ 中没有其他数被选为分界值所以 $A_{i,j}$ 中的元素都在数组的同一子序列中。在以 $a_i$ 为分界值的划分中$a_i$ 和当前子序列中所有元素都进行了比较所以 $a_i$ 和 $a_j$ 进行了比较充分性得证。考虑计算 $P(a_i\ \text{和}\ a_j\ \text{比较})$。在 $A_{i,j}$ 中某个元素被选为分界值之前$A_{i,j}$ 中的元素都在数组的同一子序列中所以 $A_{i,j}$ 中每个元素都会被等可能地第一个被选为分界值。由于 $A_{i,j}$ 中有 $j - i 1$ 个元素由引理 2$$ P(a_i \text{和} a_j \text{比较}) P(a_i \text{或} a_j \text{是集合} A_{i,j} \text{中第一个被选中的分界值}) \dfrac{2}{j-i1} $$所以$$ \begin{aligned} E[X] \sum \limits _ {i 1} ^ {n - 1} \sum \limits _ {j i 1} ^ n P(a_i\ \text{和}\ a_j\ \text{比较}) \ \sum \limits _ {i 1} ^ {n - 1} \sum \limits _ {j i 1} ^ n \dfrac{2}{j - i 1} \ \sum \limits _ {i 1} ^ {n - 1} \sum \limits _ {k 2} ^ {n - i 1} \dfrac{2}{k} \ \sum \limits _ {i 1} ^ {n - 1} O(\log n) \ O(n \log n) \end{aligned} $$由此快速排序的期望时间复杂度为 $O(n \log n)$。实践中的表现在实践中几乎不可能达到最坏情况而快速排序的内存访问遵循局部性原理所以多数情况下快速排序的表现大幅优于堆排序等其他复杂度为 $O(n\log n)$ 的排序算法。堆排序虽然最坏情况下也有 $O(n\log n)$ 的保证但其对数组的访问是跳跃式的父子节点间跨度大缓存命中率远低于快速排序的线性扫描模式。优化朴素优化思想如果仅按照上文所述的基本思想来实现快速排序或者是直接照抄模板的话那大概率是通不过P1177【模板】快速排序这道模板题的——因为存在毒瘤数据能够把朴素的快速排序卡成 $O(n^2)$。所以需要对朴素快速排序思想加以优化。较为常见的优化思路有以下三种通过三数取中即选取第一个、最后一个以及中间的元素中的中位数的方法来选择两个子序列的分界元素即比较基准这样可以避免极端数据如升序序列或降序序列带来的退化当序列较短时使用插入排序的效率更高插入排序在数列几乎有序时最优时间复杂度可达 $O(n)$非常适合作为小规模序列的收尾手段每趟排序后将与分界元素相等的元素聚集在分界元素周围这样可以避免极端数据如序列中大部分元素都相等带来的退化。三路快速排序定义三路快速排序英语3-way Radix Quicksort是快速排序和基数排序的混合。它的算法思想基于荷兰国旗问题Dutch national flag problem的解法。过程与原始的快速排序不同三路快速排序在随机选取分界点 $m$ 后将待排数列划分为三个部分小于 $m$、等于 $m$ 以及大于 $m$。这样做即实现了将与分界元素相等的元素聚集在分界元素周围这一效果。借助基数排序中按关键字分组、对同组元素继续递归的思想三路快排把等于基准的整块元素一次排定无需再参与后续划分。性质三路快速排序在处理含有多个重复值的数组时效率远高于原始快速排序。其最佳时间复杂度为 $O(n)$——当所有元素都相等时一趟划分即可完成全部排序。实现三路快速排序实现起来非常简单下面给出了一种三路快排的 C 实现// 模板的 T 参数表示元素的类型此类型需要定义小于运算 template typename T // arr 为需要被排序的数组len 为数组长度 void quick_sort(T arr[], const int len) { if (len 1) return; // 随机选择基准pivot const T pivot arr[rand() % len]; // i当前操作的元素下标 // arr[0, j)存储小于 pivot 的元素 // arr[k, len)存储大于 pivot 的元素 int i 0, j 0, k len; // 完成一趟三路快排将序列分为 // 小于 pivot 的元素 | 等于 pivot 的元素 | 大于 pivot 的元素 while (i k) { if (arr[i] pivot) swap(arr[i], arr[j]); else if (pivot arr[i]) swap(arr[i], arr[--k]); else i; } // 递归完成对于两个子序列的快速排序 quick_sort(arr, j); quick_sort(arr k, len - k); }该实现的指针语义十分清晰区间[0, j)存放小于pivot的元素[k, len)存放大于pivot的元素中间部分自然是等于pivot的元素。小于时把元素交换到前面并同时推进i、j大于时把元素交换到后面并收缩k相等时只需推进i。一趟结束后等于基准的整段元素天然聚集在中部无需再参与递归。Python 版本实现如下def quick_sort(arr, l, r): if l r: return random_index random.randint(l, r) pivot arr[random_index] arr[l], arr[random_index] arr[random_index], arr[l] i l 1 j l k r 1 while i k: if arr[i] pivot: arr[i], arr[j 1] arr[j 1], arr[i] j 1 i 1 elif arr[i] pivot: arr[i], arr[k - 1] arr[k - 1], arr[i] k - 1 else: i 1 arr[l], arr[j] arr[j], arr[l] quick_sort(arr, l, j - 1) quick_sort(arr, k, r)Python 版先将随机选出的基准交换到区间左端再沿用同一套三指针扫描逻辑最后把基准归位到分界处并递归两侧。内省排序定义内省排序英语Introsort 或 Introspective sort是快速排序和堆排序的结合由 David Musser 于 1997 年发明。内省排序其实是对快速排序的一种优化保证了最差时间复杂度为 $O(n\log n)$。性质内省排序将快速排序的最大递归深度限制为 $\lfloor \log_2n \rfloor$超过限制时就转换为堆排序。这样既保留了快速排序内存访问的局部性又可以防止快速排序在某些情况下性能退化为 $O(n^2)$。堆排序的最优、平均、最坏时间复杂度均为 $O(n\log n)$且是原地算法正好充当快排退化时的兜底方案。实现从 2000 年 6 月起SGI C STL 的stl_algo.h中sort()函数的实现采用了内省排序算法。这一点在 OI-wiki 的 STL 排序函数页面可以得到交叉印证std::sort的旧版 C 标准仅要求平均时间复杂度达到 $O(n\log n)$而 C11 标准及后续标准要求最坏时间复杂度也达到 $O(n\log n)$C 标准并未严格要求此函数的实现算法具体实现取决于编译器libstdc 和 libc 中的实现都使用了内省排序。也就是说现代竞赛与工程环境中直接调用std::sort其内部正是快排 堆排的混合体天然规避了 $O(n^2)$ 退化。线性找第 k 大的数在下面的代码示例中第 $k$ 大的数被定义为序列排成升序时第 $k$ 个位置上的数编号从 0 开始。找第 $k$ 大的数K-th order statistic最简单的方法是先排序然后直接找到第 $k$ 大的位置的元素。这样做的时间复杂度是 $O(n\log n)$对于这个问题来说很不划算。我们可以借助快速排序的思想解决这个问题。考虑快速排序的划分过程在快速排序的划分结束后数列 $A_{p} \cdots A_{r}$ 被分成了 $A_{p} \cdots A_{q}$ 和 $A_{q1} \cdots A_{r}$此时可以按照左边元素的个数$q - p 1$和 $k$ 的大小关系来判断是只在左边还是只在右边递归地求解——每次划分后只需进入一侧另一侧被整体排除因此期望代价远低于完整排序。和快速排序一样该方法的时间复杂度依赖于每次划分时选择的分界值。如果采用随机选取分界值的方式可以证明在期望意义下程序的时间复杂度为 $O(n)$。这一思想同样存在于标准库中OI-wiki 的 STL 排序函数指出std::nth_element(first, nth, last)会重排[first, last)中的元素使得nth所指向的元素变为排好序后该位置会出现的元素且nth前的所有元素小于或等于nth后的所有元素其实现算法是未完成的内省排序平均时间复杂度为 $O(n)$常用于构建 K-D Tree。实现C// 模板的 T 参数表示元素的类型此类型需要定义小于运算 template typename T // arr 为查找范围数组rk 为需要查找的排名从 0 开始len 为数组长度 T find_kth_element(T arr[], int rk, const int len) { if (len 1) return arr[0]; // 随机选择基准pivot const T pivot arr[rand() % len]; // i当前操作的元素下标 // arr[0, j)存储小于 pivot 的元素 // arr[k, len)存储大于 pivot 的元素 int i 0, j 0, k len; // 完成一趟三路快排将序列分为 // 小于 pivot 的元素 等于 pivot 的元素 大于 pivot 的元素 while (i k) { if (arr[i] pivot) swap(arr[i], arr[j]); else if (pivot arr[i]) swap(arr[i], arr[--k]); else i; } // 根据要找的排名与两条分界线的位置去不同的区间递归查找第 k 大的数 // 如果小于 pivot 的元素个数比 k 多则第 k 大的元素一定是一个小于 pivot 的元素 if (rk j) return find_kth_element(arr, rk, j); // 否则如果小于 pivot 和等于 pivot 的元素加起来也没有 k 多 // 则第 k 大的元素一定是一个大于 pivot 的元素 else if (rk k) return find_kth_element(arr k, rk - k, len - k); // 否则pivot 就是第 k 大的元素 return pivot; }该实现直接复用了三路快排的一趟划分逻辑然后依据排名rk与两条分界线j、k的关系决定递归方向落入中间等于 pivot区间时立即返回否则只在一侧递归且进入右侧时要把排名减去左侧已排除的元素个数。改进中位数中的中位数中位数中的中位数英文Median of medians提供了一种确定性的选择划分过程中分界值的方法从而能够让找第 $k$ 大的数算法在最坏情况下也能实现线性时间复杂度。该算法的流程如下将整个序列划分为 $\left \lfloor \dfrac{n}{5} \right \rfloor$ 组每组元素数不超过 5 个寻找每组元素的中位数因为元素个数较少可以直接使用插入排序等算法找出这 $\left \lfloor \dfrac{n}{5} \right \rfloor$ 组元素中位数中的中位数将该元素作为前述算法中每次划分时的分界值即可。时间复杂度证明下面将证明该算法在最坏情况下的时间复杂度为 $O(n)$。设 $T(n)$ 为问题规模为 $n$ 时解决问题需要的计算量。先分析前两步——划分与寻找中位数。由于划分后每组内的元素数量非常少不超过 5 个可以认为寻找一组元素的中位数的时间复杂度为 $O(1)$。因此找出所有 $\left \lfloor \dfrac{n}{5} \right \rfloor$ 组元素中位数的时间复杂度为 $O(n)$。接下来分析第三步——递归过程。这一步进行了两次递归调用第一次是寻找各组中位数中的中位数需要的开销显然为 $T(\dfrac{n}{5})$第二次是进入分界值的左侧部分或右侧部分。根据我们选取的划分元素有 $\dfrac{1}{2} \times \left \lfloor \dfrac{n}{5} \right \rfloor \left \lfloor \dfrac{n}{10} \right \rfloor$ 组元素的中位数小于分界值这几组元素中比中位数还小的元素也一定比分界值要小从而整个序列中小于分界值的元素至少有 $3 \times \left \lfloor \dfrac{n}{10} \right \rfloor \left \lfloor \dfrac{3n}{10} \right \rfloor$ 个。同理整个序列中大于分界值的元素也至少有 $\left \lfloor \dfrac{3n}{10} \right \rfloor$ 个。因此分界值的左边或右边至多有 $\dfrac{7n}{10}$ 个元素这次递归的时间开销的上界为 $T(\dfrac{7n}{10})$。综上可以列出这样的不等式$$ T(n) \leq T(\dfrac{n}{5}) T(\dfrac{7n}{10}) O(n) $$假设 $T(n) O(n)$ 在问题规模足够小时成立。根据定义此时有 $T(n) \leq cn$其中 $c$ 为一正常数。将不等式右边的所有 $T(n)$ 进行代换$$ \begin{aligned} T(n) \leq T(\dfrac{n}{5}) T(\dfrac{7n}{10}) O(n)\ \leq \dfrac{cn}{5} \dfrac{7cn}{10} O(n)\ \leq \dfrac{9cn}{10} O(n)\ O(n) \end{aligned} $$由于 $\dfrac{9c}{10} c$当 $n$ 足够大时 $O(n)$ 项可以吸收进 $cn$ 中递归式收敛由此证明该算法在最坏情况下也具有 $O(n)$ 的时间复杂度。这一每组 5 个元素 找中位数的中位数的技巧核心价值就在于把每次划分的平衡度从看运气变成有下界保证。总结回顾本文快速排序的完整知识图谱如下核心机制基于分治思想的三步流程——划分、递归、免合并划分基准的选择方式决定了算法的命运随机基准保障期望 $O(n\log n)$复杂度画像最优/平均 $O(n\log n)$、最坏 $O(n^2)$、不稳定期望复杂度的严格证明依赖元素对比较概率 $2/(j-i1)$这一关键引理三大优化方向三数取中规避有序序列退化、短序列转插入排序减少常数、三路划分聚集相等元素应对大量重复值工程级成品三路快速排序与基数排序思想混合、内省排序与堆排序结合后者正是现代std::sort的底层实现参见 STL 排序函数高级应用基于划分的线性期望时间找第 k 大数以及用中位数中的中位数将其强化为最坏情况线性时间。理解快速排序不仅意味着掌握一种排序算法更意味着掌握如何通过随机化与分治把不确定的输入转化为可控的期望性能这一算法设计范式这也是 OI-wiki 基础算法章节将其作为重点讲解的原因所在。参考资料与注释本文内容以 docs/basic/quick-sort.md 为主体交叉参考了仓库内以下文档分治与递归、插入排序、基数排序、堆排序、归并排序、排序算法导论、复杂度与 STL 排序函数。原文档中涉及的外部参考包括关于局部性原理的C 性能榨汁机系列文章解释快排缓存友好的实践优势、维基教科书中快速排序的算法实现条目递归与非递归、Python 实现的出处、关于三种快排及优化的博客文章以及关于 introsort 的维基百科条目。此外C 标准库中qsort、std::sort、std::nth_element、std::stable_sort、std::partial_sort的用法与复杂度要求详见 STL 排序函数页面。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考