排序这块东西平时写业务代码的人很少自己动手调个库函数就完事了。但只要经历过几次凌晨被叫起来查问题或者被丢到资源吃紧的环境里跑程序就会开始琢磨底层到底发生了什么。我这次聊的是快速排序的非递归写法——这个系列前面三篇把递归版实现、基准选择策略、小区间优化都过了一遍这一篇专门解决“把递归干掉”这件事。标题里写了个“4”说明它不是入门默认你已经知道快排为什么平均是 O(n log n)也知道最坏为什么退化成 O(n²)。为什么值得单独用一篇讲非递归因为递归快排和迭代快排看起来只是写法差异实际上在栈空间、可中断性、调试成本上是两套完全不同的东西。我自己第一次改这个版本是因为某个日志处理模块在排序 50 万条记录时会偶发崩溃日志里看不出任何异常换成非递归加显式栈之后稳定跑了两年。这篇内容适合三类人正在啃算法课、想搞清楚系统栈到底存了什么的学生需要在受限环境里跑排序的开发以及已经写出来能跑、但总担心边界和栈深度的读者。代码我统一用 C但思路和 Java、Python、Go 完全通用语言只是皮。1. 为什么要把快排从递归改成非递归1.1 递归快排真正的风险点在哪递归版快排的代码短、逻辑干净教科书上基本都是那个样子选基准、划分、左右两半各自递归。绝大多数情况下它跑得很好以至于很多人根本不觉得这里面有风险。但风险确实存在只是被“数据量不大”“栈空间够用”这两个前提遮住了。第一类风险是栈深度不可控。递归的调用栈由运行时替你管理你没法设置它的大小也没法在中途检查“还剩多少”。标准快排在最坏情况下每次划分都极不均匀比如数组已经有序而基准固定取第一个元素递归深度会退化到 n 层。n 等于 10⁶ 的时候每层栈帧哪怕只占 64 字节加起来也要 64MB默认配置基本直接崩。我遇到过在一块嵌入式板子上排序二十几万条记录程序不是算错是直接复位——栈溢出触发了硬件异常。第二类风险是递归进去就出不来。业务上经常有这种需求排序要分批做中间让出 CPU 给别的任务或者排序过程要能被中断、能汇报进度。递归写法一旦进去就得跑完才返回想做协作式调度非常别扭。非递归把状态放在堆上自己管随时可以停下来保存现场、下次接着跑。第三类风险是可观测性差。递归深了以后调试器里栈帧几十层想知道“现在到底在处理哪个区间”非常费劲显式栈就不一样你把栈内容打出来里面就是待处理的区间列表一眼就能看出卡在哪一段。这一点在排查“排完整体看着对、局部区间没排好”这类诡异问题时特别有用我后面第 5 章会详细讲。1.2 显式栈方案与递归的等价性拆解要改造成功得先想清楚一件事递归快排的调用栈里到底存了什么答案比你想象的少。函数返回地址、参数、局部变量看着一堆但真正决定“下一步干什么”的信息只有一样——待处理区间的两个端点。基准、临时变量、循环计数器在划分结束的那一瞬间全部作废了不需要保存。这个“状态压缩”是快排能优雅改成迭代的关键。换成带回溯的搜索类算法比如八皇后、图着色状态复杂得多改成迭代得自己造一台状态机那才叫痛苦。快排没有这个问题一个存区间的数组就完全等价。等价关系可以这么理解递归是运行时替你维护一个栈每层压入“返回后继续处理右半段”这层意思非递归是你自己维护一个数组显式地压入“右半段还没处理”。前者你只能相信它不出问题后者你可以数、可以打印、可以断言、可以限制上限。1.3 什么场景值得上非递归不是所有场合都值得改。给你一张我自己整理的判断表按实际情况对号入座场景特征建议原因数据量小于十万跑在桌面/服务器保持递归代码短维护成本低栈深度撑得住数据量百万级且输入可能有序必须非递归或加随机基准极端输入下递归深度无法预估运行在资源受限环境强烈建议非递归显式栈可以定长预分配不占运行栈需要分批、可中断执行必须非递归递归无法保存中间状态返回排序逻辑本身在热路径被频繁调用建议非递归省掉函数调用开销实测有 3%~8% 提升教学、面试、一次性脚本递归可读性优先别过度设计那点性能差异是怎么来的省掉了每次调用的压栈、跳转、返回但增加了显式数组的读写。两者大致抵消非递归略占优因为数组读写是顺序的、缓存友好而函数调用会污染指令缓存。别指望靠这个提速一倍那是想多了。2. 核心设计栈里到底该存什么2.1 存区间下标的经典方案最直接的方案是压入一对下标。这里有个小分歧存左闭右闭的(lo, hi)还是存起点加长度(lo, len)。两种都对我偏好前者因为和教科书上的递归参数完全一致改成迭代时不需要做任何坐标换算少一层心算就少一类错误。用长度的话每次划分后要算(lo, p - lo)和(p 1, hi - p)写起来啰嗦而且hi - lo和hi - lo 1差一个 1 的地方特别容易错。闭区间写法里某一段非空的条件就是lo hi空区间根本不入栈——这个判断简单到不会写错。用一个结构体数组还是两个并行数组小规模我倾向两个int数组并行避免结构体对齐带来的额外填充缓存行利用率也高一点。当然这点差异在绝大多数业务里可以忽略别在这上面花太多心思。一个更省空间的变体是既然hi可以由lo加长度推出来而长度在排序过程中只会变小那确实能用更少的位数编码。但这类优化属于“我已经很闲了”级别除非你的栈真的是瓶颈否则没必要。2.2 只压较小区间加循环处理大区间这一节是全篇最重要的部分也是决定你写出来的是“假非递归”深度仍然是 O(n)还是“真非递归”深度 O(log n)的分水岭。朴素的做法是划分完左右两段都压栈。代码看起来对称漂亮问题是最坏情况下栈里会堆积 O(n) 个区间——比如输入已经有序、每次划分只能切掉一个元素时每层都压一个只含一个元素的区间栈长直接线性增长。你从递归栈溢出改成了自己的数组溢出问题只是从 A 换成了 B。正确解法是尾递归消除每次划分完先处理较短的那一段把较长的那一段压栈。为什么这样管用因为循环变量代表“当前正在处理的区间”它在不断变小而栈里存的每一个区间长度至少是上一层处理区间的一半以上。既然每压一次栈规模至少翻倍那栈里最多就log₂(n)个元素。推导过程写清楚一点设当前区间长度 m划分后左段长 a、右段长 b满足 a b m − 1扣掉基准本身占的一位。我们压入较长的那段处理较短的那段。那么下一次循环处理的区间长度不超过 (m − 1)/2。也就是说循环每转一圈工作区间至少减半一次。从 n 减到 1最多需要log₂(n)轮而每一轮最多往栈里加一个元素因此栈的峰值深度不超过log₂(n) 1。顺带一个好处较短的那段先处理它的数据大概率还在 CPU 缓存里局部性更好。这个收益在百万级数据上实测能看出一点差别虽然不大。2.3 栈容量上界推导与定长预分配有了上面的结论栈容量就可以算死了。log₂(n)在 n 取 2³²约 43 亿时是 32加 1 是 33。就算你排序 2⁶⁴ 个元素现实中不可能也才 65。所以开一个长度 64 的定长int数组永远不会溢出。这是我很喜欢的一个工程细节整个快排迭代版可以做到零动态内存分配。不用std::vector、不用new、不用malloc排序过程里一次堆操作都没有。对于那些“排序中途绝不能失败”“不能抛异常”的场合比如信号处理、实时控制这一点比性能更有价值。不过定长预分配有个前提必须是“压大处理小”策略。如果你改成两边都压栈或者压小处理大64 就完全不够用了。所以这个常量和策略是绑定的写注释的时候一定要说明白不然下一个人改两行代码栈就悄悄溢出了。我自己习惯在代码里加一句断言assert(top STACK_CAPACITY stack overflow: check push-smaller strategy);断言在调试时能第一时间抓住问题在发布版里编译掉不留开销。3. 划分环节的工程化改造3.1 三数取中与小区间切换阈值迭代框架搭好之后性能瓶颈就全落在划分函数上。基准选择依然是重点固定取首元素的策略在已排序或逆序输入下会退化成 O(n²)这个坑递归版会踩非递归版一样会踩。三数取中是最划算的改进代价是三次比较加一次交换收益是把极端输入下的划分质量拉回正常水平。具体做法是比较首、中、尾三个位置的值把中位数换到首位置当基准。注意这里有个容易写错的点三数取中不是取平均值也不是简单取中间位置而是真的把三个值排序后取中间那个。小区间切换阈值是另一个必加的优化。数组长度小于某个门槛时直接走插入排序不再划分。原因有三个小数组上插入排序的常数因子远小于快排没有函数调用、没有递归、分支预测友好快排在长度只有几个元素时划分本身就没什么收益反而白白做了一堆比较插入排序是稳定的顺序访问缓存命中率高。门槛取多少市面上的实现从 8 到 32 都有。我在第 4 章给了一组实测数据结论是16 到 24 之间差别很小取 24 稍微稳一点。别纠结这个数字差几个元素对整体性能的影响在 1% 以内比你在其他地方随手浪费的多得多。3.2 Hoare 与 Lomuto 的取舍划分算法有两套主流写法很多人在这一步直接抄错了。Lomuto 划分思路直观以末尾元素为基准用一个指针从左往右扫把小于基准的往左边挪。代码短、好理解、适合教学。缺点是交换次数多每个小元素都可能触发一次交换而且遇到大量重复元素时退化严重——全是相等元素时它会把相等的都丢到一边划分极不均匀。Hoare 划分是原始版本两个指针从两端往中间夹左边找大于等于基准的右边找小于等于基准的找到就交换。交换次数平均只有 Lomuto 的三分之一左右而且最终基准落在中间附近划分天然更均衡。我选择 Hoare但必须提醒几个坑它的返回值语义是“左段的右端点”不是“基准的最终位置”。用闭区间的话划分结果是[lo, p]和[p 1, hi]两段都非空所以不会死循环。很多人照着某个博客写成[lo, p - 1]和[p, hi]然后递归无限下去本质上就是把语义搞混了。还有一个边界安全的问题用do { i; } while (a[i] pivot)这种写法第一下自增之后立刻读a[i]看着吓人。它之所以安全是因为基准值本身就在数组里当哨兵——pivot取的是a[lo]右指针j向左扫到lo时必然停下a[lo] pivot不满足 pivot此时i不可能越界。但如果你为了“优化”把基准单独拿出来、把a[lo]换成别的值这个哨兵就没了越界立刻发生。我踩过这个坑改完跑小数据没事跑大数据偶发崩溃定位了很久。3.3 重复元素处理三路划分的适用边界普通二路划分有个隐蔽的弱点数组里如果有大量与基准相等的元素这些相等元素会被随机分到左右两边下一层还要继续处理它们白做功。极端情况是全部元素相等二路划分每次都只切掉一个直接退化成 O(n²)。业务数据里这种情况比想象中常见。按状态字段排序、按等级分组、按布尔标记排序取值域都很小重复率极高。这时候该上三路划分荷兰国旗问题一趟扫描把数组分成 基准、 基准、 基准三段中间那段直接归位不再入栈。代价是三路划分的常数比二路大每次比较要做两次判断。所以策略是如果数据重复率低二路更快重复率高三路完胜。怎么判断如果提前知道数据特征就用对应的不确定的话二路加三数取中已经够用只有明确知道取值域很小才上三路。三路划分在迭代框架里的写法要小心划分完得到lt和gt两个下标左段是[lo, lt - 1]右段是[gt 1, hi]。两段都可能为空压栈前必须判空否则空区间进栈后循环里lo hi直接读越界。4. 完整实现与逐段代码解析4.1 迭代版快速排序的完整代码下面这份是我自己项目里用的版本注释写得比较密可以直接抄。核心结构是外层循环弹栈内层while处理当前区间直到长度低于阈值最后统一走插入排序。#include cassert #include algorithm namespace sortx { constexpr int INSERTION_THRESHOLD 24; // 小区间切换阈值 constexpr int STACK_CAPACITY 64; // 压大处理小 深度 log2(n)1 // 闭区间 [lo, hi] 的插入排序 inline void insertionSort(int* a, int lo, int hi) { for (int i lo 1; i hi; i) { int key a[i]; int j i - 1; while (j lo a[j] key) { a[j 1] a[j]; --j; } a[j 1] key; } } // 三数取中把中位数换到 lo 位置当基准 inline void medianToFirst(int* a, int lo, int hi) { int mid lo ((hi - lo) 1); if (a[mid] a[lo]) std::swap(a[mid], a[lo]); if (a[hi] a[lo]) std::swap(a[hi], a[lo]); if (a[hi] a[mid]) std::swap(a[hi], a[mid]); std::swap(a[lo], a[mid]); // 中位数就位 } // Hoare 划分返回左段的右端点 p划分结果 [lo, p] 与 [p1, hi] // 前置条件hi - lo 2且 a[lo] 已是三数取中的结果 inline int partitionHoare(int* a, int lo, int hi) { const int pivot a[lo]; int i lo - 1; int j hi 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]); } } void quickSort(int* a, int n) { if (n 2) return; int stackLo[STACK_CAPACITY]; int stackHi[STACK_CAPACITY]; int top 0; stackLo[top] 0; stackHi[top] n - 1; top; while (top 0) { --top; int lo stackLo[top]; int hi stackHi[top]; // 当前区间一直划分直到长度落到阈值以内 while (hi - lo 1 INSERTION_THRESHOLD) { int p partitionHoare(a, lo, hi); int leftLen p - lo 1; int rightLen hi - p; if (leftLen rightLen) { // 压右段继续处理左段 stackLo[top] p 1; stackHi[top] hi; top; assert(top STACK_CAPACITY); hi p; } else { // 压左段继续处理右段 stackLo[top] lo; stackHi[top] p; top; assert(top STACK_CAPACITY); lo p 1; } } insertionSort(a, lo, hi); } } } // namespace sortx4.2 关键变量与不变式说明这份代码里有几个不变式理解了它们你就能自己改、也不会改错。第一条栈里所有区间两两不相交且覆盖所有尚未排序的元素。这条保证了正确性——把所有区间处理完整个数组就排好了。如果某次压栈写错坐标区间会重叠同一段被排两次结果可能是对的白做功或者漏掉某段结果错但很难发现。第二条top的峰值不超过log₂(n) 1。这条保证了空间安全也是定长数组能用的依据。你在调试时可以直接在循环里打印top正常数据下它应该长期维持在 2 到 30 之间如果看到它一直往上涨比如超过 40说明策略写反了压的是小区间。第三条内层while退出时lo到hi的区间长度必然不超过阈值。这条是插入排序正确性的前提——插入排序处理的就是这个残留的小数组。如果某次划分后你忘了更新lo或hi这个残留区间就是错的插入排序会把本来排好的部分搅乱。第四条partitionHoare返回的p满足lo p hi。左边不等于hi是因为至少要留一个元素给右段pivot本身在左段否则右段为空、pivot落到右段的边界上循环就乱了p不小于lo是因为左段至少含基准一个元素。这两个边界条件如果被破坏内层while就会陷入死循环而且是很隐蔽的那种。4.3 阈值标定与实测记录阈值这个参数我做过一轮简单的标定环境是常见的 x86 笔记本编译器开 -O2数据是随机打散的 32 位整数每组跑 20 次取中位数阈值100 万元素耗时1000 万元素耗时备注862 ms780 ms划分次数偏多收益不明显1658 ms726 ms接近最优2457 ms718 ms我的默认值3259 ms735 ms开始下滑插入排序的 O(k²) 拖后腿6466 ms812 ms明显变慢结论很平淡16 到 32 都能用24 是我的舒适区。这里真正想说的不是这个数字而是标定这件事本身值得做。很多参数在网上流传的“最佳值”都是别人在特定硬件、特定编译器、特定数据分布下调出来的你直接抄过来可能差得远。花二十分钟写个基准测试比翻十篇博客靠谱。顺带说一个实测中发现的细节对近乎有序的数据只有少量元素错位阈值取大一点反而更好因为此时划分本来就均匀插入排序处理长序列的效率比多次划分高。但如果数据是随机的阈值取大就会因为 O(k²) 而吃亏。所以如果你的数据特征明确可以针对性调整不确定就用 24别在这上面耗太久。5. 常见问题与排查实录5.1 死循环与栈溢出的三类典型症状症状一程序卡住不动CPU 占用 100%但没有任何输出。十有八九是partitionHoare返回的p越界了导致内层while反复处理同一个区间。检查点划分结果到底是[lo, p] / [p1, hi]还是[lo, p-1] / [p, hi]两种写法对应不同的返回值语义混用必死。我的建议是选定一种之后在注释里把语义写死改代码的人一看就不敢乱动。症状二数据量小时一切正常数据量一大就崩。先查栈容量和压栈策略。把top打个日志出来正常应该稳定在一个小数字上波动如果看到它单调递增到几十、上百那就是两边都压栈或者压小处理大了。还有一种可能是assert被关掉了NDEBUG 定义了溢出被静默吃掉表现成别的乱象。症状三排序结果大部分正确局部区间没排好。这种最磨人。通常是压栈时坐标写错比如该压p 1写成了p导致某段被重复处理、另一段被漏掉。排查方法很土但有效在小数组上比如 20 个元素加断言每次弹出区间后检查lo hi且区间不重叠跑几百组随机数据问题立刻暴露。5.2 排查速查表现象最可能的原因处理办法彻底卡死无输出划分返回值语义与使用方不一致统一约定并写注释加区间非空断言大数据崩溃小数据正常栈深度 O(n) 或定长数组不够检查是否“压大处理小”打印 top 曲线结果局部乱序入栈坐标错位区间重叠或遗漏小规模随机数据加重叠断言复现全体相等时极慢二路划分对重复元素退化换三路划分或在检测到重复时切换已排序输入极慢基准固定取首元素上三数取中或随机化基准排序结果尾部有垃圾值插入排序hi参数传错检查内层循环退出后lo/hi是否正确换台机器就变慢阈值不适配当前硬件重新跑标定别迷信固定值5.3 用对拍验证正确性算法改造最怕的是“看起来对”。我现在的习惯是写完任何排序都拿std::sort跑对拍生成随机长度0 到 500、随机内容含大量重复值、全相同、已排序、逆序四种极端分布的数组跑一千组逐元素比对。这个习惯帮我抓到过一个很隐蔽的 bug三路划分版本里当整个区间全部相等时lt停在lo、gt停在hi左右两段都为空压栈前我忘了判空空区间进栈后弹出时lo hi插入排序的循环条件i hi不成立直接跳过看起来没事但下一次弹出的区间坐标已经错位了。这种问题在常规随机数据下根本不出现只有全相等才触发。对拍的另一个价值是测边界长度为 0、1、2、3 的数组全相同、只有两个元素逆序、只有最后一个元素错位。这些用例手写不了几条但用随机生成加std::sort对比几百行代码就能覆盖得相当全。我建议你在改任何一个排序实现之后第一件事就是把这套对拍搭起来别靠肉眼。最后分享一个我自己的小技巧迭代版快排调试的时候把那个定长栈数组的前top个元素打印出来格式化成[lo, hi]的列表和递归版的调用栈对比着看两者应该完全一致顺序可能不同。这个对比能让你在十分钟内确认自己的迭代改造是不是真的等价比逐行读代码快得多。这个内容往下还能扩展的方向是把显式栈换成一个可以序列化的结构做到排序中途存档、跨进程续跑这个我在分布式场景里用过一次比重跑一遍整个排序省事不少。