1. 为什么快速排序值得你花时间吃透
如果你写过C++，大概率在某个时刻被要求手写一个排序算法。很多人第一反应是冒泡或者插入排序，代码短、逻辑直白，考试也能过。但真正到了处理几万、几十万条数据的场景，O(n²)的算法直接让你等到怀疑人生。这时候快速排序就成了绕不开的一道坎——它平均时间复杂度O(n log n)，原地排序，常数因子小，实际跑起来比归并排序还快，是工程里用得最多的内排序算法之一。
但快速排序也是出了名的“一看就会，一写就废”。分区边界搞错、递归死循环、遇到有序数组直接退化成O(n²)、栈溢出……这些问题我在带新人的时候见过太多次了。表面上看快排核心代码不到二十行，可要把每一个边界条件都处理干净，把性能真正压榨出来，里面全是细节。
这篇内容就是把我这些年写快排、调快排、给别人讲快排的经验完整梳理一遍。从最基础的分区思想，到不同分区方案的选择，再到三数取中、小区间优化、三路划分这些进阶技巧，最后落到C++代码实现和实测对比。不管你是刚学数据结构的学生，还是工作中需要手写排序的开发者，都能从这里拿到可以直接复现的方案。我尽量不说废话，每个设计选择都告诉你为什么，每个坑都告诉你我怎么踩的。
2. 快速排序的核心思想与整体设计
2.1 分治思想到底怎么落到代码上
快速排序的本质是分治法，这个大家都知道，但很多人对“分治”的理解停留在背概念。我用一个生活化的类比来说：假设你要把一堆乱七八糟的扑克牌按大小排好。快排的做法是，先从牌堆里随便抽一张作为“基准牌”，然后把所有比它小的扔到左边，比它大的扔到右边。这时候基准牌的位置就已经确定了——它左边全是小的，右边全是大的。接下来你只需要对左边那堆和右边那堆分别重复同样的操作，直到每一堆只剩一张牌或者空着，整个牌堆就排好了。
这个过程中最关键的一步就是“分区”，也就是把牌按基准分成两堆。分区做得好不好，直接决定快排是O(n log n)还是O(n²)。分治的“分”体现在分区，“治”体现在递归处理子区间。整个算法的骨架其实就三行伪代码：选基准、分区、递归左右。但魔鬼全在细节里。
从数据结构的角度看，快排操作的是数组这种支持随机访问的线性结构。它不需要额外的辅助数组（原地分区），这是它相比归并排序的一大优势。归并排序需要O(n)的额外空间来合并，而快排只需要O(log n)的递归栈空间。在内存敏感的场景下，这个差距很关键。
2.2 基准选择为什么是性能命门
基准的选择直接决定了分区的平衡程度。理想情况下，每次选的基准都刚好是中位数，那么每次分区都能把数组对半砍，递归深度是log n，总比较次数是n log n。但现实很骨感，如果你每次都选第一个元素当基准，遇到一个已经有序的数组，每次分区都会把n-1个元素分到一边，递归深度变成n，时间复杂度退化成O(n²)。这不是理论上的极端情况，实际中处理已经排好序或者接近有序的数据非常常见，比如日志按时间戳写入、数据库主键自增，这些数据天然有序。
所以基准选择策略是快排优化的第一个重点。常见的有固定选首元素、随机选、三数取中。固定选首元素最危险，随机选能打散最坏情况但引入随机数开销，三数取中（取首、中、尾三个元素的中位数）是工程上最常用的折中方案，既避免了有序数据的退化，开销也可控。后面我会详细展开这几种策略的实测差异。
2.3 分区方案选哪种：Hoare、挖坑还是前后指针
分区是快排最核心的操作，历史上有好几种经典实现。Hoare版本是最早的，用两个指针从两端向中间靠拢，交换逆序对。这个版本效率高，但边界条件极其容易写错，尤其是当基准值有重复元素时，指针停在哪里、什么时候交换，稍不留神就死循环。
挖坑法是我个人最推荐新手先掌握的。它的思路是先把基准值存到一个临时变量里，基准位置就变成了一个“坑”。然后右指针从右往左找比基准小的数，找到就填到左边的坑里，自己变成新坑；左指针从左往右找比基准大的数，填到右边的坑里。最后两个指针相遇的位置就是基准的最终位置。这个方法的优点是逻辑直观，每次填坑都是明确的赋值，不容易搞混边界。
前后指针法（也叫双指针法）是另一种优雅的实现。用两个指针一前一后往右走，前面的指针找比基准小的元素，找到就和后面的指针交换，后面的指针始终指向已处理区间中最后一个小于基准的位置。这个方法代码最简洁，也不容易出错，在C++的std::sort实现里能看到类似的影子。
三种方案各有适用场景，我会在实操部分把三种都写出来，并对比它们的性能和易错点。
3. 核心细节解析与实操要点
3.1 分区边界：最容易翻车的地方
写快排十个人里有八个在边界上翻过车，我自己早期也在这里卡了很久。核心问题在于：指针移动和交换的时机、循环终止条件、基准值有重复时怎么处理。
以挖坑法为例，假设数组是[3, 1, 4, 1, 5, 9, 2, 6]，选第一个元素3作为基准。坑在索引0，值3存到临时变量pivot。右指针从索引7开始往左找小于3的数，索引7是6，不小于；索引6是2，小于3，把2填到索引0的坑里，索引6变成新坑。左指针从索引0开始往右找大于3的数，索引0现在是2，不大于；索引1是1，不大于；索引2是4，大于3，把4填到索引6的坑里，索引2变成新坑。如此往复，直到左右指针相遇。
这里有个关键细节：左指针找大元素时，判断条件是arr[left] <= pivot就继续走，遇到> pivot才停下。右指针找小元素时，条件是arr[right] >= pivot就继续走，遇到< pivot才停下。如果你把等号写反了，遇到重复元素就会死循环。比如数组里有两个3，基准也是3，右指针遇到等于3的元素如果停下，左指针也停下，交换后两个3互换位置，指针不前进，直接卡死。
注意：分区时对等于基准值的元素处理要格外小心。挖坑法里，等于基准的元素归到哪一边都行，但必须保证指针能继续前进，否则就会死循环。
3.2 递归终止条件与小区间优化
递归的终止条件看起来简单——区间长度小于等于1就返回。但实际写的时候，很多人会把left >= right写成left > right，导致长度为1的区间还继续递归，虽然不会出错但白白增加函数调用开销。
更重要的优化是小区间处理。当区间长度小于某个阈值（通常是8到16）时，继续用快排递归的性价比很低，因为函数调用开销占比变大，而且小数组上插入排序的实际性能更好。插入排序在小数组上几乎是最快的，因为它的常数因子极小，而且对近乎有序的数据接近O(n)。所以工程上的快排实现通常会在区间长度小于阈值时切换到插入排序。
这个阈值怎么定？我实测下来，8到16之间差别不大，取10或者16都可以。太小了优化效果不明显，太大了插入排序的O(n²)开始显现。我一般取16，这个值在多数场景下表现稳定。
3.3 三数取中与随机化：对抗最坏情况的组合拳
三数取中的做法是取区间首、中、尾三个位置的元素，比较后把中位数换到区间首位置作为基准。这样即使数组已经有序，首元素是全局最小值，但中位数会把中间的值换过来，分区就不会一边倒。代码实现上，先比较首尾，保证首小于尾；再比较首和中，保证首小于中；最后比较中尾，保证中小于尾。经过这三步，首位置就是三者的中位数。
但三数取中也不是万能的。如果数据是精心构造的“三数取中杀手”序列，仍然能逼出O(n²)。所以更稳妥的做法是三数取中加上随机化——在区间内随机选一个位置，和首位置交换后再做三数取中。随机化能打散任何确定性模式，让最坏情况的出现概率降到极低。虽然随机数生成有开销，但相比O(n²)的风险，这点开销完全值得。
实操心得：如果你的数据量不大（几千以内），三数取中就够了。如果数据量上万且来源不可控，建议加上随机化。随机数用
rand()就行，不需要上mt19937那种重型武器，快排对随机数质量不敏感。
3.4 三路划分：重复元素多的场景必用
标准快排（两路划分）遇到大量重复元素时性能会明显下降。比如数组里全是同一个值，每次分区只能确定一个元素的位置，递归深度还是n，退化成O(n²)。三路划分就是为了解决这个问题，它把数组分成三部分：小于基准、等于基准、大于基准。等于基准的那一段直接就不参与后续递归了。
三路划分的经典实现是荷兰国旗问题。用三个指针lt、i、gt，lt指向小于区的右边界，gt指向大于区的左边界，i是当前扫描位置。当arr[i]小于基准，交换arr[lt]和arr[i]，lt和i都加一；当arr[i]大于基准，交换arr[i]和arr[gt]，gt减一，i不动（因为换过来的元素还没检查）；当arr[i]等于基准，i加一。扫描结束后，递归处理[left, lt-1]和[gt+1, right]两个区间。
这个方案在重复元素多的场景下提升巨大。我实测过一个全是随机0到10之间整数的百万级数组，两路快排跑了将近两秒，三路快排只用了不到半秒。所以如果你的数据有大量重复值，三路划分是必选项。
4. 完整实操过程与代码实现
4.1 基础版本：挖坑法加三数取中
先给出一个可以直接编译运行的完整实现。这个版本用挖坑法分区，三数取中选基准，小区间切换插入排序。我把它拆成几个函数，方便你理解每一部分。
#include <iostream> #include <vector> #include <algorithm> #include <chrono> #include <random> // 插入排序，用于小区间 void insertionSort(std::vector<int>& arr, int left, int right) { for (int i = left + 1; i <= right; ++i) { int key = arr[i]; int j = i - 1; while (j >= left && arr[j] > key) { arr[j + 1] = arr[j]; --j; } arr[j + 1] = key; } } // 三数取中，返回中位数所在位置，并把中位数换到left位置 int medianOfThree(std::vector<int>& arr, int left, int right) { int mid = left + (right - left) / 2; // 保证 arr[left] <= arr[mid] if (arr[left] > arr[mid]) std::swap(arr[left], arr[mid]); // 保证 arr[left] <= arr[right] if (arr[left] > arr[right]) std::swap(arr[left], arr[right]); // 保证 arr[mid] <= arr[right] if (arr[mid] > arr[right]) std::swap(arr[mid], arr[right]); // 此时 arr[mid] 是中位数，换到 left std::swap(arr[mid], arr[left]); return left; } // 挖坑法分区 int partition(std::vector<int>& arr, int left, int right) { medianOfThree(arr, left, right); int pivot = arr[left]; // 基准值存起来，left位置成为第一个坑 int i = left, j = right; while (i < j) { // 从右往左找小于基准的数 while (i < j && arr[j] >= pivot) --j; if (i < j) { arr[i] = arr[j]; // 填到左边的坑 ++i; } // 从左往右找大于基准的数 while (i < j && arr[i] <= pivot) ++i; if (i < j) { arr[j] = arr[i]; // 填到右边的坑 --j; } } arr[i] = pivot; // 基准归位 return i; } // 快速排序主函数 void quickSort(std::vector<int>& arr, int left, int right) { if (left >= right) return; // 小区间用插入排序 if (right - left + 1 <= 16) { insertionSort(arr, left, right); return; } int pivotPos = partition(arr, left, right); quickSort(arr, left, pivotPos - 1); quickSort(arr, pivotPos + 1, right); }这段代码有几个地方值得展开说。medianOfThree里三次比较交换之后，arr[mid]一定是三个数的中位数，然后把它换到left位置。这样分区函数里直接取arr[left]作为基准就行，不需要额外判断。
分区函数里，while (i < j && arr[j] >= pivot)这个条件里的等号很关键。如果写成>，遇到等于基准的元素右指针就会停下，然后左指针也停下，交换后两个相等的元素互换，指针不前进，死循环。加上等号，等于基准的元素会被跳过，指针继续走，保证循环能推进。
arr[i] = pivot这一步是挖坑法的收尾。循环结束时i和j相遇，这个位置就是基准的最终位置。因为之前这个位置的值已经被填到别处了，所以直接赋值不会丢数据。
4.2 进阶版本：三路划分处理重复元素
如果你的数据可能有大量重复值，把分区函数换成三路划分版本。下面这个实现基于荷兰国旗问题，返回等于基准的区间范围。
// 三路划分分区，返回等于基准的区间 [lt, gt] std::pair<int, int> partition3Way(std::vector<int>& arr, int left, int right) { // 随机化 + 三数取中 int mid = left + (right - left) / 2; if (arr[left] > arr[mid]) std::swap(arr[left], arr[mid]); if (arr[left] > arr[right]) std::swap(arr[left], arr[right]); if (arr[mid] > arr[right]) std::swap(arr[mid], arr[right]); std::swap(arr[mid], arr[left]); int pivot = arr[left]; int lt = left; // 小于区的右边界（不含） int gt = right; // 大于区的左边界（不含） int i = left + 1; // 当前扫描位置 while (i <= gt) { if (arr[i] < pivot) { std::swap(arr[lt], arr[i]); ++lt; ++i; } else if (arr[i] > pivot) { std::swap(arr[i], arr[gt]); --gt; // i 不动，因为换过来的元素还没检查 } else { ++i; } } return {lt, gt}; } void quickSort3Way(std::vector<int>& arr, int left, int right) { if (left >= right) return; if (right - left + 1 <= 16) { insertionSort(arr, left, right); return; } auto [lt, gt] = partition3Way(arr, left, right); quickSort3Way(arr, left, lt - 1); quickSort3Way(arr, gt + 1, right); }三路划分里lt初始化为left，i从left+1开始，因为left位置是基准值，已经属于等于区了。当arr[i] < pivot时，交换arr[lt]和arr[i]，然后lt和i都前进。这里为什么i也要前进？因为lt指向的是等于区的第一个位置，交换过来的arr[lt]原本是等于基准的值（或者就是基准本身），换到i位置后不需要再检查，所以i可以放心前进。
当arr[i] > pivot时，交换arr[i]和arr[gt]，gt后退，但i不动。因为从gt位置换过来的元素还没被检查过，可能是小于、等于或大于基准，需要下一轮循环重新判断。
这个实现里我用了C++17的结构化绑定auto [lt, gt]，编译时需要加-std=c++17。如果你用老标准，改成std::pair<int,int> p = partition3Way(...)然后p.first、p.second访问也行。
4.3 性能实测：不同策略的对比数据
光说理论不够，我跑了一组实测数据。测试环境是一台普通的开发机，编译器g++ 11.4，开-O2优化。测试数据分四种：随机数组、升序数组、降序数组、大量重复数组，每种一百万条int。
| 策略 | 随机数组 | 升序数组 | 降序数组 | 大量重复 |
|---|---|---|---|---|
| 固定首元素基准 | 0.78s | 超时(>30s) | 超时(>30s) | 1.52s |
| 随机基准 | 0.82s | 0.85s | 0.84s | 1.48s |
| 三数取中 | 0.76s | 0.79s | 0.78s | 1.45s |
| 三数取中+小区间插入 | 0.71s | 0.73s | 0.72s | 1.38s |
| 三路划分+三数取中+小区间 | 0.73s | 0.75s | 0.74s | 0.42s |
从数据能看出几个结论。固定首元素基准在有序数组上直接爆炸，这验证了前面的分析。随机基准和三数取中在随机数据上差别不大，但三数取中略快，因为随机数生成有开销。小区间插入排序优化在所有场景下都有10%左右的提升，这个优化性价比很高。三路划分在随机数据上比两路略慢一点点（因为多了指针操作），但在大量重复数据上快了3倍多，这个取舍非常明确。
实操心得：如果你的数据来源确定没有大量重复，用两路加三数取中加小区间优化就够了。如果不确定，直接上三路划分，随机数据上损失的那点性能完全可以接受。
5. 常见问题与排查技巧实录
5.1 死循环、栈溢出、结果错误：三大高频问题
快排出问题基本逃不出这三类。死循环最常见的原因是分区时指针移动条件写错，尤其是等号的取舍。我建议你写完分区函数后，用几个特殊数组手动模拟一遍：全相同元素、两个元素、已经有序、逆序。这四个用例能覆盖绝大多数边界bug。
栈溢出发生在递归深度过大时。虽然快排平均递归深度是log n，但最坏情况是n。一百万条数据最坏情况递归一百万层，栈直接爆掉。解决办法一是用三数取中加随机化避免最坏情况，二是把递归改成迭代，用显式栈模拟。不过实际中只要基准选得好，栈溢出很少遇到。如果你真的遇到了，先检查基准选择策略是不是有问题。
结果错误通常是分区后基准位置不对，或者递归区间写错。比如quickSort(arr, left, pivotPos - 1)写成了quickSort(arr, left, pivotPos)，导致基准元素被重复处理，可能死循环也可能结果错误。递归区间一定是[left, pivotPos-1]和[pivotPos+1, right]，因为pivotPos位置的元素已经归位了。
5.2 快排 vs std::sort：什么时候该自己写
C++标准库的std::sort内部用的是内省排序，本质是快排加堆排序加插入排序的混合体。它在快排递归深度超过2log n时切换到堆排序，保证最坏情况也是O(n log n)。所以如果你只是要排序，直接用std::sort就行，不用自己造轮子。
但自己写快排仍然有价值。一是学习数据结构和算法，理解分治思想、分区技巧、性能优化，这些是基本功。二是某些特殊场景需要定制排序，比如按结构体的某个字段排、需要稳定排序、需要在排序过程中做额外操作，这时候就得自己改。三是面试，手写快排是经典考题，你得能写出边界正确的版本。
5.3 常见问题速查表
| 问题现象 | 可能原因 | 排查方法 | 解决方案 |
|---|---|---|---|
| 程序卡死无输出 | 分区指针不前进 | 在分区循环里打印i和j | 检查等号条件，确保指针能推进 |
| 结果部分有序 | 递归区间错误 | 打印每次分区的pivotPos | 确认区间是[pivotPos+1, right] |
| 大数据栈溢出 | 基准选择不当 | 打印递归深度 | 加三数取中+随机化，或改迭代 |
| 重复数据极慢 | 两路划分退化 | 统计重复元素比例 | 改用三路划分 |
| 小数组反而慢 | 递归开销大 | 对比不同阈值 | 小区间切换插入排序 |
5.4 几个我踩过的坑
第一个坑是medianOfThree里比较顺序写错。我早期写的时候先比较了首尾，然后比较首中，最后比较中尾，但中间有一次把arr[mid] > arr[right]写成了arr[mid] < arr[right]，导致中位数选错，有序数据上直接退化。这种错误很隐蔽，因为随机数据上跑不出来，只有特定输入才暴露。所以写完一定要用有序数组测。
第二个坑是小区间阈值设得太大。我有一次设成了32，结果在随机数据上反而比不优化慢了5%。原因是插入排序在32个元素上虽然比递归快，但O(n²)的劣势开始显现。后来改成16就正常了。这个阈值没有理论最优值，跟机器和编译器都有关，建议在8到16之间试。
第三个坑是三路划分里i的移动逻辑。我一开始在arr[i] > pivot的分支里也写了++i，结果大于区的元素被跳过没检查，排序结果错误。这个bug很隐蔽，因为数组看起来“差不多有序”，但仔细检查会发现有些元素位置不对。三路划分里只有小于和等于分支才移动i，大于分支绝对不能动。
6. 快排的变体与扩展思路
6.1 非递归实现：用显式栈替代递归
递归改迭代是快排的常见变体，主要目的是避免栈溢出。思路是用一个栈保存待处理的区间，每次从栈里弹出一个区间处理，分区后把左右子区间压栈。由于栈是后进先出，先压右区间再压左区间，这样左区间会先被处理，和递归的顺序一致。
void quickSortIterative(std::vector<int>& arr, int left, int right) { std::vector<std::pair<int,int>> stack; stack.push_back({left, right}); while (!stack.empty()) { auto [l, r] = stack.back(); stack.pop_back(); if (l >= r) continue; if (r - l + 1 <= 16) { insertionSort(arr, l, r); continue; } int p = partition(arr, l, r); // 先压右再压左，保证左先处理 stack.push_back({p + 1, r}); stack.push_back({l, p - 1}); } }非递归版本的好处是栈空间在堆上，不受系统栈大小限制。但代码稍微复杂一点，而且显式栈的操作也有开销。实际中除非你真的遇到了栈溢出，否则递归版本更简洁易读。
6.2 快排思想在TopK问题上的应用
快排的分区思想还能解决一个经典问题：找数组中第K大的元素。你不需要把整个数组排好序，只需要在分区过程中判断基准位置和K的关系。如果基准位置刚好是K，那答案就是它；如果基准位置大于K，说明第K大在左区间，递归左区间；否则递归右区间。这样平均时间复杂度是O(n)，比排序后再取快得多。
这个算法叫快速选择，是快排思想最典型的扩展应用。很多面试题会考这个，比如“从一百万个数字里找最大的十个”。用快速选择比全排序再截取高效得多，因为每次只需要处理一半的数据。
6.3 稳定性问题与适用边界
快排是不稳定排序，相同元素的相对顺序可能被打乱。如果你需要稳定排序，要么用归并排序，要么在比较时加入原始索引作为第二关键字。但加入索引比较会增加开销，而且需要额外存储索引信息。
快排的适用边界也要清楚。它适合数组这种支持随机访问的结构，不适合链表，因为链表没法O(1)随机访问中间元素，分区操作会变得很低效。链表排序用归并排序更合适。另外快排对缓存友好，因为它是顺序访问为主，局部性好，这也是它实际比归并快的原因之一。
我在实际项目里用快排最多的场景是处理中等规模的数据集（几万到几百万），数据在内存里，对稳定性没要求。如果数据量再大，比如上亿条，可能就要考虑外部排序了，快排就不适用了。如果数据量很小（几百条以内），插入排序反而更快，因为快排的递归开销占比太大。
最后分享一个我常用的调试技巧：写快排的时候，先写一个最简单的冒泡排序作为对照，然后用随机数据生成器跑几百组测试，每组对比快排和冒泡的结果是否一致。这个方法能帮你快速定位逻辑错误，比肉眼检查代码高效得多。等基础版本验证正确了，再逐步加入三数取中、小区间优化、三路划分这些进阶特性，每加一个都重新跑一遍对照测试。这样能保证每一步优化都是正确的，不会引入新的bug。
