算法)
前言快速排序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的关系。代码按 C17 编写未在本机编译执行正确性按标准语义逐行推演。一、划分快排的核心快排的正确性几乎全部取决于划分函数。划分要满足一个不变式返回位置p之后[lo, p]的元素都不大于[p1, hi]的元素且基准落在正确的一侧。注意这不是「基准在最终位置」——Hoare 划分不保证基准归位这是最常见的混淆点。Lomuto 划分Lomuto 方案取最后一个元素作基准用i维护「小于基准区域」的右边界// 适用于 C17#include utility#include vectorint partition_lomuto(std::vectorint a, int lo, int hi) {int pivot a[hi];int i lo; // [lo, i) 都小于 pivotfor (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]与[i1, hi]。Lomuto 写法简单但对「大量重复元素」表现差等于基准的元素全被推到右侧划分极不均衡。Hoare 划分Hoare 方案从两端向中间扫描交换逆序对// 适用于 C17int partition_hoare(std::vectorint 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]的元素都不大于[j1, hi]的元素。因此递归区间是[lo, j]与[j1, hi]不是[lo, j-1]与[j1, hi]。如果按 Lomuto 的习惯写j-1会漏掉元素甚至无限递归。两个do-while的边界依赖哨兵因为pivot取自区间内部i最多走到基准值处停下j最多走到基准值处停下不会越界。这也是为什么不能随便把pivot换成区间外的值。二、递归实现与深度控制有了划分递归写法很直接但要注意两个工程问题区间为空/单元素时立即返回递归深度最坏为 n需要控制。// 适用于 C17#include vector#include utilityvoid quick_sort_impl(std::vectorint 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::vectorint a) {if (a.size() 2) {return;}quick_sort_impl(a, 0, static_castint(a.size()) - 1);}「先递归较小一侧、较大一侧改用循环」这个技巧把递归深度压到 O(log n)每层至少把较小的一半处理掉剩余部分在下一轮循环里继续栈上同时存在的帧数不会超过 log₂n 的量级。标准并没有规定栈大小但把深度从 O(n) 降到 O(log n) 对避免栈溢出有实际意义。基准选择也影响退化概率。取首元素在「已排序」「逆序」输入上最差取中间元素能避开这两个常见陷阱三数取中首、中、尾的中位数进一步降低恶意输入的影响但仍不能对抗刻意构造的数据。真正要在对抗性输入下保证 O(n log n)需要内省排序或随机化基准。三、迭代版用显式栈代替递归如果不想依赖调用栈可以用std::vectorstd::pairint,int当显式栈。这样栈的容量受堆限制也便于观察。// 适用于 C17#include utility#include vectorvoid quick_sort_iterative(std::vectorint a) {if (a.size() 2) {return;}std::vectorstd::pairint, int stack;stack.emplace_back(0, static_castint(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]需要 C17。显式栈的缺点是可能压入大量区间最坏情况下栈内元素数量与递归深度同阶如果用「先处理小区间」的策略可以把栈深度也压到 O(log n)。注意partition_hoare的参数是inta.size()转int在超大容器上可能溢出工程代码应改用std::ptrdiff_t或std::size_t并单独处理空区间。四、与std::sort的关系维度教科书快排std::sort最坏复杂度O(n²)通常保证 O(n log n)内省排序稳定性不稳定不稳定额外空间O(log n) 栈O(log n) 栈小数组处理继续递归常切换插入排序比较器要求严格弱序严格弱序是否可并行需自己实现C17 提供并行重载std::sort在多数实现里是内省排序快排为主递归深度超过阈值时改用堆排序区间较小时用插入排序。它不保证稳定需要稳定排序用std::stable_sort。自己写快排的价值主要是理解算法工程中直接用std::sort更稳妥。无论哪种实现比较都必须是严格弱序strict weak ordering。用作比较会让相等元素互相「小于」划分可能越界或死循环属于未定义行为undefined behavior, UB。常见坑点❌ Lomuto 划分后递归[lo, p]与[p1, hi]。✅ Lomuto 的基准已归位应递归[lo, p-1]与[p1, hi]并先判断p lo。❌ Hoare 划分后递归[lo, p-1]与[p1, hi]。✅ Hoare 的基准不保证归位应递归[lo, p]与[p1, 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或给比较加次级键。总结要点结论平均/最坏复杂度O(n log n) / O(n²)空间递归栈 O(log n)优化后稳定性不稳定Lomuto基准归位递归[lo,p-1]、[p1,hi]Hoare基准不归位递归[lo,p]、[p1,hi]退化防护合理选基准 小区间切换 深度限制工程选择优先std::sort自实现用于学习快排的代码很短短到让人以为难点在语法真正的难点在划分的边界与退化防护。把「哪种划分对应哪种递归区间」记牢再用「先小后大」控制深度才算真正写对了快排。理解这些之后再看std::sort为什么要引入内省机制就会非常自然。
前言快速排序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的关系。代码按 C17 编写未在本机编译执行正确性按标准语义逐行推演。一、划分快排的核心快排的正确性几乎全部取决于划分函数。划分要满足一个不变式返回位置p之后[lo, p]的元素都不大于[p1, hi]的元素且基准落在正确的一侧。注意这不是「基准在最终位置」——Hoare 划分不保证基准归位这是最常见的混淆点。Lomuto 划分Lomuto 方案取最后一个元素作基准用i维护「小于基准区域」的右边界// 适用于 C17#include utility#include vectorint partition_lomuto(std::vectorint a, int lo, int hi) {int pivot a[hi];int i lo; // [lo, i) 都小于 pivotfor (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]与[i1, hi]。Lomuto 写法简单但对「大量重复元素」表现差等于基准的元素全被推到右侧划分极不均衡。Hoare 划分Hoare 方案从两端向中间扫描交换逆序对// 适用于 C17int partition_hoare(std::vectorint 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]的元素都不大于[j1, hi]的元素。因此递归区间是[lo, j]与[j1, hi]不是[lo, j-1]与[j1, hi]。如果按 Lomuto 的习惯写j-1会漏掉元素甚至无限递归。两个do-while的边界依赖哨兵因为pivot取自区间内部i最多走到基准值处停下j最多走到基准值处停下不会越界。这也是为什么不能随便把pivot换成区间外的值。二、递归实现与深度控制有了划分递归写法很直接但要注意两个工程问题区间为空/单元素时立即返回递归深度最坏为 n需要控制。// 适用于 C17#include vector#include utilityvoid quick_sort_impl(std::vectorint 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::vectorint a) {if (a.size() 2) {return;}quick_sort_impl(a, 0, static_castint(a.size()) - 1);}「先递归较小一侧、较大一侧改用循环」这个技巧把递归深度压到 O(log n)每层至少把较小的一半处理掉剩余部分在下一轮循环里继续栈上同时存在的帧数不会超过 log₂n 的量级。标准并没有规定栈大小但把深度从 O(n) 降到 O(log n) 对避免栈溢出有实际意义。基准选择也影响退化概率。取首元素在「已排序」「逆序」输入上最差取中间元素能避开这两个常见陷阱三数取中首、中、尾的中位数进一步降低恶意输入的影响但仍不能对抗刻意构造的数据。真正要在对抗性输入下保证 O(n log n)需要内省排序或随机化基准。三、迭代版用显式栈代替递归如果不想依赖调用栈可以用std::vectorstd::pairint,int当显式栈。这样栈的容量受堆限制也便于观察。// 适用于 C17#include utility#include vectorvoid quick_sort_iterative(std::vectorint a) {if (a.size() 2) {return;}std::vectorstd::pairint, int stack;stack.emplace_back(0, static_castint(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]需要 C17。显式栈的缺点是可能压入大量区间最坏情况下栈内元素数量与递归深度同阶如果用「先处理小区间」的策略可以把栈深度也压到 O(log n)。注意partition_hoare的参数是inta.size()转int在超大容器上可能溢出工程代码应改用std::ptrdiff_t或std::size_t并单独处理空区间。四、与std::sort的关系维度教科书快排std::sort最坏复杂度O(n²)通常保证 O(n log n)内省排序稳定性不稳定不稳定额外空间O(log n) 栈O(log n) 栈小数组处理继续递归常切换插入排序比较器要求严格弱序严格弱序是否可并行需自己实现C17 提供并行重载std::sort在多数实现里是内省排序快排为主递归深度超过阈值时改用堆排序区间较小时用插入排序。它不保证稳定需要稳定排序用std::stable_sort。自己写快排的价值主要是理解算法工程中直接用std::sort更稳妥。无论哪种实现比较都必须是严格弱序strict weak ordering。用作比较会让相等元素互相「小于」划分可能越界或死循环属于未定义行为undefined behavior, UB。常见坑点❌ Lomuto 划分后递归[lo, p]与[p1, hi]。✅ Lomuto 的基准已归位应递归[lo, p-1]与[p1, hi]并先判断p lo。❌ Hoare 划分后递归[lo, p-1]与[p1, hi]。✅ Hoare 的基准不保证归位应递归[lo, p]与[p1, 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或给比较加次级键。总结要点结论平均/最坏复杂度O(n log n) / O(n²)空间递归栈 O(log n)优化后稳定性不稳定Lomuto基准归位递归[lo,p-1]、[p1,hi]Hoare基准不归位递归[lo,p]、[p1,hi]退化防护合理选基准 小区间切换 深度限制工程选择优先std::sort自实现用于学习快排的代码很短短到让人以为难点在语法真正的难点在划分的边界与退化防护。把「哪种划分对应哪种递归区间」记牢再用「先小后大」控制深度才算真正写对了快排。理解这些之后再看std::sort为什么要引入内省机制就会非常自然。
