C／C++实现双路快速排序算法原理

前言先澄清一个术语。中文里的「双路快速排序」通常指二路划分用两个指针分别从区间两端向中间扫描把元素分成「不大于基准」和「不小于基准」两部分。它和「双轴快速排序」dual-pivot quicksort选两个基准把区间分成三段不是一回事本文讲的是前者。二路划分要解决的核心问题是大量重复元素如果划分时把所有等于基准的元素都堆到一边遇到全相等的数组递归会退化成 O(n²)。常见的错误实现有两种。第一种是 Lomuto 划分用单指针从左到右扫描把小于基准的元素换到前面等于基准的元素全部留在右侧数组全相等时每次划分只能排除一个元素。第二种是双指针扫描时用或跳过等于基准的元素效果和 Lomuto 类似重复元素越多越慢。本文先说明二路划分为什么能均摊重复元素再逐行推演指针移动最后给出完整实现和几个边界情况的处理。示例以 C17 为准。一、划分的目标与重复元素的处理快速排序的骨架是「划分 递归」。划分选一个基准值 pivot把区间重排成三块小于 pivot 的、等于 pivot 的、大于 pivot 的。递归只需要处理小于和大于两块等于 pivot 的元素已经在最终位置上。不同的划分方式区别在于「等于 pivot 的元素分到哪边」。Lomuto 划分把小于 pivot 的放左边其余包括等于放右边一次划分后 pivot 落在分界点上但所有等于 pivot 的元素都挤在右侧。如果整个数组的元素都相等每次划分只能确定一个元素的位置递归深度为 n总代价 O(n²)。二路划分的关键改动是扫描时遇到等于 pivot 的元素也停下来把它和另一侧的等值元素交换。这样等于 pivot 的元素会被均匀地分到两侧全相等数组第一次划分就能把区间对半分开递归深度回到 O(log n)。代价是相等的元素之间发生了交换算法因此不稳定。这也解释了一个看似奇怪的现象在二路快排里内层循环的条件应当写成a[i] pivot和a[j] pivot而不是a[i] pivot和a[j] pivot。后者会「吞掉」等值元素让它们全部留在原地正是我们要避免的退化。二、双指针扫描的过程取区间第一个元素作为 pivot把它暂存在变量里数组的a[lo]位置在最后才会被覆盖。左指针i从lo 1向右走右指针j从hi向左走。每一轮做两件事i向右跳过所有严格小于 pivot 的元素停在第一个「不小于 pivot」的位置。j向左跳过所有严格大于 pivot 的元素停在第一个「不大于 pivot」的位置。如果此时i j说明两个指针已经交错划分结束。否则交换a[i]与a[j]然后i右移、j左移继续下一轮。扫描时必须带上i j的边界判断。没有它当区间里所有元素都小于 pivot 时i会一路走出hi访问越界同理j可能走到lo以下。这两个边界不是可选的优化而是正确性的一部分。循环结束后j指向「左侧区域的最后一个位置」a[j]一定不大于 pivot。把a[lo]与a[j]交换pivot 就落到了j左侧全部不大于它右侧全部不小于它。返回j作为下一轮递归的分界。为什么最后交换的是j而不是i因为i停下的位置是第一个「不小于 pivot」的元素它可能大于 pivot而j停下的位置保证不大于 pivot。把 pivot 换到j左边才满足「不大于」。用i会导致左侧混入大于 pivot 的元素排序结果错误。三、递归与栈深度标准的递归写法是对左右两段分别调用。最坏情况下例如输入已经有序、每次取第一个元素作 pivot递归深度会达到 n节点数多时可能耗尽调用栈。一个常用的改进是「先递归较短的一侧较长的一侧用循环处理」。每次划分后比较左右两段的长度对短的一侧递归长的一侧通过更新lo或hi继续循环。这样栈上同时存在的递归层数不会超过 O(log n)即使最坏情况也不会因为深度爆栈代价是时间复杂度仍然可能是 O(n²)。这个技巧不改变算法的时间复杂度只改变空间复杂度。它常被误认为能「避免最坏情况」实际上只是把最坏情况从「可能崩溃」变成「跑得慢」。四、完整示例// 适用于 C17#include algorithm#include cstddef#include iostream#include utility#include vectortemplate typename Tint partition(std::vectorT a, int lo, int hi) {const T pivot a[static_caststd::size_t(lo)];int i lo 1;int j hi;while (true) {while (i j a[static_caststd::size_t(i)] pivot) i;while (i j a[static_caststd::size_t(j)] pivot) --j;if (i j) break;std::swap(a[static_caststd::size_t(i)],a[static_caststd::size_t(j)]);i;--j;}std::swap(a[static_caststd::size_t(lo)],a[static_caststd::size_t(j)]);return j;}template typename Tvoid quickSort(std::vectorT a, int lo, int hi) {while (lo hi) {int p partition(a, lo, hi);// 先递归较短的一侧较长的一侧留在循环里处理if (p - lo hi - p) {quickSort(a, lo, p - 1);lo p 1;} else {quickSort(a, p 1, hi);hi p - 1;}}}int main() {std::vectorint data {5, 3, 8, 1, 9, 2, 7, 4, 6, 0, 5, 5, 3};if (!data.empty()) {quickSort(data, 0, static_castint(data.size()) - 1);}for (int x : data) std::cout x ;std::cout \n;std::cout std::boolalpha std::is_sorted(data.begin(), data.end()) \n;return 0;}逐段推演。以{5, 3, 8, 1, 9, 2, 7, 4, 6, 0, 5, 5, 3}为例pivot 是 5i从下标 1 开始。3 小于 5i走到 28 不小于 5停住。j从末尾 3 开始3 不大于 5停住交换 8 和 3i到 3、j到 10。接着i扫过 1停在 9j扫过 5、5、6都大于 5停在 4交换 9 和 4。如此往复最终j停在左侧区域的末尾把 pivot 换过去。递归部分用p - lo hi - p判断哪边更短。若左边短先递归左边再把lo推到p 1继续处理右边否则反过来。p - 1和p 1保证每轮区间至少缩小一个元素不会出现p始终等于lo导致的无限递归。partition里的下标转换写得比较啰嗦是因为std::vector::operator[]接受std::size_t而指针用int更便于表达「可能为 -1」的状态。实际工程中也可以全部用std::ptrdiff_t避免有符号与无符号混用带来的警告。五、复杂度与工程取舍二路快排的平均时间复杂度是 O(n log n)最坏是 O(n²)。最坏情况包括每次选到的 pivot 都是当前区间的极值例如对已排序数组取首元素或者划分极不平衡。随机选择 pivot、三数取中、小区间改用插入排序都是常见的缓解手段。空间方面递归实现需要栈空间平均 O(log n)采用「短边递归」后最坏也能控制在 O(log n)。二路快排不稳定相等元素的相对顺序会改变需要稳定排序时应使用std::stable_sort或归并排序。标准库的std::sort通常采用内省排序introsort快速排序为主递归过深时切换为堆排序小区间用插入排序从而把最坏时间复杂度控制在 O(n log n)。自己实现快排主要用于教学或特殊数据类型生产代码优先用标准库。另外std::sort的比较器必须是严格弱序自己写划分时如果用到自定义比较也要保证同样的性质。本文的实现只用了和对内置类型和满足全序的自定义类型都成立。常见坑点坑点一内层扫描不判断边界。❌while (a[i] pivot) i;所有元素都小于 pivot 时 i 越界。✅while (i j a[i] pivot) i;两个指针都要加边界。坑点二用跳过等值元素。❌while (i j a[i] pivot) i;全相等数组退化成 O(n²)。✅ 严格小于才前进遇到等于 pivot 的元素停下来参与交换。坑点三最后把 pivot 换到i的位置。❌std::swap(a[lo], a[i]); return i;i 位置可能大于 pivot左侧被污染。✅ 换到jj是左侧区域最后一个不大于 pivot 的位置。坑点四递归区间没有排除 pivot。❌quickSort(a, lo, p); quickSort(a, p, hi);p 位置不变可能无限递归。✅quickSort(a, lo, p - 1); quickSort(a, p 1, hi);。坑点五对空数组也减一取区间。❌quickSort(a, 0, a.size() - 1);空 vector 时size() - 1回绕成极大值。✅ 先判断!a.empty()或把区间改成半开区间[lo, hi)。坑点六以为双路快排最坏也是 O(n log n)。❌ 认为「双路」就意味着复杂度有保证。✅ 最坏仍是 O(n²)只是重复元素多时表现更好要保证最坏界需要内省排序。坑点七以为双路快排稳定。❌ 依赖相等元素的原始顺序。✅ 交换会打乱顺序需要稳定排序时用std::stable_sort。坑点八用(lo hi) / 2取中点。❌ 区间很大时lo hi超出int范围有符号溢出是未定义行为。✅ 写成lo (hi - lo) / 2或改用无符号下标并注意回绕。总结维度二路快排划分方式双指针从两端扫描等于 pivot 也停下重复元素均摊到两侧避免全相等时退化平均时间O(n log n)最坏时间O(n²)取决于 pivot 选择空间短边递归后 O(log n)稳定性不稳定二路快排的价值不在「比普通快排快多少」而在它对重复元素的处理方式让等于基准的元素均匀分开而不是堆在一侧。实现时把边界判断、等值停住、pivot 换到j、递归排除p这四点做对划分就不会出错至于最坏情况靠随机化或内省排序去兜底而不是指望划分本身解决。