C++快速排序全解析：分治思想、三种分区写法与工程级优化

先说一个我自己的体会。有一阵子我在处理一批模拟订单数据，几十万条结构体记录，需要按时间戳排序。头一回图省事，直接套了个最简单的选择排序，结果跑了快半分钟，整个后端接口直接超时。换成快排之后，同一批数据处理起来几乎感觉不到等待。排序这行代码在大多数工程里都躲在角落，平时不起眼，可数据量一旦上来，算法选型的差距立刻变成时间上的天壤之别。

这是C++算法系列的第7篇，聊分治法里最典型的应用——快速排序。这篇不只是给你一个能跑通的模板，而是把快排背后的分治思想、三种partition写法、复杂度为什么会退化、工程级优化是怎么落的，以及我自己实际代码里踩过的坑，一次讲透。适合刚学完C++语法、想系统捋一遍排序算法的读者，也适合面试前想彻底吃透快排的开发者。

1. 从"选择排序跑了半分钟"说起：为什么快排是默认选项

1.1 排序是很多高效算法的地基

先别急着背代码。排序在工程里出现的频率，远比你想象的高。数据去重要先排序，二分查找要先排序，求TopK、做区间合并、按时间轴展示日志，几乎都依赖一个有序数组作为前提。

我自己最常见的场景是日志分析：原始日志按到达顺序落盘，可能来自多个模块，时间戳是乱的。想画一条耗时曲线出来，第一步就是把记录按时间戳排好。这时候如果排序本身写成O(n^2)，后面所有依赖有序数据的逻辑都跟着遭殃。

1.2 常用排序的复杂度对比

把一堆排序算法放到一张表里看，形势很清楚：

O(nlogn)这一档里，归并排序稳定但需要额外O(n)空间，堆排序在工程实现里常数偏大、缓存访问不友好。快排占据了一个非常好的生态位：原地排序、平均情况常数小、对CPU缓存友好。所以各大语言标准库里最常用的通用排序，骨架上基本都是快排，外加一些兜底策略。

1.3 快排是分治思想最直观的样本

把快排学透的意义还在于，它是理解分治法的最佳切片。分治模型在归并、二分、线段树、经典分治算法里反复出现，但快排的"分治感"最特殊——它把大部分工作放在分解阶段，合并阶段什么都不用做。这一点后面展开说。

所以这篇的顺序是这样的：先讲清楚分治三步走，再写三种partition，然后分析最坏情况是怎么来的，接着给出一套工程级优化实现，最后用实测数据告诉你优化到底值多少。

2. 分治三步走：分解、求解、合并，以及那个"不用合并"的关键洞见

2.1 分治思想的一般模型

分治法做一件事，抽象出来就三步：把大问题拆成若干结构相同的子问题；递归解决每个子问题；把子问题的结果合并成大问题的结果。

这个模型最典型的例子是归并排序：先把数组对半砍，递归把左右半边分别排好序，最后用一次合并操作把两个有序数组拼成一个。归并排序的工作重心在"合并"这一步，因为拆的时候什么也没干。

快排则刚好反过来。

2.2 快排的分解：选基准与分区

快排的分解阶段做两件事。第一，从当前区间里选一个元素作为基准pivot；第二，通过一趟partition，把整个区间调整成这样的结构：pivot左侧的所有元素都不大于pivot，pivot右侧的所有元素都不小于pivot。

以数组[5, 2, 8, 1, 9]为例，选5为基准，一次分区后可能变成[2, 1] 5 [8, 9]。注意5自己已经待在了正确的位置上——最后的有序数组里，5就在第二个下标位置，左边两个元素确实比5小，右边两个元素确实比5大。

这就是快排最核心的洞见：一个元素一旦作为pivot完成一次分区，它的最终位置就被确定下来了。后续的递归只需要处理左右两个子区间，永远不需要再去移动5。

2.3 为什么快排的合并步骤是空操作

子问题怎么解决？对左区间和右区间各自递归调用同样的快排逻辑。当区间长度缩小到1个元素，天然有序，递归终止。

合并步骤呢？没有。左右两个区间各自有序之后，整个数组就已经完全有序了。因为pivot已经被固定在正确位置，左侧区间的所有元素都小于等于pivot，右侧区间的所有元素都大于等于pivot，不需要任何额外的拼接操作。

用整理书架来类比：你随手抽一本书作为参照，比它薄的放左边，比它厚的放右边，这本书本身放回架子中间。然后对左边那堆再抽一本继续分，对右边那堆也继续分。等每一堆都只有一两本书的时候，整个书架就已经按厚度排列好了。你从来没有做过"把两堆书拼起来"这种操作，它们是各归各位自然形成的。

伪代码骨架长这样：

void quickSort(vector& a, int left, int right) { if (left >= right) return; // 只有一个元素，递归终止 int pivotIndex = partition(a, left, right); // 分解 quickSort(a, left, pivotIndex - 1); // 递归处理左侧 quickSort(a, pivotIndex + 1, right); // 递归处理右侧 // 没有合并步骤 }

这个骨架极其简洁，但真正容易写错的地方全藏在partition里。下一节把三种主流partition写法拉出来对比。

3. partition三选一：Lomuto、Hoare、挖坑法怎么选

3.1 Lomuto分区：教学和面试的第一选择

Lomuto分区是最容易理解的一种。它的策略是以区间最后一个元素为pivot，用一个指针i维护"最后一个不大于pivot的位置"，再用另一个指针j从头到尾扫描。

int lomutoPartition(std::vector<int>& a, int l, int r) { int pivot = a[r]; int i = l; for (int j = l; j < r; ++j) { if (a[j] <= pivot) { std::swap(a[i], a[j]); ++i; } } std::swap(a[i], a[r]); return i; }

走一遍就明白了。i一开始指向区间头部，j从l扫到r-1。每遇到一个不大于pivot的元素，就把它换到前面去，i前进一格。扫描结束后，区间被分成三段：[l, i-1]都不大于pivot，[i, r-1]都大于pivot，最后把pivot与a[i]互换，pivot就到了最终位置。

Lomuto的优点是代码短、边界条件少，非常适合面试时徒手写。缺点是交换次数偏多，尤其当pivot取值不理想时，一次分区会做大量无意义交换。工程上一般不直接用，但我个人认为面试时先写Lomuto是最稳的，不容易翻车。

对应的快排调用：

void quickSortL(std::vector<int>& a, int l, int r) { if (l >= r) return; int p = lomutoPartition(a, l, r); quickSortL(a, l, p - 1); quickSortL(a, p + 1, r); }

3.2 Hoare分区：交换次数更少，边界更挑剔

Hoare分区是快排原始论文里的写法。它的思路是：pivot可以取区间中间值，然后用两个指针i、j从两端往中间走，i找不小于pivot的，j找不大于pivot的，找到就交换，直到i和j相遇。

int hoarePartition(std::vector<int>& a, int l, int r) { int pivot = a[l + (r - l) / 2]; int i = l - 1; int j = r + 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]); } }

这段代码对边界极其敏感。a[i] < pivot和a[j] > pivot里用的是严格小于和严格大于，目的是让等于pivot的元素也能被跨过去，避免i和j卡死。如果这里写成<=和>=，当区间里有很多等于pivot的元素时，i、j很容易在某处原地打转，最后分区失去意义。

Hoare分区和Lomuto有一个非常关键的区别：它返回的下标j并不是pivot的最终位置，只是左右区间的一个分界点。所以递归调用要写成这样：

void quickSortH(std::vector<int>& a, int l, int r) { if (l >= r) return; int p = hoarePartition(a, l, r); quickSortH(a, l, p); quickSortH(a, p + 1, r); }

注意左区间是[l, p]，不是[l, p - 1]。这一点几乎每次写Hoare都要踩，写错就是无限递归加栈溢出。

3.3 挖坑法：笔试里的讨巧写法

挖坑法在教材和笔试题里出现频率很高，实现思路是：把pivot值先存下来，原位置看作一个坑，然后从右往左找小于pivot的填坑，坑转移到右边；再从左往右找大于pivot的填坑，坑转移到左边；循环直到左右指针相遇，把pivot填进最后的坑。

int holePartition(std::vector<int>& a, int l, int r) { int pivot = a[l]; int i = l, j = r; while (i < j) { while (i < j && a[j] >= pivot) --j; a[i] = a[j]; while (i < j && a[i] <= pivot) ++i; a[j] = a[i]; } a[i] = pivot; return i; }

挖坑法的本质和Lomuto很像，只是用一个坑位减少了显式的swap调用。它最大的好处是手算、手推起来很直观，适合在白板上画给面试官看。但注意内层循环的等号处理：右指针找的是严格小于pivot的，左指针找的是严格大于pivot的，这样大量重复元素才不会导致死循环。

3.4 三种写法横向对比与稳定性

稳定性问题上多说一句。快排是不稳定的，因为分区过程里发生了跨距离交换。比如数组[3a, 2, 3b, 1]，选最后一个1当pivot做Lomuto分区，两个3在swap过程中相对顺序可能直接被颠倒。所以如果业务上要求"时间相同保持原始顺序"，不要自己写快排，直接考虑归并排序或者标准库的稳定排序版本。

4. 复杂度推演与实测崩溃：有序数组为何能把快排打成O(n^2)

4.1 均匀分区时的递归式

先看理想情况。假设每次分区都能把区间近似对半切开，那么快排的递归式是：

T(n) = 2 * T(n/2) + O(n)

这个式子的意思是：处理规模为n的区间，要花O(n)做一次分区，然后递归处理两个规模为n/2的子区间。展开这个递归式，每层总共处理n个元素，递归深度约log2(n)层，所以总复杂度是O(nlogn)。

比较次数上有个实际经验值：快排的平均比较次数大约是 1.39 * n * log2(n)。这个常数比归并排序的 n * log2(n) 大一点，但因为快排是原地扫描、支持缓存友好访问，实际运行时间往往反而更短。

4.2 分区严重失衡时的递归式

如果每次分区都不均衡呢？极端情况是pivot恰好每次都是当前区间的最小值或最大值，那么一次分区只把区间切成1个元素和n-1个元素两段，递归式变成：

T(n) = T(n-1) + O(n)

把这个式子一路展开：T(n) = n + (n-1) + (n-2) + ... + 1，正好是 n(n+1)/2，也就是O(n^2)。这是排序算法里最尴尬的事情——理论上O(nlogn)的算法，在最坏情况下和冒泡排序一个水平。

4.3 两个最常见的退化场景

第一个场景，就是数据基本有序，而代码固定取第一个元素当pivot。假设给你一个已经排好序的数组1, 2, 3, ..., 10000，每次取a[l]当pivot，这个pivot恰好是整个区间的最小值。于是一次分区之后，pivot被放到最左端，右边剩9999个元素需要继续递归。第二次递归又取新的第一个元素，又是最小值，又只能分出去一个。这样一路递归下去，递归深度直接冲到一万层。

第二个场景是大量重复元素。如果pivot取的是区间中某个值，而区间里几乎一半元素都和pivot相等，采用上面提到的Lomuto版本且等号处理不当，分区结果会非常不均衡，等于把一大片"等于pivot"的元素全堆在一侧，递归深度和比较次数双双失控。

4.4 我的一个真实崩溃现场

我印象挺深的一次：处理一批已经按ID升序排列的结构体，需要改成按时间字段排序。我图省事，把固定取首元素的快排模板直接套上去，数据也不算特别大，七八万条记录，结果程序直接抛栈溢出。原因就是这个递归式：七八万层的递归调用，把程序栈彻底打爆了。

当时第一反应是"是不是代码有死循环"，排查了半天才发现不是死循环，是赤裸裸的O(n^2)退化外加栈空间耗尽。换掉基准选取策略之后，同一批数据毫秒级跑完。从那以后我对"小学生模板都能AC"这种事就再也不信了——模板只是起点，数据特征才是决定算法命运的东西。

5. 工程级快排的四件套：随机化、三点取中、三路分区与小数组兜底

5.1 随机pivot与三点取中

解决退化问题的第一板斧是让pivot选得更聪明。一种是随机化：在[l, r]里随机选一个下标跟a[l]交换，再取a[l]作为pivot。随机化后，遇到最坏情况是一种低概率事件，平均表现非常稳健。代价是生成随机数有少量开销。

另一种更工程化的是三点取中。从区间的首、中、尾三个位置取出中位数来当pivot，实现如下：

int medianOfThree(std::vector<int>& a, int l, int r) { int m = l + (r - l) / 2; if (a[l] > a[m]) std::swap(a[l], a[m]); if (a[l] > a[r]) std::swap(a[l], a[r]); if (a[m] > a[r]) std::swap(a[m], a[r]); return m; }

执行完之后，a[l] <= a[m] <= a[r]，a[m]就是中位数。这个策略对几乎有序的输入特别有效：如果数组整体有序，中间元素天然是中位数，分区瞬间回到均匀状态。实际工程里三点取中比纯随机更常见，因为省掉了随机数生成的开销，行为也可预测。

5.2 小区间插入排序兜底

递归调用不是免费的。每递归一层，要处理栈帧分配、函数调用开销、左右分区扫描。当区间缩小到几十个元素时，快排在"小规模数据"上的常数已经比插入排序更高了。

工程标准的做法是：当r - l + 1 <= 16时，直接改用插入排序。为什么阈值选16？这个数值来源于大量测试的折中：再小一点，插入排序优势不明显；再大一点，插入排序O(n^2)的本质又会影响性能。我一般用16，也有人用20或32，差别不大。

void insertionSort(std::vector<int>& a, int l, int r) { for (int i = l + 1; i <= r; ++i) { int key = a[i]; int j = i - 1; while (j >= l && a[j] > key) { a[j + 1] = a[j]; --j; } a[j + 1] = key; } }

5.3 三路快排：处理大量重复元素的关键

前面说过，大量重复元素能逼疯普通快排。应对办法是三路快排，也叫荷兰国旗分区，把区间一次分成三块：小于pivot、等于pivot、大于pivot。等于pivot的区块直接跳过不参与递归。

void quickSort3Way(std::vector<int>& a, int l, int r) { if (l >= r) return; if (r - l + 1 <= 16) { insertionSort(a, l, r); return; } int pivot = a[l]; int lt = l; int gt = r; int i = l + 1; while (i <= gt) { if (a[i] < pivot) { std::swap(a[lt], a[i]); ++lt; ++i; } else if (a[i] > pivot) { std::swap(a[i], a[gt]); --gt; } else { ++i; } } quickSort3Way(a, l, lt - 1); quickSort3Way(a, gt + 1, r); }

代码逻辑：lt维护当前已扫描区域中最右侧的小于pivot边界，gt维护大于pivot边界，i遍历中间。遇到小于pivot的元素，交换到左边；遇到大于pivot的，交换到右边，但此时i不动，因为换过来的新元素还没检查过；遇到等于的直接i++。

这个版本处理100万个值只取0到9这样的枚举数据时，效果是降维打击。大量相等的元素被合并到中间区块，完全不参与后续递归，实测总时间接近O(n)级别。

5.4 内省排序：防退化兜底策略

就算加了三点取中，理论上快排最坏情况依然是O(n^2)。标准库sort的思路更绝：它不依赖运气，而是检测递归深度，一旦深度超过某个阈值(大约是2log2(n))，就改用堆排序收尾。因为堆排序最坏情况稳定是O(nlogn)。这种"快速排序+插入排序+堆排序"的组合叫内省排序。

我这里给一个简化版思路：把递归深度作为一个参数传进去，深度超限就切换到堆排序。实际工程中你完全可以直接依赖标准库的sort，自己实现快排主要出现在刷题、面试、或对数据特征有定制需求时。但理解内省排序的兜底策略，能让你明白标准库sort为什么敢在绝大多数数据上跑的飞快还不翻车。

5.5 用尾递归降低栈深度

快排的空间复杂度本质是递归栈深度。最坏情况下O(n)的栈深度是这个算法的结构性问题。除了换成随机化降低概率，还可以做一层尾递归优化：每次只递归元素数量较少的那个子区间，另一个子区间用循环继续处理。

void quickSortIterHelper(std::vector<int>& a, int l, int r) { while (l < r) { int p = lomutoPartition(a, l, r); if (p - l < r - p) { quickSortIterHelper(a, l, p - 1); l = p + 1; } else { quickSortIterHelper(a, p + 1, r); r = p - 1; } } }

这段代码用while替代一半的递归，确保每一次递归处理的区间都不会超过当前区间的一半，栈深度被压到O(logn)。手写快排时加上这层保险，会让你的代码在极端数据下更抗造。

6. 实测对比与排坑笔记：优化前后差多少，以及几个没人提醒你的细节

6.1 测试环境与数据构造

纸上谈兵没意思。我用一台普通开发机，编译器开了O2优化，分别测试了100万个随机int、100万个升序int、100万个只取0到9重复值int三类数据，计时用std::chrono，正确性用std::is_sorted校验。

std::vector<int> data(1000000); std::generate(data.begin(), data.end(), []() { return rand() % 1000000; }); auto start = std::chrono::steady_clock::now(); quickSort3Way(data, 0, data.size() - 1); auto end = std::chrono::steady_clock::now(); // 校验逻辑略

6.2 优化前后耗时对比

不同机器、不同编译器的实测数字会有浮动，但趋势稳定：三点取中救活了有序数据，三路快排救活了重复数据。朴素版在升序数据上的栈溢出，不是性能问题，直接是可用性问题。

6.3 实战中反复踩过的代码坑

第一坑，区间取中点写成了(l + r) / 2。当l和r都很大时，两个int相加可能溢出，正确写法是l + (r - l) / 2。在刷题时这个坑不常见，但处理几千万级别索引的排序时会真实发生。

第二坑，Lomuto分区里把a[j] <= pivot写成a[j] < pivot。看起来差别不大，结果会导致大量等于pivot的元素始终留在后半区，pivot的最终位置偏移，分区失衡。等于号的处理在快排里从来不是小事。

第三坑，Hoare分区返回的p下标，被当成pivot最终位置去递归[l, p-1]和[p+1, r]。这个写错之后，轻则某些元素永远没参与排序，重则无限递归。记住Hoare的返回值是分界点，不是pivot。

第四坑，递归终止条件写成if (l > r)而不是if (l >= r)。如果某个递归调用传入了p+1 > r之类的区间，l > r虽然能退出，但很容易掩盖上游递归区间划分的问题。我更倾向用l >= r直接杜绝空区间进入递归。

第五坑，排序函数参数用了值传递vector<int> a，整段快排立刻变成O(n^2)级别的拷贝灾难。一定要用引用传递，或者用迭代器区间。

6.4 什么时候别让快排上场

快排不是银弹。如果你需要稳定性，比如按时间排序时要求相同时刻保持原始先后，快排的跨距离交换会毁掉这个顺序，此时应选归并排序或标准库的稳定排序版本。

如果排序的元素是体积很大的结构体，频繁swap的拷贝成本会很高。可以改用索引数组或指针数组排序，先用vector<int>存下标，排序时只交换下标，最后按下标顺序输出。这样无论元素多大，参与比较和交换的都是几个整数。

如果数据几乎有序且规模很大，快排配合三点取中表现还不错，但更彻底的选择是采用一些混合归并思路的排序。这类排序在近有序数据上能做到接近线性的表现。工程里碰到"数据只差一点就排好"的场景，不要只看平均复杂度，要专门留意数据分布特征。

最后再分享一点个人的写法习惯

这些年我写C++排序，九成情况直接调标准库的sort和稳定排序版本，自己手写快排的机会主要集中在刷题、面试、或者遇到特殊数据需要定制分区逻辑的时候。但我强烈建议你把快排从头到尾手写一遍：Lomuto一遍，Hoare一遍，三路快排一遍。不是为了背模板，而是写的过程会让你真正理解递归、分治和工程折中是怎么回事。尤其是把"为什么取中点而不是写死第一个元素""为什么等于号必须这样处理"这些问题自己回答清楚之后，再看标准库sort的文档，你会突然觉得那些实现都是有血有肉的设计决策，而不是一个黑盒。快排的思想不会过时，它至今仍是理解算法思维和解耦问题时最好的入门样本。