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 4right继续向左扫描遇到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(vectorint 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::vectorint而不是 C 风格数组。这不是摆架子而是vector自带长度信息区间参数只要传left和right就够了不用再额外传size。更重要的是vector的底层是连续内存快排这种强 cache 友好的算法在vector上能发挥出全部性能。用裸数组当然也能写但当你递归拆分区间时begin()和end()的指针计算容易让你在边界条件里迷失方向。3. 实操过程与完整实现3.1 从分区函数到完整排序分区函数搞定后快排主体就是递归调用。每次分区返回基准的最终位置pivotIndex然后对[left, pivotIndex - 1]和[pivotIndex 1, right]两个子区间分别递归。void quickSort(vectorint 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(vectorint 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(vectorint 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(vectorint 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(vectorint 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() { vectorint 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 103.4 三路快排专门处理重复元素的改进版如果面试官问“数组里全是同一个元素你的快排性能如何”普通快排就露怯了。因为即使三数取中面对n个相同元素每次分区也只能把基准归位递归深度是n时间退化到O(n²)。对策是三路快排3-way partition分区时把数组分成三块——小于基准、等于基准、大于基准。等于基准的元素天然归位不需要再递归这样大量重复元素会被直接跳过。三路快排的核心逻辑是“双指针 扫描指针”pairint, int partition3Way(vectorint 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初始化为lefti从left 1开始扫描。当遇到小于基准的元素时把它交换到lt 1位置因为lt位置放的是基准的替身然后lt右移、i继续。遇到大于基准的元素时把它交换到rt位置但此时i不能自增——因为交换过来的元素还没被扫描过。等到循环结束时[lt, rt]区间内全是等于基准的值返回这个区间后递归只需要处理[left, lt-1]和[rt1, right]。三路快排处理全重复数组的时间复杂度是O(n)只用一趟扫描就完成了排序这就是它能在大量重复数据场景下胜出的原因。多功能排序场景下这个改进是真正的救场方案。4. 常见问题与排查技巧实录4.1 越界与死循环问题问题内层循环越界访问。排查思路先看有没有给内层循环加left right条件。这是分区实现里最经典的 bug——不加条件时如果整个区间里的元素全部大于基准右侧扫描会一路扫描到left的左边去访问越界内存程序立刻崩溃。问题分区后递归死循环。排查思路检查递归区间是否错误地包含了pivotIndex。如果分区返回的pivotIndex又被传进递归某一轮分区后区间不收缩程序就会无限递归直到栈溢出。一个简单的自检方法是打印每一轮的left、right、pivotIndex看区间长度是否严格递减。4.2 重复元素导致的性能退化问题数组中大量元素相同普通快排跑得异常慢。排查思路这是比较符号没吃透导致的。普通快排如果用严格不等号分区所有等于基准的元素会被反复交换、反复参与递归性能直接崩盘。解决方案要么是改成和要么直接上三路快排。下面是我整理的快排常见问题速查表现象可能原因解决方向内层循环越界崩溃缺少left right限制在每个内层循环条件中补全边界判断递归死循环导致栈溢出递归区间包含了基准位置确保递归区间为[left, pivot-1]和[pivot1, right]有序数组性能退化基准选择不当引入三数取中规避最大值/最小值作基准大量重复元素性能差等于基准的元素反复参与分区改用三路快排等于区间直接跳过输出结果不稳定偶发乱序分区扫描过程中交换了基准位置检查是否在right指针扫描阶段误交换了基准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都是这样用最原始的人肉调试法抓出来的。快排不是一个“背下来就完事”的算法它的每个调优点背后都连着数据结构、内存访问模式、递归机制这些底层知识。把这篇里的每个细节亲手验证一遍你对分治的理解深度会和之前完全不在一个层级。