企业官网建设流程全解析

前言

先澄清一个术语。中文里的「双路快速排序」通常指二路划分：用两个指针分别从区间两端向中间扫描，把元素分成「不大于基准」和「不小于基准」两部分。它和「双轴快速排序」（dual-pivot quicksort，选两个基准把区间分成三段）不是一回事，本文讲的是前者。二路划分要解决的核心问题是大量重复元素：如果划分时把所有等于基准的元素都堆到一边，遇到全相等的数组，递归会退化成 O(n²)。

常见的错误实现有两种。第一种是 Lomuto 划分，用单指针从左到右扫描，把小于基准的元素换到前面，等于基准的元素全部留在右侧；数组全相等时，每次划分只能排除一个元素。第二种是双指针扫描时用<=或>=跳过等于基准的元素，效果和 Lomuto 类似，重复元素越多越慢。

本文先说明二路划分为什么能均摊重复元素，再逐行推演指针移动，最后给出完整实现和几个边界情况的处理。示例以 C++17 为准。

一、划分的目标与重复元素的处理

快速排序的骨架是「划分 + 递归」。划分选一个基准值 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向左走。

每一轮做两件事：

1. 
   
2. i向右跳过所有严格小于 pivot 的元素，停在第一个「不小于 pivot」的位置。
3. 
   
4. j向左跳过所有严格大于 pivot 的元素，停在第一个「不大于 pivot」的位置。
5. 
   

如果此时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²)。

这个技巧不改变算法的时间复杂度，只改变空间复杂度。它常被误认为能「避免最坏情况」，实际上只是把最坏情况从「可能崩溃」变成「跑得慢」。

四、完整示例

// 适用于 C++17
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <utility>
#include <vector>

template <typename T>
int partition(std::vector<T>& a, int lo, int hi) {
const T pivot = a[static_cast<std::size_t>(lo)];
int i = lo + 1;
int j = hi;

while (true) {
while (i <= j && a[static_cast<std::size_t>(i)] < pivot) ++i;
while (i <= j && a[static_cast<std::size_t>(j)] > pivot) --j;

if (i > j) break;

std::swap(a[static_cast<std::size_t>(i)],
a[static_cast<std::size_t>(j)]);
++i;
--j;
}

std::swap(a[static_cast<std::size_t>(lo)],
a[static_cast<std::size_t>(j)]);
return j;
}

template <typename T>
void quickSort(std::vector<T>& 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::vector<int> data = {5, 3, 8, 1, 9, 2, 7, 4, 6, 0, 5, 5, 3};

if (!data.empty()) {
quickSort(data, 0, static_cast<int>(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 是 5，i从下标 1 开始。3 小于 5，i走到 2；8 不小于 5，停住。j从末尾 3 开始，3 不大于 5，停住；交换 8 和 3，i到 3、j到 10。接着i扫过 1，停在 9；j扫过 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，左侧被污染。

✅ 换到j，j是左侧区域最后一个不大于 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 换到j、递归排除p这四点做对，划分就不会出错；至于最坏情况，靠随机化或内省排序去兜底，而不是指望划分本身解决。