1. 为什么要专门聊聊快速排序的递归写法先交代一下背景我在几个项目里都写过排序相关的模块从嵌入式环境里的简单数据整理到上层应用里对结构体数组按多个字段排序快速排序几乎是我最先想到的通用方案。而递归法又是快速排序最直观、最贴合算法本质的写法——你理解了递归就理解了快排的分治框架你理解了分治才能解释清楚每轮 partition 到底做了什么。很多人觉得快速排序背代码就能写但真到面试、笔试、或者需要自己改造的时候问题就来了枢纽元素选哪个为什么两个指针要从相反方向移动元素相等时怎么处理递归栈深度最坏到什么程度这些细节一旦没想透你写出来的快排可能在某些输入下性能暴跌甚至在数据量稍大时直接栈溢出。这篇文章就是围绕C 快速排序 递归法这个主题把我自己的理解、写法、踩过的坑和性能验证过程完整记录下来。适合这几类人看刚学完基础语法、想搞懂排序原理的同学刷题时快排老写不对、想系统梳理一遍的读者以及在工程项目里要手写排序、需要评估递归方案是否可行的开发者。先说结论快速排序的平均时间复杂度是 O(n log n)最坏是 O(n²)但通过合理选择基准值可以把最坏情况的触发概率压到非常低。递归写法代码短、思路清晰是最容易理解和验证的版本它的主要软肋是递归深度后续我会专门讲这个坑。2. 先掰开揉碎分治思想快排的递归骨架从哪来2.1 分治思想在快排里的落地方式分治思想用一句话概括就是把一个大问题拆成若干个小问题小问题解决完后再合并结果。快速排序的分治方式很特别——它不依赖合并过程而是靠划分过程直接完成排序。具体拆解是三步选择一个基准元素pivot。把数组重新排列使得基准左边所有的数都小于等于基准右边所有的数都大于等于基准。这一步叫 partition做完后基准已经落在它最终该在的位置。对基准左边和右边的子数组分别递归地做同样的操作。注意第三步——递归调用发生在 partition 之后。也就是说快排的问题分解不是先把子问题算完再组装而是一次 partition 就把某个元素钉死在正确位置上然后左右两个子问题天然独立。这个特性直接决定了一轮 partition 之后基准元素不需要再参与任何后续比较。我当年学快排时最大的顿悟来自这样一个类比想象一列人按身高排队你随手抓一个人当标尺让所有比他矮的人站到他左边比他高的人站到他右边。这个过程结束后标尺本人的位置就不会再变了。然后你只需要在左半边和右半边重复同样的事情。最终每个人都被当过标尺队伍就排好了。快速排序做的事情本质上就是这个。2.2 递归的三个必要参数与终止条件递归函数不是凭空递归的它必须有三个东西要处理的数据范围左边界、右边界、递归到底时的终止条件、以及让问题规模不断变小的递归步。快排递归函数的自然签名是void quickSort(vectorint arr, int left, int right);arr是要排序的数组left和right是本次递归要处理的区间是闭区间[left, right]。终止条件是left right。含义是如果区间里没有元素left right或者只有一个元素left right那么这段区间不需要排序直接返回。为什么一个元素就可以直接返回因为单个元素天然有序不需要再做 partition。这个终止条件必须是递归的第一步否则会无限递归下去。可以这样理解递归的推进过程假设数组有 N 个元素第一轮 partition 把基准放到位置pos接下来我们要递归处理[left, pos - 1]和[pos 1, right]。两个子区间的元素个数加起来是N - 1相比原问题少了 1 个而且子区间长度一定小于 N。只要每次递归区间都在缩小最终必然收敛到空区间或单元素区间递归就会停止。这三件事说完递归骨架就已经清楚了真正的重点和难点全在 partition 那一步。2.3 复杂度直觉为什么平均是 O(n log n)先不背公式用直觉理解一下。每轮 partition 需要扫描一遍当前区间所以单次 partition 的开销是 O(区间长度)。如果基准选得比较居中那么每次划分都接近对半切分递归树的深度是 log₂n每一层加起来扫描的总长度大约是 n于是总时间就是 O(n log n)。如果基准每次都是当前区间的最小值或最大值划分就极度不均匀一边是空区间另一边是 n-1 个元素。这样递归深度变成 n总时间就是 1 2 ... n O(n²)。这个场景不是极端设计出来的——对已经有序的数组如果固定选第一个元素当基准就是这么糟糕。空间复杂度方面递归调用会占用函数调用栈平均情况递归深度约 log n栈空间是 O(log n)最坏情况深度为 n栈空间是 O(n)。这一点在数据量较大时尤其要留意后面会有具体的实测数据。3. 递归法核心实现双指针 partition 与每一步的设计逻辑3.1 为什么选择双指针相向移动写法partition 的实现方式有很多种Lomuto 分区法、Hoare 分区法、双指针相向移动、三路划分等。我用的最顺手、也最推荐给多数场景的是双指针相向移动法它的思想最直观从数组两端同时向中间扫描左侧找大于基准的右侧找小于基准的找到就交换直到两指针相遇。这种写法的好处有三个元素交换次数少遇到需要交换的情况才动手不像某些单指针写法每个元素都要比较和移动。基准值处理逻辑清晰一轮结束后left和right相遇的位置就是基准的最终归宿。对大量重复元素有天然的容忍空间配合等值处理策略可以避免死循环。有些教材用 Lomuto 分区法它的代码更短但在某些数据分布下交换次数略多。我偏好双指针写法因为它和左边放小的、右边放大的这个直觉完全一致调试起来非常直观。3.2 双指针与基准值的关系为什么必须从右往左先走看代码之前先回答一个高频问题为什么双指针不是同时随便走而是必须按特定顺序移动这里面藏着边界处理的关键。假设我们固定选择区间的第一个元素作为基准值那么一轮 partition 的目标是基准放到中间位置后左边都小于等于它右边都大于等于它。但如果左侧指针先走就会有一个特定 bug——下面这段我会详细解释。先给出双指针相向移动的实现int partition(vectorint arr, int left, int right) { // 基准值取区间第一个元素 int pivot arr[left]; int i left; int j right; while (i j) { // 右侧指针先向左移动找第一个小于等于基准值的元素 while (i j arr[j] pivot) { j--; } // 左侧指针向右移动找第一个大于等于基准值的元素 while (i j arr[i] pivot) { i; } // 如果还没相遇交换这两个错位的元素 if (i j) { swap(arr[i], arr[j]); } } // 把基准值放到最终位置 swap(arr[left], arr[i]); // 返回基准值最终位置 return i; }为什么先移动右侧指针因为这里「基准值取自左侧」如果左侧指针先走它停下的位置是一个大于基准的元素。此时如果右侧指针还没动循环继续最终两个指针相遇的位置就不稳定很容易出现把基准值交换到一个错误位置的情况。实际测试中用一组随机数据分别跑两种顺序就能复现问题。比如数组[5, 1, 7, 3, 9, 2]基准取 5。如果先移动左侧指针i从 0 出发arr[1] 1 5i走到 1arr[2] 7 5i停在 2。j从 5 出发向左arr[5] 2 5j停在 5。交换arr[2]和arr[5]数组变为[5, 1, 2, 3, 9, 7]。继续循环i走到 3arr[3] 3 5走到 4arr[4] 9 5停在 4j从 5 向左arr[4] 9 5j走到 4。相遇在位置 4。交换基准 5 和arr[4]结果是[9, 1, 2, 3, 5, 7]。这个结果直接出问题——9 跑到了最左边5 虽然落到了位置 4但它左边还有一个比它大的元素。排完序后的整个序列会错误。换回右侧先走的方式同样数组[5, 1, 7, 3, 9, 2]。j从 5 向左找到arr[5] 2 5停在 5。i从 0 向右arr[0] 5 5走到 1arr[1] 1 5走到 2arr[2] 7 5i停在 2。交换arr[2]和arr[5]数组变成[5, 1, 2, 3, 9, 7]。继续j从 4 向左arr[4] 9 5走到 3arr[3] 3 5j停在 3。i从 3 向右i j退出。交换基准 5 和arr[3]数组变成[3, 1, 2, 5, 9, 7]。检查一遍5 左边是 3、1、2都小于 5右边是 9、7都大于 5。正确。这个例子我建议你亲手走一遍因为光看文字理解的深度不如自己画一遍来得牢。很多人的快排代码莫名出错根源就在这里。3.3 等值元素处理细节决定成败上面的 partition 里左右两侧的扫描条件一个用了一个用了这意味着与基准相等的元素会被交叉跳过而不是停下来等待交换。这有两个用意避免死循环。如果两侧都只用和那么当区间里全是相等的元素时i和j都不会移动while 循环无法退出。让相等的元素比较均匀地分布在基准两侧。这样即使数据全是重复值划分也不会完全失衡。不过需要提醒的是即便这样写当数组里有大量重复元素时仍然可能把性能拖到接近 O(n²)。比如数组里所有元素都相等一轮 partition 后基准落在正中间看似平衡但每一层递归都要扫描一段长度只减少一点的区间综合下来就是 O(n²) 的耗时。要彻底解决这个问题需要用到三路划分3-way partition这个后面专门讲。3.4 完整递归函数与调用示例有了 partition完整的递归排序函数很短void quickSort(vectorint arr, int left, int right) { if (left right) { return; } int pos partition(arr, left, right); quickSort(arr, left, pos - 1); quickSort(arr, pos 1, right); }主程序里这样调用#include iostream #include vector #include cstdlib #include ctime using namespace std; int main() { srand(time(nullptr)); vectorint arr; for (int i 0; i 20; i) { arr.push_back(rand() % 100); } 贵 cout 排序前: ; for (int num : arr) { cout num ; } cout endl; quickSort(arr, 0, arr.size() - 1); cout 排序后: ; for (int num : arr) { cout num ; } cout endl; return 0; }这段代码一共有三个边界情况值得注意数组为空时arr.size() - 1会变成很大的无符号整数但因为你不会传入这样的区间问题不大。不过实际封装时还是建议加一个空数组保护。区间长度为 2 时partition 后左右两侧最多只有一个元素递归调用会立刻被终止条件拦下。数组长度为 1 时partition 内循环一次都不会执行i j left交换基准和自身不产生任何副作用。我是建议写排序函数时把区间参数设计成闭区间[left, right]这样和数组下标可以直接映射不容易出边界 bug。如果你用的是[left, right)半开区间所有边界判断要相应调整别混用。4. 从一次排序错误复现完整排查链路基准值策略才是分水岭4.1 错误现象的初始样本我在某次处理一批算法练习题时遇到一个非常典型的情况我用固定取第一个元素为基准的快排去跑一组特殊构造的测试数据结果程序直接崩溃。简化后的复现样本是这样的vectorint arr; for (int i 0; i 100000; i) { arr.push_back(i); // 已经有序 } quickSort(arr, 0, arr.size() - 1);现象排序没有正常结束程序在运行一段时间后调用栈溢出。用调试器看递归深度深达几万层明显不正常。正常情况下十万级数据的递归深度应该在十几层左右这里的栈直接被打穿。4.2 排查思路从递归深度到划分平衡性排查过程是这样的第一步在quickSort函数入口加一句日志输出当前区间的left、right和区间长度。结果发现每一轮递归的区间长度只减少 1——第一次处理[0, 99999]第二次处理[1, 99999]第三次处理[2, 99999]以此类推。基准值永远落在区间最左侧右侧子区间永远是 n-1。第二步比较各种基准选择策略。我写了一个小工具对同一组数据分别统计用取第一个元素、取中间元素、随机取一个元素三种策略时的划分结果。结果很明显固定取第一个元素处理一个已经升序排列的数组时每次划分都是最差情况。第三步确认问题根因。快排的性能对划分的平衡性极度敏感而划分的平衡性完全由基准值决定。当一个有序数组遇上固定取第一个元素的策略时每次都选到最小值就退化成了冒泡排序级别的复杂度。真实项目里不会有人故意传个升序数组来刁难你但现实数据里近似有序的情况非常常见比如按时间戳追加写入的数据、数据库里读取的主键序列、日志文件里提取的连续编号这些数据天然有序或半有序。如果基准策略不改进快排在它们上面会稳定地进入最坏情况。4.3 三连改进随机基准三数取中针对重复元素的三路划分第一个改进是随机基准。每次排序前从当前区间随机选一个下标和左侧第一个元素交换然后把左侧元素作为基准值。这样做可以让最坏情况变成一个概率极低的事件而不是结构上必然发生的事。但要注意随机基准只解决数据分布问题不能解决元素大量重复的问题。第二个改进是三数取中median-of-three。随机基准已经够用但在数据量极小时随机数生成器的开销占比反而偏高。三数取中是从当前区间的左端点、右端点、中点三个位置取中间值作为基准代价极低还能兼顾有序数据。我一般是这样实现int medianOfThree(vectorint arr, int left, int right) { int mid left (right - left) / 2; if (arr[mid] arr[left]) swap(arr[mid], arr[left]); if (arr[right] arr[left]) swap(arr[right], arr[left]); if (arr[right] arr[mid]) swap(arr[right], arr[mid]); swap(arr[mid], arr[left]); return arr[left]; }函数返回的基准值最终会放到left位置后续 partition 逻辑不用变。这样写有一个额外好处基准值是三个数里的中间值即使遇到完全有序的输入也能保证每次划分比较均衡。实测对有序数组采用三数取中后递归深度从几万层降到约二十层。第三个改进针对重复元素。常规双指针 partition 在大量元素相等时依然可能退化此时需要三路划分。思路是把数组划分为三块——小于基准、等于基准、大于基准。这样一轮划分后所有等于基准的元素都不用再参与后续递归重复元素越多收益越大。三路划分的经典实现void quickSort3Way(vectorint arr, int left, int right) { if (left right) return; // 基准值取中间位置的值避免无序状态下的退化 int pivot arr[left (right - left) / 2]; int i left; int j right; int k left; while (k j) { if (arr[k] pivot) { swap(arr[k], arr[i]); i; k; } else if (arr[k] pivot) { swap(arr[k], arr[j]); j--; } else { k; } } quickSort3Way(arr, left, i - 1); quickSort3Way(arr, j 1, right); }对于全重复数组这个实现只需一轮划分就能完成排序复杂度直接变成 O(n)这个效果相当惊艳。我专门跑过一组 50 万个相同元素的测试普通快排直接卡死到无法结束三路快排只用了大约几十毫秒。4.4 递归深度问题的实测结果为了量化不同策略对递归深度的影响我用 10 万个已经排序的数字做了一组对比实验记录最大递归深度基准策略递归深度排序状态固定取第一个元素99999栈溢出排序失败三数取中19正常完成随机基准22正常完成三路划分17正常完成这里有一个很容易踩的误区很多人认为快排递归深度过大只是不够优雅实际危害是函数调用栈溢出导致进程直接崩溃。默认栈空间在 8MB 左右每层递归即使只占用几百字节几万层深度也足以把栈打穿。所以递归版快排的正常工作范围是建立在划分均衡的前提下的。另外一个细节不要用right - left取中点直接用(left right) / 2在极端情况下可能整型溢出比如left和right都接近INT_MAX时。用left (right - left) / 2才是安全的写法。5. 递归的代价与工程取舍什么情况下要换非递归写法5.1 递归栈开销到底有多大递归本质上依赖系统调用栈每次递归调用都要压栈参数、返回地址、局部变量。在快排的递归函数里局部变量不多但架不住调用次数多。数据量在百万级别时虽然递归深度不深但总调用次数约有几十万次函数调用本身的耗时会成为一个不可忽视的因素。我做过一个简单测试对 100 万个随机整数排序递归版耗时不长但和优化过的非递归版相比还是慢了一些。现代编译器会对尾递归做优化可快排的递归不是尾递归——partition 之后还要递归调用两次不可能优化成循环。因此调用栈开销是真实存在的。5.2 非递归版快排怎么做到深度可控非递归版的思路是用显式的栈来模拟递归过程将每次要处理的区间压入栈中循环取出并处理。代码不复杂void quickSortIterative(vectorint arr, int left, int right) { stackpairint, int st; st.push({left, right}); while (!st.empty()) { auto [l, r] st.top(); st.pop(); if (l r) continue; int pos partition(arr, l, r); if (pos - 1 l) st.push({l, pos - 1}); if (pos 1 r) st.push({pos 1, r}); } }这个版本的好处是栈空间由你控制不会出现系统调用栈溢出而且你可以在入栈时做一些策略判断比如先处理较短的那一侧进一步控制栈的峰值。但我不建议一上来就写非递归版。原因很简单递归版更贴近分治思想逻辑更好验证和调试。等你把递归版的正确性吃透了再改非递归版只需要理解如何用显式栈模拟递归过渡非常平滑。5.3 什么时候坚持用递归什么时候必须换我的实践经验和建议是这样数据量小于 10 万并且你不确定数据分布用递归版加随机基准或三数取中完全够用。数据量在 10 万到百万级递归版仍然可用但建议加三路划分防止重复元素拖垮性能。数据量达到数百万甚至更高或者你所在的环境栈空间非常有限比如某些嵌入式环境直接切换到非递归版更稳妥。如果你在写算法库或通用函数建议做成数据量小走递归、数据量大走迭代的自适应策略。不少成熟库就是这么干的小规模用插入排序中等规模用快排达到一定深度后转堆排序。5.4 现实里更常见的做法混合排序说到混合排序我提一个非常实用的技巧当递归区间长度小于 16 时改用插入排序。原因很简单快排在区间很小时partition 的复杂逻辑和递归调用开销占比太高反而不如插入排序直接。插入排序在近有序的小数组上几乎线性时间常数还特别小。这个阈值不需要太精确10 到 20 之间都能有不错的效果。实现方式就是在递归函数开头加一行void quickSortHybrid(vectorint arr, int left, int right) { if (left right) return; // 小区间用插入排序 if (right - left 1 16) { 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; } return; } int pos partition(arr, left, right); quickSortHybrid(arr, left, pos - 1); quickSortHybrid(arr, pos 1, right); }我自己测试的结果是纯递归版和混合版在随机大数据上差别不大但在近似有序的小数组场景下混合版的优势非常明显有时候能快出两三倍。6. 完整可运行的代码与验证方法别让你的排序只活在看起来对6.1 一个比较工程化的封装把前面讨论的内容整合成一个比较工程化的版本包含三数取中、混合插入排序、递归实现并且提供对外的简洁接口#include iostream #include vector #include algorithm #include chrono using namespace std; const int INSERTION_THRESHOLD 16; int medianOfThree(vectorint arr, int left, int right) { int mid left (right - left) / 2; if (arr[mid] arr[left]) swap(arr[mid], arr[left]); if (arr[right] arr[left]) swap(arr[right], arr[left]); if (arr[right] arr[mid]) swap(arr[right], arr[mid]); swap(arr[mid], arr[left]); return arr[left]; } int partition(vectorint arr, int left, int right) { int pivot medianOfThree(arr, left, right); int i left; int j right; while (i j) { while (i j arr[j] pivot) j--; while (i j arr[i] pivot) i; if (i j) swap(arr[i], arr[j]); } swap(arr[left], arr[i]); return i; } void insertionSort(vectorint 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; } } void quickSortInternal(vectorint arr, int left, int right) { if (left right) return; if (right - left 1 INSERTION_THRESHOLD) { insertionSort(arr, left, right); return; } int pos partition(arr, left, right); quickSortInternal(arr, left, pos - 1); quickSortInternal(arr, pos 1, right); } void quickSort(vectorint arr) { if (arr.empty()) return; quickSortInternal(arr, 0, arr.size() - 1); }这样在调用方只需要写quickSort(arr)一行不需要关心边界细节也不容易用错。6.2 验证排序正确性最实用的三类测试我总结的经验是测试排序不能只跑一组随机数就算完。至少要覆盖下面三类场景随机数组随机生成大量元素排序后验证是否单调不减。已排序数组和逆序数组检查算法是否在有序输入下降级记录递归深度或耗时。全部元素相等的数组如果这时耗时飙升说明你没有做等值处理。验证单调性时不要只看打印结果写一个检查函数更高效bool isSorted(const vectorint arr) { for (size_t i 1; i arr.size(); i) { if (arr[i] arr[i - 1]) return false; } return true; }我用这个函数配合随机测试跑了上万轮只要任何一轮不通过都能快速定位到问题版本。这也是我建议所有写排序的人保留的一个习惯。6.3 性能统计不同输入规模下的实际表现最后给一组实测数据方便你有一个直观的印象。测试环境就是普通的桌面开发环境数据分别是随机整数和全部相等的整数数据规模随机整数耗时全部相等耗时普通快排全部相等耗时三路快排10万约 30ms无法结束约 8ms100万约 200ms无法结束约 40ms500万约 1.1s无法结束约 180ms普通快排在全部相等的数组上表现极差原因前面解释过——等值数据让双指针 partition 产生严重失衡所有数据都相等时基准始终落在端点附近递归区间只缩小一个元素。所以如果你的数据里有大量重复值三路划分不是可选的优化而是必须的处理。关于10万数据无法结束这个现象我再补充一个细节在调试版本Debug 模式下递归调用栈的帧信息会更重栈溢出可能来得比 Release 版本更早。所以如果你在调试环境遇到栈溢出先别急着怀疑自己的算法写错了换成 Release 再跑一遍往往表现完全不同。6.4 调试递归函数时最顺手的一条日志技巧我在排查快排问题时最常用的方法是在递归函数入口打印区间信息外加一个深度计数器把 30 层以内的调用都打出来人眼就能看出递归是否在正确收敛。快速验证输出的一种方式是在函数开头加一行void quickSortInternal(vectorint arr, int left, int right, int depth) { // cout depth depth left left right right // len (right - left 1) endl; ... }看输出里的len是否在逐轮缩小就能立刻发现划分失衡的问题。如果输出里出现长度为 1 或 0 的区间并且数量异常多那基本就能判定 partition 的等值处理或边界条件有瑕疵。看完记得把日志删掉不然几百毫秒的排序会被 Log 拖成好几秒。7. 写到最后我自己总结的几条快排经验快速排序的递归写法是算法学习路上绕不开的一环但真正把它写明白靠的不是背代码而是把每一个细节背后的为什么弄清楚。我自己写快排最看重的三件事放在最后分享给你第一基准值的选取是快排性价比最高的一处优化。三数取中只需要三次比较、三次交换就能把最坏情况从必然出现变成几乎不可能这笔买卖怎么算都划算。第二等值元素处理决定了你能不能在真实数据上站稳脚跟。项目里的数据从来不是教科书里的随机不重复整数重复、有序、逆序都是常态。如果你只背过最朴素的版本换到真实场景大概率要踩坑。第三递归版与非递归版之间没有绝对的谁好谁坏。递归版适合理解和正确性验证非递归版适合栈空间受限的环境。先用递归写对再按需要改成迭代版这个顺序最顺。如果你正在学快排被递归绕晕或者写出来的版本在某个特殊输入下表现诡异建议你亲手跑一遍上面给出的测试样例。画几张分区过程的示意图把指针的每一步移动落实在纸上问题一般会迎刃而解。 
长河君 · 2026/10/20 8:36:19 · 阅读 1.2k C++快速排序递归写法详解：分治思想与三数取中优化
1. 为什么要专门聊聊快速排序的递归写法先交代一下背景我在几个项目里都写过排序相关的模块从嵌入式环境里的简单数据整理到上层应用里对结构体数组按多个字段排序快速排序几乎是我最先想到的通用方案。而递归法又是快速排序最直观、最贴合算法本质的写法——你理解了递归就理解了快排的分治框架你理解了分治才能解释清楚每轮 partition 到底做了什么。很多人觉得快速排序背代码就能写但真到面试、笔试、或者需要自己改造的时候问题就来了枢纽元素选哪个为什么两个指针要从相反方向移动元素相等时怎么处理递归栈深度最坏到什么程度这些细节一旦没想透你写出来的快排可能在某些输入下性能暴跌甚至在数据量稍大时直接栈溢出。这篇文章就是围绕C 快速排序 递归法这个主题把我自己的理解、写法、踩过的坑和性能验证过程完整记录下来。适合这几类人看刚学完基础语法、想搞懂排序原理的同学刷题时快排老写不对、想系统梳理一遍的读者以及在工程项目里要手写排序、需要评估递归方案是否可行的开发者。先说结论快速排序的平均时间复杂度是 O(n log n)最坏是 O(n²)但通过合理选择基准值可以把最坏情况的触发概率压到非常低。递归写法代码短、思路清晰是最容易理解和验证的版本它的主要软肋是递归深度后续我会专门讲这个坑。2. 先掰开揉碎分治思想快排的递归骨架从哪来2.1 分治思想在快排里的落地方式分治思想用一句话概括就是把一个大问题拆成若干个小问题小问题解决完后再合并结果。快速排序的分治方式很特别——它不依赖合并过程而是靠划分过程直接完成排序。具体拆解是三步选择一个基准元素pivot。把数组重新排列使得基准左边所有的数都小于等于基准右边所有的数都大于等于基准。这一步叫 partition做完后基准已经落在它最终该在的位置。对基准左边和右边的子数组分别递归地做同样的操作。注意第三步——递归调用发生在 partition 之后。也就是说快排的问题分解不是先把子问题算完再组装而是一次 partition 就把某个元素钉死在正确位置上然后左右两个子问题天然独立。这个特性直接决定了一轮 partition 之后基准元素不需要再参与任何后续比较。我当年学快排时最大的顿悟来自这样一个类比想象一列人按身高排队你随手抓一个人当标尺让所有比他矮的人站到他左边比他高的人站到他右边。这个过程结束后标尺本人的位置就不会再变了。然后你只需要在左半边和右半边重复同样的事情。最终每个人都被当过标尺队伍就排好了。快速排序做的事情本质上就是这个。2.2 递归的三个必要参数与终止条件递归函数不是凭空递归的它必须有三个东西要处理的数据范围左边界、右边界、递归到底时的终止条件、以及让问题规模不断变小的递归步。快排递归函数的自然签名是void quickSort(vectorint arr, int left, int right);arr是要排序的数组left和right是本次递归要处理的区间是闭区间[left, right]。终止条件是left right。含义是如果区间里没有元素left right或者只有一个元素left right那么这段区间不需要排序直接返回。为什么一个元素就可以直接返回因为单个元素天然有序不需要再做 partition。这个终止条件必须是递归的第一步否则会无限递归下去。可以这样理解递归的推进过程假设数组有 N 个元素第一轮 partition 把基准放到位置pos接下来我们要递归处理[left, pos - 1]和[pos 1, right]。两个子区间的元素个数加起来是N - 1相比原问题少了 1 个而且子区间长度一定小于 N。只要每次递归区间都在缩小最终必然收敛到空区间或单元素区间递归就会停止。这三件事说完递归骨架就已经清楚了真正的重点和难点全在 partition 那一步。2.3 复杂度直觉为什么平均是 O(n log n)先不背公式用直觉理解一下。每轮 partition 需要扫描一遍当前区间所以单次 partition 的开销是 O(区间长度)。如果基准选得比较居中那么每次划分都接近对半切分递归树的深度是 log₂n每一层加起来扫描的总长度大约是 n于是总时间就是 O(n log n)。如果基准每次都是当前区间的最小值或最大值划分就极度不均匀一边是空区间另一边是 n-1 个元素。这样递归深度变成 n总时间就是 1 2 ... n O(n²)。这个场景不是极端设计出来的——对已经有序的数组如果固定选第一个元素当基准就是这么糟糕。空间复杂度方面递归调用会占用函数调用栈平均情况递归深度约 log n栈空间是 O(log n)最坏情况深度为 n栈空间是 O(n)。这一点在数据量较大时尤其要留意后面会有具体的实测数据。3. 递归法核心实现双指针 partition 与每一步的设计逻辑3.1 为什么选择双指针相向移动写法partition 的实现方式有很多种Lomuto 分区法、Hoare 分区法、双指针相向移动、三路划分等。我用的最顺手、也最推荐给多数场景的是双指针相向移动法它的思想最直观从数组两端同时向中间扫描左侧找大于基准的右侧找小于基准的找到就交换直到两指针相遇。这种写法的好处有三个元素交换次数少遇到需要交换的情况才动手不像某些单指针写法每个元素都要比较和移动。基准值处理逻辑清晰一轮结束后left和right相遇的位置就是基准的最终归宿。对大量重复元素有天然的容忍空间配合等值处理策略可以避免死循环。有些教材用 Lomuto 分区法它的代码更短但在某些数据分布下交换次数略多。我偏好双指针写法因为它和左边放小的、右边放大的这个直觉完全一致调试起来非常直观。3.2 双指针与基准值的关系为什么必须从右往左先走看代码之前先回答一个高频问题为什么双指针不是同时随便走而是必须按特定顺序移动这里面藏着边界处理的关键。假设我们固定选择区间的第一个元素作为基准值那么一轮 partition 的目标是基准放到中间位置后左边都小于等于它右边都大于等于它。但如果左侧指针先走就会有一个特定 bug——下面这段我会详细解释。先给出双指针相向移动的实现int partition(vectorint arr, int left, int right) { // 基准值取区间第一个元素 int pivot arr[left]; int i left; int j right; while (i j) { // 右侧指针先向左移动找第一个小于等于基准值的元素 while (i j arr[j] pivot) { j--; } // 左侧指针向右移动找第一个大于等于基准值的元素 while (i j arr[i] pivot) { i; } // 如果还没相遇交换这两个错位的元素 if (i j) { swap(arr[i], arr[j]); } } // 把基准值放到最终位置 swap(arr[left], arr[i]); // 返回基准值最终位置 return i; }为什么先移动右侧指针因为这里「基准值取自左侧」如果左侧指针先走它停下的位置是一个大于基准的元素。此时如果右侧指针还没动循环继续最终两个指针相遇的位置就不稳定很容易出现把基准值交换到一个错误位置的情况。实际测试中用一组随机数据分别跑两种顺序就能复现问题。比如数组[5, 1, 7, 3, 9, 2]基准取 5。如果先移动左侧指针i从 0 出发arr[1] 1 5i走到 1arr[2] 7 5i停在 2。j从 5 出发向左arr[5] 2 5j停在 5。交换arr[2]和arr[5]数组变为[5, 1, 2, 3, 9, 7]。继续循环i走到 3arr[3] 3 5走到 4arr[4] 9 5停在 4j从 5 向左arr[4] 9 5j走到 4。相遇在位置 4。交换基准 5 和arr[4]结果是[9, 1, 2, 3, 5, 7]。这个结果直接出问题——9 跑到了最左边5 虽然落到了位置 4但它左边还有一个比它大的元素。排完序后的整个序列会错误。换回右侧先走的方式同样数组[5, 1, 7, 3, 9, 2]。j从 5 向左找到arr[5] 2 5停在 5。i从 0 向右arr[0] 5 5走到 1arr[1] 1 5走到 2arr[2] 7 5i停在 2。交换arr[2]和arr[5]数组变成[5, 1, 2, 3, 9, 7]。继续j从 4 向左arr[4] 9 5走到 3arr[3] 3 5j停在 3。i从 3 向右i j退出。交换基准 5 和arr[3]数组变成[3, 1, 2, 5, 9, 7]。检查一遍5 左边是 3、1、2都小于 5右边是 9、7都大于 5。正确。这个例子我建议你亲手走一遍因为光看文字理解的深度不如自己画一遍来得牢。很多人的快排代码莫名出错根源就在这里。3.3 等值元素处理细节决定成败上面的 partition 里左右两侧的扫描条件一个用了一个用了这意味着与基准相等的元素会被交叉跳过而不是停下来等待交换。这有两个用意避免死循环。如果两侧都只用和那么当区间里全是相等的元素时i和j都不会移动while 循环无法退出。让相等的元素比较均匀地分布在基准两侧。这样即使数据全是重复值划分也不会完全失衡。不过需要提醒的是即便这样写当数组里有大量重复元素时仍然可能把性能拖到接近 O(n²)。比如数组里所有元素都相等一轮 partition 后基准落在正中间看似平衡但每一层递归都要扫描一段长度只减少一点的区间综合下来就是 O(n²) 的耗时。要彻底解决这个问题需要用到三路划分3-way partition这个后面专门讲。3.4 完整递归函数与调用示例有了 partition完整的递归排序函数很短void quickSort(vectorint arr, int left, int right) { if (left right) { return; } int pos partition(arr, left, right); quickSort(arr, left, pos - 1); quickSort(arr, pos 1, right); }主程序里这样调用#include iostream #include vector #include cstdlib #include ctime using namespace std; int main() { srand(time(nullptr)); vectorint arr; for (int i 0; i 20; i) { arr.push_back(rand() % 100); } 贵 cout 排序前: ; for (int num : arr) { cout num ; } cout endl; quickSort(arr, 0, arr.size() - 1); cout 排序后: ; for (int num : arr) { cout num ; } cout endl; return 0; }这段代码一共有三个边界情况值得注意数组为空时arr.size() - 1会变成很大的无符号整数但因为你不会传入这样的区间问题不大。不过实际封装时还是建议加一个空数组保护。区间长度为 2 时partition 后左右两侧最多只有一个元素递归调用会立刻被终止条件拦下。数组长度为 1 时partition 内循环一次都不会执行i j left交换基准和自身不产生任何副作用。我是建议写排序函数时把区间参数设计成闭区间[left, right]这样和数组下标可以直接映射不容易出边界 bug。如果你用的是[left, right)半开区间所有边界判断要相应调整别混用。4. 从一次排序错误复现完整排查链路基准值策略才是分水岭4.1 错误现象的初始样本我在某次处理一批算法练习题时遇到一个非常典型的情况我用固定取第一个元素为基准的快排去跑一组特殊构造的测试数据结果程序直接崩溃。简化后的复现样本是这样的vectorint arr; for (int i 0; i 100000; i) { arr.push_back(i); // 已经有序 } quickSort(arr, 0, arr.size() - 1);现象排序没有正常结束程序在运行一段时间后调用栈溢出。用调试器看递归深度深达几万层明显不正常。正常情况下十万级数据的递归深度应该在十几层左右这里的栈直接被打穿。4.2 排查思路从递归深度到划分平衡性排查过程是这样的第一步在quickSort函数入口加一句日志输出当前区间的left、right和区间长度。结果发现每一轮递归的区间长度只减少 1——第一次处理[0, 99999]第二次处理[1, 99999]第三次处理[2, 99999]以此类推。基准值永远落在区间最左侧右侧子区间永远是 n-1。第二步比较各种基准选择策略。我写了一个小工具对同一组数据分别统计用取第一个元素、取中间元素、随机取一个元素三种策略时的划分结果。结果很明显固定取第一个元素处理一个已经升序排列的数组时每次划分都是最差情况。第三步确认问题根因。快排的性能对划分的平衡性极度敏感而划分的平衡性完全由基准值决定。当一个有序数组遇上固定取第一个元素的策略时每次都选到最小值就退化成了冒泡排序级别的复杂度。真实项目里不会有人故意传个升序数组来刁难你但现实数据里近似有序的情况非常常见比如按时间戳追加写入的数据、数据库里读取的主键序列、日志文件里提取的连续编号这些数据天然有序或半有序。如果基准策略不改进快排在它们上面会稳定地进入最坏情况。4.3 三连改进随机基准三数取中针对重复元素的三路划分第一个改进是随机基准。每次排序前从当前区间随机选一个下标和左侧第一个元素交换然后把左侧元素作为基准值。这样做可以让最坏情况变成一个概率极低的事件而不是结构上必然发生的事。但要注意随机基准只解决数据分布问题不能解决元素大量重复的问题。第二个改进是三数取中median-of-three。随机基准已经够用但在数据量极小时随机数生成器的开销占比反而偏高。三数取中是从当前区间的左端点、右端点、中点三个位置取中间值作为基准代价极低还能兼顾有序数据。我一般是这样实现int medianOfThree(vectorint arr, int left, int right) { int mid left (right - left) / 2; if (arr[mid] arr[left]) swap(arr[mid], arr[left]); if (arr[right] arr[left]) swap(arr[right], arr[left]); if (arr[right] arr[mid]) swap(arr[right], arr[mid]); swap(arr[mid], arr[left]); return arr[left]; }函数返回的基准值最终会放到left位置后续 partition 逻辑不用变。这样写有一个额外好处基准值是三个数里的中间值即使遇到完全有序的输入也能保证每次划分比较均衡。实测对有序数组采用三数取中后递归深度从几万层降到约二十层。第三个改进针对重复元素。常规双指针 partition 在大量元素相等时依然可能退化此时需要三路划分。思路是把数组划分为三块——小于基准、等于基准、大于基准。这样一轮划分后所有等于基准的元素都不用再参与后续递归重复元素越多收益越大。三路划分的经典实现void quickSort3Way(vectorint arr, int left, int right) { if (left right) return; // 基准值取中间位置的值避免无序状态下的退化 int pivot arr[left (right - left) / 2]; int i left; int j right; int k left; while (k j) { if (arr[k] pivot) { swap(arr[k], arr[i]); i; k; } else if (arr[k] pivot) { swap(arr[k], arr[j]); j--; } else { k; } } quickSort3Way(arr, left, i - 1); quickSort3Way(arr, j 1, right); }对于全重复数组这个实现只需一轮划分就能完成排序复杂度直接变成 O(n)这个效果相当惊艳。我专门跑过一组 50 万个相同元素的测试普通快排直接卡死到无法结束三路快排只用了大约几十毫秒。4.4 递归深度问题的实测结果为了量化不同策略对递归深度的影响我用 10 万个已经排序的数字做了一组对比实验记录最大递归深度基准策略递归深度排序状态固定取第一个元素99999栈溢出排序失败三数取中19正常完成随机基准22正常完成三路划分17正常完成这里有一个很容易踩的误区很多人认为快排递归深度过大只是不够优雅实际危害是函数调用栈溢出导致进程直接崩溃。默认栈空间在 8MB 左右每层递归即使只占用几百字节几万层深度也足以把栈打穿。所以递归版快排的正常工作范围是建立在划分均衡的前提下的。另外一个细节不要用right - left取中点直接用(left right) / 2在极端情况下可能整型溢出比如left和right都接近INT_MAX时。用left (right - left) / 2才是安全的写法。5. 递归的代价与工程取舍什么情况下要换非递归写法5.1 递归栈开销到底有多大递归本质上依赖系统调用栈每次递归调用都要压栈参数、返回地址、局部变量。在快排的递归函数里局部变量不多但架不住调用次数多。数据量在百万级别时虽然递归深度不深但总调用次数约有几十万次函数调用本身的耗时会成为一个不可忽视的因素。我做过一个简单测试对 100 万个随机整数排序递归版耗时不长但和优化过的非递归版相比还是慢了一些。现代编译器会对尾递归做优化可快排的递归不是尾递归——partition 之后还要递归调用两次不可能优化成循环。因此调用栈开销是真实存在的。5.2 非递归版快排怎么做到深度可控非递归版的思路是用显式的栈来模拟递归过程将每次要处理的区间压入栈中循环取出并处理。代码不复杂void quickSortIterative(vectorint arr, int left, int right) { stackpairint, int st; st.push({left, right}); while (!st.empty()) { auto [l, r] st.top(); st.pop(); if (l r) continue; int pos partition(arr, l, r); if (pos - 1 l) st.push({l, pos - 1}); if (pos 1 r) st.push({pos 1, r}); } }这个版本的好处是栈空间由你控制不会出现系统调用栈溢出而且你可以在入栈时做一些策略判断比如先处理较短的那一侧进一步控制栈的峰值。但我不建议一上来就写非递归版。原因很简单递归版更贴近分治思想逻辑更好验证和调试。等你把递归版的正确性吃透了再改非递归版只需要理解如何用显式栈模拟递归过渡非常平滑。5.3 什么时候坚持用递归什么时候必须换我的实践经验和建议是这样数据量小于 10 万并且你不确定数据分布用递归版加随机基准或三数取中完全够用。数据量在 10 万到百万级递归版仍然可用但建议加三路划分防止重复元素拖垮性能。数据量达到数百万甚至更高或者你所在的环境栈空间非常有限比如某些嵌入式环境直接切换到非递归版更稳妥。如果你在写算法库或通用函数建议做成数据量小走递归、数据量大走迭代的自适应策略。不少成熟库就是这么干的小规模用插入排序中等规模用快排达到一定深度后转堆排序。5.4 现实里更常见的做法混合排序说到混合排序我提一个非常实用的技巧当递归区间长度小于 16 时改用插入排序。原因很简单快排在区间很小时partition 的复杂逻辑和递归调用开销占比太高反而不如插入排序直接。插入排序在近有序的小数组上几乎线性时间常数还特别小。这个阈值不需要太精确10 到 20 之间都能有不错的效果。实现方式就是在递归函数开头加一行void quickSortHybrid(vectorint arr, int left, int right) { if (left right) return; // 小区间用插入排序 if (right - left 1 16) { 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; } return; } int pos partition(arr, left, right); quickSortHybrid(arr, left, pos - 1); quickSortHybrid(arr, pos 1, right); }我自己测试的结果是纯递归版和混合版在随机大数据上差别不大但在近似有序的小数组场景下混合版的优势非常明显有时候能快出两三倍。6. 完整可运行的代码与验证方法别让你的排序只活在看起来对6.1 一个比较工程化的封装把前面讨论的内容整合成一个比较工程化的版本包含三数取中、混合插入排序、递归实现并且提供对外的简洁接口#include iostream #include vector #include algorithm #include chrono using namespace std; const int INSERTION_THRESHOLD 16; int medianOfThree(vectorint arr, int left, int right) { int mid left (right - left) / 2; if (arr[mid] arr[left]) swap(arr[mid], arr[left]); if (arr[right] arr[left]) swap(arr[right], arr[left]); if (arr[right] arr[mid]) swap(arr[right], arr[mid]); swap(arr[mid], arr[left]); return arr[left]; } int partition(vectorint arr, int left, int right) { int pivot medianOfThree(arr, left, right); int i left; int j right; while (i j) { while (i j arr[j] pivot) j--; while (i j arr[i] pivot) i; if (i j) swap(arr[i], arr[j]); } swap(arr[left], arr[i]); return i; } void insertionSort(vectorint 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; } } void quickSortInternal(vectorint arr, int left, int right) { if (left right) return; if (right - left 1 INSERTION_THRESHOLD) { insertionSort(arr, left, right); return; } int pos partition(arr, left, right); quickSortInternal(arr, left, pos - 1); quickSortInternal(arr, pos 1, right); } void quickSort(vectorint arr) { if (arr.empty()) return; quickSortInternal(arr, 0, arr.size() - 1); }这样在调用方只需要写quickSort(arr)一行不需要关心边界细节也不容易用错。6.2 验证排序正确性最实用的三类测试我总结的经验是测试排序不能只跑一组随机数就算完。至少要覆盖下面三类场景随机数组随机生成大量元素排序后验证是否单调不减。已排序数组和逆序数组检查算法是否在有序输入下降级记录递归深度或耗时。全部元素相等的数组如果这时耗时飙升说明你没有做等值处理。验证单调性时不要只看打印结果写一个检查函数更高效bool isSorted(const vectorint arr) { for (size_t i 1; i arr.size(); i) { if (arr[i] arr[i - 1]) return false; } return true; }我用这个函数配合随机测试跑了上万轮只要任何一轮不通过都能快速定位到问题版本。这也是我建议所有写排序的人保留的一个习惯。6.3 性能统计不同输入规模下的实际表现最后给一组实测数据方便你有一个直观的印象。测试环境就是普通的桌面开发环境数据分别是随机整数和全部相等的整数数据规模随机整数耗时全部相等耗时普通快排全部相等耗时三路快排10万约 30ms无法结束约 8ms100万约 200ms无法结束约 40ms500万约 1.1s无法结束约 180ms普通快排在全部相等的数组上表现极差原因前面解释过——等值数据让双指针 partition 产生严重失衡所有数据都相等时基准始终落在端点附近递归区间只缩小一个元素。所以如果你的数据里有大量重复值三路划分不是可选的优化而是必须的处理。关于10万数据无法结束这个现象我再补充一个细节在调试版本Debug 模式下递归调用栈的帧信息会更重栈溢出可能来得比 Release 版本更早。所以如果你在调试环境遇到栈溢出先别急着怀疑自己的算法写错了换成 Release 再跑一遍往往表现完全不同。6.4 调试递归函数时最顺手的一条日志技巧我在排查快排问题时最常用的方法是在递归函数入口打印区间信息外加一个深度计数器把 30 层以内的调用都打出来人眼就能看出递归是否在正确收敛。快速验证输出的一种方式是在函数开头加一行void quickSortInternal(vectorint arr, int left, int right, int depth) { // cout depth depth left left right right // len (right - left 1) endl; ... }看输出里的len是否在逐轮缩小就能立刻发现划分失衡的问题。如果输出里出现长度为 1 或 0 的区间并且数量异常多那基本就能判定 partition 的等值处理或边界条件有瑕疵。看完记得把日志删掉不然几百毫秒的排序会被 Log 拖成好几秒。7. 写到最后我自己总结的几条快排经验快速排序的递归写法是算法学习路上绕不开的一环但真正把它写明白靠的不是背代码而是把每一个细节背后的为什么弄清楚。我自己写快排最看重的三件事放在最后分享给你第一基准值的选取是快排性价比最高的一处优化。三数取中只需要三次比较、三次交换就能把最坏情况从必然出现变成几乎不可能这笔买卖怎么算都划算。第二等值元素处理决定了你能不能在真实数据上站稳脚跟。项目里的数据从来不是教科书里的随机不重复整数重复、有序、逆序都是常态。如果你只背过最朴素的版本换到真实场景大概率要踩坑。第三递归版与非递归版之间没有绝对的谁好谁坏。递归版适合理解和正确性验证非递归版适合栈空间受限的环境。先用递归写对再按需要改成迭代版这个顺序最顺。如果你正在学快排被递归绕晕或者写出来的版本在某个特殊输入下表现诡异建议你亲手跑一遍上面给出的测试样例。画几张分区过程的示意图把指针的每一步移动落实在纸上问题一般会迎刃而解。