先说一个我自己的体会。有一阵子我在处理一批模拟订单数据几十万条结构体记录需要按时间戳排序。头一回图省事直接套了个最简单的选择排序结果跑了快半分钟整个后端接口直接超时。换成快排之后同一批数据处理起来几乎感觉不到等待。排序这行代码在大多数工程里都躲在角落平时不起眼可数据量一旦上来算法选型的差距立刻变成时间上的天壤之别。这是C算法系列的第7篇聊分治法里最典型的应用——快速排序。这篇不只是给你一个能跑通的模板而是把快排背后的分治思想、三种partition写法、复杂度为什么会退化、工程级优化是怎么落的以及我自己实际代码里踩过的坑一次讲透。适合刚学完C语法、想系统捋一遍排序算法的读者也适合面试前想彻底吃透快排的开发者。1. 从选择排序跑了半分钟说起为什么快排是默认选项1.1 排序是很多高效算法的地基先别急着背代码。排序在工程里出现的频率远比你想象的高。数据去重要先排序二分查找要先排序求TopK、做区间合并、按时间轴展示日志几乎都依赖一个有序数组作为前提。我自己最常见的场景是日志分析原始日志按到达顺序落盘可能来自多个模块时间戳是乱的。想画一条耗时曲线出来第一步就是把记录按时间戳排好。这时候如果排序本身写成O(n^2)后面所有依赖有序数据的逻辑都跟着遭殃。1.2 常用排序的复杂度对比把一堆排序算法放到一张表里看形势很清楚算法平均时间复杂度最坏时间复杂度额外空间稳定性冒泡排序O(n^2)O(n^2)O(1)稳定选择排序O(n^2)O(n^2)O(1)不稳定插入排序O(n^2)O(n^2)O(1)稳定归并排序O(nlogn)O(nlogn)O(n)稳定堆排序O(nlogn)O(nlogn)O(1)不稳定快速排序O(nlogn)O(n^2)O(logn)不稳定O(nlogn)这一档里归并排序稳定但需要额外O(n)空间堆排序在工程实现里常数偏大、缓存访问不友好。快排占据了一个非常好的生态位原地排序、平均情况常数小、对CPU缓存友好。所以各大语言标准库里最常用的通用排序骨架上基本都是快排外加一些兜底策略。1.3 快排是分治思想最直观的样本把快排学透的意义还在于它是理解分治法的最佳切片。分治模型在归并、二分、线段树、经典分治算法里反复出现但快排的分治感最特殊——它把大部分工作放在分解阶段合并阶段什么都不用做。这一点后面展开说。所以这篇的顺序是这样的先讲清楚分治三步走再写三种partition然后分析最坏情况是怎么来的接着给出一套工程级优化实现最后用实测数据告诉你优化到底值多少。2. 分治三步走分解、求解、合并以及那个不用合并的关键洞见2.1 分治思想的一般模型分治法做一件事抽象出来就三步把大问题拆成若干结构相同的子问题递归解决每个子问题把子问题的结果合并成大问题的结果。这个模型最典型的例子是归并排序先把数组对半砍递归把左右半边分别排好序最后用一次合并操作把两个有序数组拼成一个。归并排序的工作重心在合并这一步因为拆的时候什么也没干。快排则刚好反过来。2.2 快排的分解选基准与分区快排的分解阶段做两件事。第一从当前区间里选一个元素作为基准pivot第二通过一趟partition把整个区间调整成这样的结构pivot左侧的所有元素都不大于pivotpivot右侧的所有元素都不小于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::vectorint 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::vectorint 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::vectorint 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::vectorint 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::vectorint 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 三种写法横向对比与稳定性分区方式基准位置返回值语义交换次数主要易错点Lomuto区间最后一个pivot最终位置较多j扫描越界问题少见但等于pivot处理不当会退化Hoare区间中间或任意左半区间的分界点不是pivot位置约为Lomuto的1/3递归区间写错、do-while等号处理挖坑法区间第一个pivot最终位置类似Lomuto内层循环等号、坑位转移顺序稳定性问题上多说一句。快排是不稳定的因为分区过程里发生了跨距离交换。比如数组[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(n1)/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::vectorint 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::vectorint 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::vectorint 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::vectorint 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::vectorint 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 优化前后耗时对比实现版本随机数据升序数据大量重复数据朴素Lomuto固定取末尾pivot约0.30s直接栈溢出约0.28sHoare取中间pivot约0.18s约0.20s约0.19s三点取中小数组插入排序约0.12s约0.08s约0.15s三路快排插入排序兜底约0.09s约0.06s约0.05s不同机器、不同编译器的实测数字会有浮动但趋势稳定三点取中救活了有序数据三路快排救活了重复数据。朴素版在升序数据上的栈溢出不是性能问题直接是可用性问题。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]和[p1, r]。这个写错之后轻则某些元素永远没参与排序重则无限递归。记住Hoare的返回值是分界点不是pivot。第四坑递归终止条件写成if (l r)而不是if (l r)。如果某个递归调用传入了p1 r之类的区间l r虽然能退出但很容易掩盖上游递归区间划分的问题。我更倾向用l r直接杜绝空区间进入递归。第五坑排序函数参数用了值传递vectorint a整段快排立刻变成O(n^2)级别的拷贝灾难。一定要用引用传递或者用迭代器区间。6.4 什么时候别让快排上场快排不是银弹。如果你需要稳定性比如按时间排序时要求相同时刻保持原始先后快排的跨距离交换会毁掉这个顺序此时应选归并排序或标准库的稳定排序版本。如果排序的元素是体积很大的结构体频繁swap的拷贝成本会很高。可以改用索引数组或指针数组排序先用vectorint存下标排序时只交换下标最后按下标顺序输出。这样无论元素多大参与比较和交换的都是几个整数。如果数据几乎有序且规模很大快排配合三点取中表现还不错但更彻底的选择是采用一些混合归并思路的排序。这类排序在近有序数据上能做到接近线性的表现。工程里碰到数据只差一点就排好的场景不要只看平均复杂度要专门留意数据分布特征。最后再分享一点个人的写法习惯这些年我写C排序九成情况直接调标准库的sort和稳定排序版本自己手写快排的机会主要集中在刷题、面试、或者遇到特殊数据需要定制分区逻辑的时候。但我强烈建议你把快排从头到尾手写一遍Lomuto一遍Hoare一遍三路快排一遍。不是为了背模板而是写的过程会让你真正理解递归、分治和工程折中是怎么回事。尤其是把为什么取中点而不是写死第一个元素为什么等于号必须这样处理这些问题自己回答清楚之后再看标准库sort的文档你会突然觉得那些实现都是有血有肉的设计决策而不是一个黑盒。快排的思想不会过时它至今仍是理解算法思维和解耦问题时最好的入门样本。 
长河君 · 2026/10/20 12:03:04 · 阅读 1.2k C++快速排序全解析：分治思想、三种分区写法与工程级优化
先说一个我自己的体会。有一阵子我在处理一批模拟订单数据几十万条结构体记录需要按时间戳排序。头一回图省事直接套了个最简单的选择排序结果跑了快半分钟整个后端接口直接超时。换成快排之后同一批数据处理起来几乎感觉不到等待。排序这行代码在大多数工程里都躲在角落平时不起眼可数据量一旦上来算法选型的差距立刻变成时间上的天壤之别。这是C算法系列的第7篇聊分治法里最典型的应用——快速排序。这篇不只是给你一个能跑通的模板而是把快排背后的分治思想、三种partition写法、复杂度为什么会退化、工程级优化是怎么落的以及我自己实际代码里踩过的坑一次讲透。适合刚学完C语法、想系统捋一遍排序算法的读者也适合面试前想彻底吃透快排的开发者。1. 从选择排序跑了半分钟说起为什么快排是默认选项1.1 排序是很多高效算法的地基先别急着背代码。排序在工程里出现的频率远比你想象的高。数据去重要先排序二分查找要先排序求TopK、做区间合并、按时间轴展示日志几乎都依赖一个有序数组作为前提。我自己最常见的场景是日志分析原始日志按到达顺序落盘可能来自多个模块时间戳是乱的。想画一条耗时曲线出来第一步就是把记录按时间戳排好。这时候如果排序本身写成O(n^2)后面所有依赖有序数据的逻辑都跟着遭殃。1.2 常用排序的复杂度对比把一堆排序算法放到一张表里看形势很清楚算法平均时间复杂度最坏时间复杂度额外空间稳定性冒泡排序O(n^2)O(n^2)O(1)稳定选择排序O(n^2)O(n^2)O(1)不稳定插入排序O(n^2)O(n^2)O(1)稳定归并排序O(nlogn)O(nlogn)O(n)稳定堆排序O(nlogn)O(nlogn)O(1)不稳定快速排序O(nlogn)O(n^2)O(logn)不稳定O(nlogn)这一档里归并排序稳定但需要额外O(n)空间堆排序在工程实现里常数偏大、缓存访问不友好。快排占据了一个非常好的生态位原地排序、平均情况常数小、对CPU缓存友好。所以各大语言标准库里最常用的通用排序骨架上基本都是快排外加一些兜底策略。1.3 快排是分治思想最直观的样本把快排学透的意义还在于它是理解分治法的最佳切片。分治模型在归并、二分、线段树、经典分治算法里反复出现但快排的分治感最特殊——它把大部分工作放在分解阶段合并阶段什么都不用做。这一点后面展开说。所以这篇的顺序是这样的先讲清楚分治三步走再写三种partition然后分析最坏情况是怎么来的接着给出一套工程级优化实现最后用实测数据告诉你优化到底值多少。2. 分治三步走分解、求解、合并以及那个不用合并的关键洞见2.1 分治思想的一般模型分治法做一件事抽象出来就三步把大问题拆成若干结构相同的子问题递归解决每个子问题把子问题的结果合并成大问题的结果。这个模型最典型的例子是归并排序先把数组对半砍递归把左右半边分别排好序最后用一次合并操作把两个有序数组拼成一个。归并排序的工作重心在合并这一步因为拆的时候什么也没干。快排则刚好反过来。2.2 快排的分解选基准与分区快排的分解阶段做两件事。第一从当前区间里选一个元素作为基准pivot第二通过一趟partition把整个区间调整成这样的结构pivot左侧的所有元素都不大于pivotpivot右侧的所有元素都不小于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::vectorint 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::vectorint 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::vectorint 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::vectorint 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::vectorint 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 三种写法横向对比与稳定性分区方式基准位置返回值语义交换次数主要易错点Lomuto区间最后一个pivot最终位置较多j扫描越界问题少见但等于pivot处理不当会退化Hoare区间中间或任意左半区间的分界点不是pivot位置约为Lomuto的1/3递归区间写错、do-while等号处理挖坑法区间第一个pivot最终位置类似Lomuto内层循环等号、坑位转移顺序稳定性问题上多说一句。快排是不稳定的因为分区过程里发生了跨距离交换。比如数组[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(n1)/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::vectorint 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::vectorint 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::vectorint 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::vectorint 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::vectorint 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 优化前后耗时对比实现版本随机数据升序数据大量重复数据朴素Lomuto固定取末尾pivot约0.30s直接栈溢出约0.28sHoare取中间pivot约0.18s约0.20s约0.19s三点取中小数组插入排序约0.12s约0.08s约0.15s三路快排插入排序兜底约0.09s约0.06s约0.05s不同机器、不同编译器的实测数字会有浮动但趋势稳定三点取中救活了有序数据三路快排救活了重复数据。朴素版在升序数据上的栈溢出不是性能问题直接是可用性问题。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]和[p1, r]。这个写错之后轻则某些元素永远没参与排序重则无限递归。记住Hoare的返回值是分界点不是pivot。第四坑递归终止条件写成if (l r)而不是if (l r)。如果某个递归调用传入了p1 r之类的区间l r虽然能退出但很容易掩盖上游递归区间划分的问题。我更倾向用l r直接杜绝空区间进入递归。第五坑排序函数参数用了值传递vectorint a整段快排立刻变成O(n^2)级别的拷贝灾难。一定要用引用传递或者用迭代器区间。6.4 什么时候别让快排上场快排不是银弹。如果你需要稳定性比如按时间排序时要求相同时刻保持原始先后快排的跨距离交换会毁掉这个顺序此时应选归并排序或标准库的稳定排序版本。如果排序的元素是体积很大的结构体频繁swap的拷贝成本会很高。可以改用索引数组或指针数组排序先用vectorint存下标排序时只交换下标最后按下标顺序输出。这样无论元素多大参与比较和交换的都是几个整数。如果数据几乎有序且规模很大快排配合三点取中表现还不错但更彻底的选择是采用一些混合归并思路的排序。这类排序在近有序数据上能做到接近线性的表现。工程里碰到数据只差一点就排好的场景不要只看平均复杂度要专门留意数据分布特征。最后再分享一点个人的写法习惯这些年我写C排序九成情况直接调标准库的sort和稳定排序版本自己手写快排的机会主要集中在刷题、面试、或者遇到特殊数据需要定制分区逻辑的时候。但我强烈建议你把快排从头到尾手写一遍Lomuto一遍Hoare一遍三路快排一遍。不是为了背模板而是写的过程会让你真正理解递归、分治和工程折中是怎么回事。尤其是把为什么取中点而不是写死第一个元素为什么等于号必须这样处理这些问题自己回答清楚之后再看标准库sort的文档你会突然觉得那些实现都是有血有肉的设计决策而不是一个黑盒。快排的思想不会过时它至今仍是理解算法思维和解耦问题时最好的入门样本。