C++快速排序详解：分治思想、基准选取与三路快排实战

搞排序绕不开快排，搞懂快排绕不开分治。这篇是“C++算法”系列里专门聊快排的一篇，我把分治思想、基准选法、重复元素处理这些该讲清楚的细节都捋了一遍，配合完整的C++实现和调试心得，适合刚啃完基础排序、想系统搞懂快排原理的读者。

很多教材讲快排就讲个大概：选个基准，左右分区，递归下去。但真要自己上手写，坑不少——基准怎么选才不容易退化？大量重复元素为什么会让普通快排变慢？递归深度太深会不会爆栈？这些细节直接决定你写出来的排序能不能在实战里站得住。这篇就按我实际调试的顺序，把这些点一个一个拆开说。

1. 分治思想与快排的整体设计思路

1.1 快排为什么是分治的典型代表

分治思想拆成三步：分解、解决、合并。归并排序也是分治，但它合并的时候要额外开空间；快排的巧妙之处在于，它在“分解”这一步就通过原地交换把元素放到了正确位置，所以“合并”这一步什么都不用做。

具体来说，快排每轮做一件事：挑一个基准值（pivot），把数组分成两半，左半所有元素都小于等于基准，右半所有元素都大于等于基准，基准本身落在它最终的位置上。然后对左右两半分别递归执行同样的操作。整个数组有序，就是一轮轮“把基准放到正确位置”累积出来的结果。

很多初学者会问：为什么要把基准放到正确位置？举个最简单的例子，数组[3, 1, 2, 5, 4]，如果第一轮选中3作为基准，分区后变成[1, 2]、3、[5, 4]，此刻3已经不需要再动了——它的左边全比它小，右边全比它大，无论左右两边内部怎么排，3的最终位置就是这个。这个“基准归位”的性质，就是快排递归的根基。

1.2 一次分区的本质：不变量与扫描过程

写快排最容易翻车的地方就是分区函数。我推荐一段经典的“挖坑法”或者“左右指针法”，核心是维护一个不变量：

每一轮循环结束后，left左边的元素都不大于基准，right右边的元素都不小于基准。

用挖坑法举例，先记住基准值，原基准位置就形成“坑”，然后右侧指针往左找小于基准的值填坑，左侧指针向右找大于基准的值填坑，两个指针相遇的位置就是基准的最终位置。

初始数组: [6, 1, 2, 7, 9, 3, 4, 5, 10, 8] 基准: 6（数组第一个元素） 坑位: index 0 right 从右往左扫描，找到第一个小于6的元素: 5 把5填入index 0，数组变成 [5, 1, 2, 7, 9, 3, 4, *坑*, 10, 8] (坑在index 7) left 从左往右扫描，找到第一个大于6的元素: 7 把7填入index 7，数组变成 [5, 1, 2, *坑*, 9, 3, 4, 7, 10, 8] (坑在index 3) right 继续从右往左，找到小于6的元素: 3 把3填入index 3，数组变成 [5, 1, 2, 3, 9, *坑*, 4, 7, 10, 8] left 继续从左往右，找到大于6的元素: 9 把9填入index 5，数组变成 [5, 1, 2, 3, *坑*, 9, 4, 7, 10, 8] left最终停在index 4，right继续向左扫描遇到left，循环结束 把基准6填入index 4，完成分区: [5, 1, 2, 3, 4, 6, 9, 7, 10, 8]

挖坑法的好处是交换次数少，逻辑直观，每一轮扫描都把不变量维持得清清楚楚：left停下的位置只可能是一个“坑”，而“坑”意味着这个位置的元素已经安全地被挪到了别处。

1.3 复杂度与退化风险

快排的平均时间复杂度是O(n log n)，但最坏情况是O(n²)。这个最坏情况什么时候出现？基准每次选中的都是当前区间的最小值或最大值。比如对一个已经有序的数组，如果基准总是取第一个元素，那分区出来一侧是空、另一侧是n-1个元素，递归深度直接变成n，性能惨不忍睹。

所以快排的性能强依赖基准选取策略。常见的对策是三数取中——取区间的左端、右端和中间位置三个元素，比较大小后取中间值作为基准。这个策略能有效规避大部分有序数组导致的退化问题。我在第3节会给出完整实现。

2. 核心细节解析：分区算法的选型与实现要点

2.1 左右指针法与挖坑法的对比

分区算法是快排的灵魂，实现方式五花八门，我见到的教材版本至少有四五种。实际工程里最常用的就是左右指针法（Lomuto 分区）和挖坑法（Hoare 变种），两者的差别值得搞清楚。

左右指针法（Lomuto）的核心是维护一个“已处理的小于基准区域”的边界：遍历整个区间，把所有小于基准的元素往左边堆。这个实现代码短，容易记，但它的缺点是交换次数偏多，且对已有序数组，即使基准选得不错，交换的 cache 性能也不如 Hoare 分区。

挖坑法的优点是交换次数更少，同时它的“填坑”过程在思考上更接近手工排序的直觉，代码调试时更容易跟踪。我在实际项目中更常用挖坑法，因为它的循环不变量更容易口头验证——我只需要盯住left和right的位置和当前“坑”在哪。

2.2 标准分区代码的逐步拆解

先给出一版简洁直观的挖坑法实现，只做分区这一步：

int partition(vector<int>& nums, int left, int right) { int pivot = nums[left]; // 取第一个元素作为基准 while (left < right) { // 从右往左找小于 pivot 的元素填坑 while (left < right && nums[right] >= pivot) { right--; } if (left < right) { nums[left] = nums[right]; left++; } // 从左往右找大于 pivot 的元素填坑 while (left < right && nums[left] <= pivot) { left++; } if (left < right) { nums[right] = nums[left]; right--; } } // 此时 left == right，基准归位 nums[left] = pivot; return left; }

这段代码有几个细节值得强调：

第一，内层循环一定要加left < right条件。不加的话，当某一侧扫描越界时就会访问到区间外的内存，这是新手最容易踩的越界坑。left和right都是一步步收敛的，理论上不会越界，但并发或者递归调用时，一个小小的边界条件错误就很难排查。

第二，比较时要使用>=和<=，而不是>和<。如果把>=写成>，那所有等于基准的元素都会被搬到对面去，如果整个数组全是同一个值，分区会无限震荡，递归深度爆炸——这是快排在重复元素场景下失效的根源之一。

第三，循环结束后left == right，这个位置就是基准的最终位置。此时left索引上的值已经被搬走了（是个坑），直接把基准放回来，不额外做swap，省一次临时变量开销。

2.3 为什么选择 vector 而不是裸数组

实现快排，我默认直接用std::vector<int>，而不是 C 风格数组。这不是摆架子，而是vector自带长度信息，区间参数只要传left和right就够了，不用再额外传size。更重要的是，vector的底层是连续内存，快排这种强 cache 友好的算法在vector上能发挥出全部性能。用裸数组当然也能写，但当你递归拆分区间时，begin()和end()的指针计算容易让你在边界条件里迷失方向。

3. 实操过程与完整实现

3.1 从分区函数到完整排序

分区函数搞定后，快排主体就是递归调用。每次分区返回基准的最终位置pivotIndex，然后对[left, pivotIndex - 1]和[pivotIndex + 1, right]两个子区间分别递归。

void quickSort(vector<int>& nums, int left, int right) { if (left >= right) { return; // 区间为空或只有一个元素，无需排序 } int pivotIndex = partition(nums, left, right); quickSort(nums, left, pivotIndex - 1); quickSort(nums, pivotIndex + 1, right); }

从“分区函数”到“完整排序”，你只需要做两件事：递归调用左区间、递归调用右区间。这里有个容易忽略的点：分区函数返回的pivotIndex本身已经排好了，绝对不能再把它包含进递归的子区间里，否则会产生死循环——因为基准已经处在正确位置，再排它毫无意义，而且如果递归区间没有收缩，栈溢出就在不远处等着你。

3.2 加入三数取中优化

前面说了，快排对基准选择敏感。三数取中（median-of-three）是我用下来性价比最高的优化，它不用引入额外的随机数生成器，也没有理论分析上的偏差，实现起来就是三个比较：

int getMedianIndex(vector<int>& nums, int left, int right) { int mid = left + (right - left) / 2; if (nums[left] > nums[mid]) swap(nums[left], nums[mid]); if (nums[left] > nums[right]) swap(nums[left], nums[right]); if (nums[mid] > nums[right]) swap(nums[mid], nums[right]); return mid; // 经过三次比较，mid 位置的元素是三者的中间值 }

这里有个小技巧：**left + (right - left) / 2比(left + right) / 2更安全**。虽然日常写题时两者没区别，但当left和right都接近INT_MAX时，直接相加可能溢出。养成这个习惯，以后写二分、写归并都能免掉一类隐蔽 bug。

得到基准的索引后，把它和left交换，再走标准的挖坑法分区，这样分区函数的其余部分完全不用改：

int medianIndex = getMedianIndex(nums, left, right); swap(nums[left], nums[medianIndex]); int pivotIndex = partition(nums, left, right);

实测下来，加了这一行优化，已经有序的数组从最坏O(n²)退化被拉回到了稳定的O(n log n)，代价只是三次比较两次交换，收益非常可观。

3.3 完整代码与测试样例

我把完整实现整理成一份可以直接编译运行的程序框架：

#include <iostream> #include <vector> #include <algorithm> using namespace std; int partition(vector<int>& nums, int left, int right) { int pivot = nums[left]; while (left < right) { while (left < right && nums[right] >= pivot) right--; if (left < right) { nums[left] = nums[right]; left++; } while (left < right && nums[left] <= pivot) left++; if (left < right) { nums[right] = nums[left]; right--; } } nums[left] = pivot; return left; } int getMedianIndex(vector<int>& nums, int left, int right) { int mid = left + (right - left) / 2; if (nums[left] > nums[mid]) swap(nums[left], nums[mid]); if (nums[left] > nums[right]) swap(nums[left], nums[right]); if (nums[mid] > nums[right]) swap(nums[mid], nums[right]); return mid; } void quickSort(vector<int>& nums, int left, int right) { if (left >= right) return; int medianIndex = getMedianIndex(nums, left, right); swap(nums[left], nums[medianIndex]); int pivotIndex = partition(nums, left, right); quickSort(nums, left, pivotIndex - 1); quickSort(nums, pivotIndex + 1, right); } int main() { vector<int> nums = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8}; quickSort(nums, 0, nums.size() - 1); for (int num : nums) { cout << num << " "; } return 0; }

这个示例中的输入数组包含了重复值、递增序列的局部、较大的跳变，覆盖了快排的常见情况。运行结果是：

1 2 3 4 5 6 7 8 9 10

3.4 三路快排：专门处理重复元素的改进版

如果面试官问“数组里全是同一个元素，你的快排性能如何”，普通快排就露怯了。因为即使三数取中，面对n个相同元素，每次分区也只能把基准归位，递归深度是n，时间退化到O(n²)。

对策是三路快排（3-way partition）：分区时把数组分成三块——小于基准、等于基准、大于基准。等于基准的元素天然归位，不需要再递归，这样大量重复元素会被直接跳过。

三路快排的核心逻辑是“双指针 + 扫描指针”：

pair<int, int> partition3Way(vector<int>& nums, int left, int right) { int pivot = nums[left]; int lt = left; // 小于区间的右边界 int rt = right; // 大于区间的左边界 int i = left + 1; while (i <= rt) { if (nums[i] < pivot) { swap(nums[i], nums[lt + 1]); lt++; i++; } else if (nums[i] > pivot) { swap(nums[i], nums[rt]); rt--; } else { i++; } } swap(nums[left], nums[lt]); return {lt, rt}; }

实现时有一个容易被绕晕的点：lt初始化为left，i从left + 1开始扫描。当遇到小于基准的元素时，把它交换到lt + 1位置（因为lt位置放的是基准的替身），然后lt右移、i继续。遇到大于基准的元素时，把它交换到rt位置，但此时i不能自增——因为交换过来的元素还没被扫描过。等到循环结束时，[lt, rt]区间内全是等于基准的值，返回这个区间后，递归只需要处理[left, lt-1]和[rt+1, right]。

三路快排处理全重复数组的时间复杂度是O(n)，只用一趟扫描就完成了排序，这就是它能在大量重复数据场景下胜出的原因。多功能排序场景下，这个改进是真正的救场方案。

4. 常见问题与排查技巧实录

4.1 越界与死循环问题

问题：内层循环越界访问。

排查思路：先看有没有给内层循环加left < right条件。这是分区实现里最经典的 bug——不加条件时，如果整个区间里的元素全部大于基准，右侧扫描会一路扫描到left的左边去访问越界内存，程序立刻崩溃。

问题：分区后递归死循环。

排查思路：检查递归区间是否错误地包含了pivotIndex。如果分区返回的pivotIndex又被传进递归，某一轮分区后区间不收缩，程序就会无限递归直到栈溢出。一个简单的自检方法是打印每一轮的left、right、pivotIndex，看区间长度是否严格递减。

4.2 重复元素导致的性能退化

问题：数组中大量元素相同，普通快排跑得异常慢。

排查思路：这是比较符号没吃透导致的。普通快排如果用严格不等号分区，所有等于基准的元素会被反复交换、反复参与递归，性能直接崩盘。解决方案要么是改成>=和<=，要么直接上三路快排。

下面是我整理的快排常见问题速查表：

4.3 调试验证技巧

快排调试有个很实用的笨办法：在分区函数开头打印当前处理的区间和数组状态，看每次分区后基准是否真的归位。我当时排查一个诡异乱序问题时，就是通过打印每一步的数组内容，发现是getMedianIndex交换了nums[left]后，left位置的值变了，但我的pivot还是记录最初那个值，导致基准和实际分区基准不一致。

这个坑值得单独说一下：如果你先交换基准元素，再取nums[left]作为基准值，顺序搞反了就会出错。正确顺序是：先交换（让基准元素到left位置），再pivot = nums[left]。同理，如果用三数取中，一定要先做交换，再做pivot赋值，否则基准值就是错的。

验证快排正确性，可以写一个简单的对拍测试：随机生成大量数组，用标准库的sort排一遍，再和自己写的快排排一遍，比较结果是否一致。再验证性能，就生成已经有序、逆序、全部重复、随机四类数据，分别跑一遍看时间差异和递归深度。这套流程能从功能和性能两个维度把你的实现压榨到位。

5. 快排的工程化思考与写在最后的经验

代码能跑只是第一步。在真实场景里写快排，还有一个细节：递归深度。C++默认的函数调用栈不是无限深，如果递归深度达到n数量级，栈溢出是必然的。三数取中能极大缓解这个问题，但严格来说，最坏情况依然存在。更激进的工程方案是把递归改成显式栈模拟，或者在区间长度小于某个阈值（比如 16）时，切换到插入排序——这算是一个很常用的工程优化，能减少大量小而浅的递归调用开销。

阈值切换插入排序的原理很简单：当区间很短时，元素基本接近有序，插入排序的常数极小；而快排递归和分区的固定开销反而更重。实测下来，阈值设在 10 到 20 之间能获得肉眼可见的性能提升。这个优化其实是工业级排序库的标配思路，标准库内部排序也用了类似的手段。

我个人在实际调试中感受最深的一点是：快排的边界条件必须用“不变量”去验证，而不是靠试运气。每次写分区循环时，问自己一句：“这个循环结束时，left左边是否都不大于基准，right右边是否都不小于基准？”如果答案是肯定的，代码基本都是对的。

最后再分享一个小技巧：调试分区函数时，可以手工选一组小数组，比如{3, 1, 2, 4}，在纸上模拟一遍挖坑过程，对应着代码一行一行看，很快就能定位问题。很多快排的隐蔽 bug，都是这样用最原始的人肉调试法抓出来的。

快排不是一个“背下来就完事”的算法，它的每个调优点背后都连着数据结构、内存访问模式、递归机制这些底层知识。把这篇里的每个细节亲手验证一遍，你对分治的理解深度会和之前完全不在一个层级。