前言

快速排序（Quicksort）是分治法的经典应用：选一个基准值（pivot），把序列划分成「不大于基准」和「不小于基准」两部分，再对两部分递归排序。平均时间复杂度 O(n log n)，最坏 O(n²)，原地排序，不稳定。

围绕快排的误解主要集中在三处。第一，把「平均 O(n log n)」当成「任何输入都 O(n log n)」——对已排序数组固定取首元素作基准，每次划分只缩小一个元素，退化为 O(n²)，深层递归还可能栈溢出。第二，划分方案写错：Hoare 划分与 Lomuto 划分的边界条件不同，混用会死循环或漏排。第三，以为std::sort就是教科书快排——标准库通常用内省排序（introsort），在递归过深时切换到堆排序，保证最坏 O(n log n)。

本文给出 Lomuto 与 Hoare 两种划分的完整实现，说明各自的边界条件，再讨论基准选择、递归深度控制，以及与std::sort的关系。代码按 C++17 编写，未在本机编译执行，正确性按标准语义逐行推演。

一、划分：快排的核心

快排的正确性几乎全部取决于划分函数。划分要满足一个不变式：返回位置p之后，[lo, p]的元素都不大于[p+1, hi]的元素，且基准落在正确的一侧。注意这不是「基准在最终位置」——Hoare 划分不保证基准归位，这是最常见的混淆点。

Lomuto 划分

Lomuto 方案取最后一个元素作基准，用i维护「小于基准区域」的右边界：

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

int partition_lomuto(std::vector<int>& a, int lo, int hi) {
int pivot = a[hi];
int i = lo; // [lo, i) 都小于 pivot
for (int j = lo; j < hi; ++j) {
if (a[j] < pivot) {
std::swap(a[i], a[j]);
++i;
}
}
std::swap(a[i], a[hi]); // 基准归位
return i;
}

循环结束时[lo, i)全小于基准，[i, hi)全不小于基准，把a[hi]换到i位置后，a[i]就是基准，左侧全小于它，右侧全不小于它。返回i后递归[lo, i-1]与[i+1, hi]。Lomuto 写法简单，但对「大量重复元素」表现差：等于基准的元素全被推到右侧，划分极不均衡。

Hoare 划分

Hoare 方案从两端向中间扫描，交换逆序对：

// 适用于 C++17
int partition_hoare(std::vector<int>& a, int lo, int hi) {
int pivot = a[lo + (hi - lo) / 2]; // 取中间值，避免有序输入退化
int i = lo - 1;
int j = hi + 1;
while (true) {
do { ++i; } while (a[i] < pivot);
do { --j; } while (a[j] > pivot);
if (i >= j) {
return j;
}
std::swap(a[i], a[j]);
}
}

Hoare 划分返回的j满足：[lo, j]的元素都不大于[j+1, hi]的元素。因此递归区间是[lo, j]与[j+1, hi]，不是[lo, j-1]与[j+1, hi]。如果按 Lomuto 的习惯写j-1，会漏掉元素甚至无限递归。

两个do-while的边界依赖哨兵：因为pivot取自区间内部，i最多走到基准值处停下，j最多走到基准值处停下，不会越界。这也是为什么不能随便把pivot换成区间外的值。

二、递归实现与深度控制

有了划分，递归写法很直接，但要注意两个工程问题：区间为空/单元素时立即返回；递归深度最坏为 n，需要控制。

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

void quick_sort_impl(std::vector<int>& a, int lo, int hi) {
while (lo < hi) {
int p = partition_hoare(a, lo, hi);
// 先递归较小的一侧，再循环处理较大的一侧
if (p - lo < hi - (p + 1)) {
quick_sort_impl(a, lo, p);
lo = p + 1;
} else {
quick_sort_impl(a, p + 1, hi);
hi = p;
}
}
}

void quick_sort(std::vector<int>& a) {
if (a.size() < 2) {
return;
}
quick_sort_impl(a, 0, static_cast<int>(a.size()) - 1);
}

「先递归较小一侧、较大一侧改用循环」这个技巧把递归深度压到 O(log n)：每层至少把较小的一半处理掉，剩余部分在下一轮循环里继续，栈上同时存在的帧数不会超过 log₂n 的量级。标准并没有规定栈大小，但把深度从 O(n) 降到 O(log n) 对避免栈溢出有实际意义。

基准选择也影响退化概率。取首元素在「已排序」「逆序」输入上最差；取中间元素能避开这两个常见陷阱；三数取中（首、中、尾的中位数）进一步降低恶意输入的影响，但仍不能对抗刻意构造的数据。真正要在对抗性输入下保证 O(n log n)，需要内省排序或随机化基准。

三、迭代版：用显式栈代替递归

如果不想依赖调用栈，可以用std::vector<std::pair<int,int>>当显式栈。这样栈的容量受堆限制，也便于观察。

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

void quick_sort_iterative(std::vector<int>& a) {
if (a.size() < 2) {
return;
}
std::vector<std::pair<int, int>> stack;
stack.emplace_back(0, static_cast<int>(a.size()) - 1);

while (!stack.empty()) {
auto [lo, hi] = stack.back();
stack.pop_back();
if (lo >= hi) {
continue;
}
int p = partition_hoare(a, lo, hi);
stack.emplace_back(lo, p);
stack.emplace_back(p + 1, hi);
}
}

结构化绑定auto [lo, hi]需要 C++17。显式栈的缺点是可能压入大量区间，最坏情况下栈内元素数量与递归深度同阶；如果用「先处理小区间」的策略，可以把栈深度也压到 O(log n)。注意partition_hoare的参数是int，a.size()转int在超大容器上可能溢出，工程代码应改用std::ptrdiff_t或std::size_t并单独处理空区间。

四、与std::sort的关系

std::sort在多数实现里是内省排序：快排为主，递归深度超过阈值时改用堆排序，区间较小时用插入排序。它不保证稳定，需要稳定排序用std::stable_sort。自己写快排的价值主要是理解算法，工程中直接用std::sort更稳妥。

无论哪种实现，比较都必须是严格弱序（strict weak ordering）。用<=作比较会让相等元素互相「小于」，划分可能越界或死循环，属于未定义行为（undefined behavior, UB）。

常见坑点

• 
  
• ❌ Lomuto 划分后递归[lo, p]与[p+1, hi]。
• 
  

✅ Lomuto 的基准已归位，应递归[lo, p-1]与[p+1, hi]，并先判断p > lo。

• 
  
• ❌ Hoare 划分后递归[lo, p-1]与[p+1, hi]。
• 
  

✅ Hoare 的基准不保证归位，应递归[lo, p]与[p+1, hi]。

• 
  
• ❌ 固定取a[lo]作基准，遇到已排序数组退化。
• 
  

✅ 取中间元素、三数取中或随机化基准，并考虑内省排序。

• 
  
• ❌ 递归两侧都用递归调用，最坏深度达到 n。
• 
  

✅ 先递归较小一侧，较大一侧用循环，把栈深度控制在 O(log n)。

• 
  
• ❌ 比较器写成a <= b。
• 
  

✅ 用a < b，保证严格弱序；相等元素必须互不「小于」。

• 
  
• ❌ 用int存a.size()，超大容器上溢出为负数。
• 
  

✅ 用std::size_t或std::ptrdiff_t，并在转换为下标前检查范围。

• 
  
• ❌ 在 Hoare 划分里用while (a[i] < pivot) ++i;而不设边界。
• 
  

✅ 用do-while配合区间内基准作哨兵，或显式加i <= hi检查。

• 
  
• ❌ 认为快排稳定，依赖相等元素的原始顺序。
• 
  

✅ 快排不稳定；需要稳定结果用std::stable_sort或给比较加次级键。

总结

快排的代码很短，短到让人以为难点在语法；真正的难点在划分的边界与退化防护。把「哪种划分对应哪种递归区间」记牢，再用「先小后大」控制深度，才算真正写对了快排。理解这些之后，再看std::sort为什么要引入内省机制，就会非常自然。