排序这块东西，平时写业务代码的人很少自己动手，调个库函数就完事了。但只要经历过几次凌晨被叫起来查问题，或者被丢到资源吃紧的环境里跑程序，就会开始琢磨底层到底发生了什么。我这次聊的是快速排序的非递归写法——这个系列前面三篇把递归版实现、基准选择策略、小区间优化都过了一遍，这一篇专门解决“把递归干掉”这件事。标题里写了个“（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 什么场景值得上非递归

不是所有场合都值得改。给你一张我自己整理的判断表，按实际情况对号入座：

那点性能差异是怎么来的？省掉了每次调用的压栈、跳转、返回，但增加了显式数组的读写。两者大致抵消，非递归略占优，因为数组读写是顺序的、缓存友好，而函数调用会污染指令缓存。别指望靠这个提速一倍，那是想多了。

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] 与 [p+1, 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 sortx

4.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 次取中位数：

结论很平淡：16 到 32 都能用，24 是我的舒适区。这里真正想说的不是这个数字，而是标定这件事本身值得做。很多参数在网上流传的“最佳值”，都是别人在特定硬件、特定编译器、特定数据分布下调出来的，你直接抄过来可能差得远。花二十分钟写个基准测试，比翻十篇博客靠谱。

顺带说一个实测中发现的细节：对近乎有序的数据（只有少量元素错位），阈值取大一点反而更好，因为此时划分本来就均匀，插入排序处理长序列的效率比多次划分高。但如果数据是随机的，阈值取大就会因为 O(k²) 而吃亏。所以如果你的数据特征明确，可以针对性调整；不确定就用 24，别在这上面耗太久。

5. 常见问题与排查实录

5.1 死循环与栈溢出的三类典型症状

症状一：程序卡住不动，CPU 占用 100%，但没有任何输出。十有八九是partitionHoare返回的p越界了，导致内层while反复处理同一个区间。检查点：划分结果到底是[lo, p] / [p+1, hi]还是[lo, p-1] / [p, hi]，两种写法对应不同的返回值语义，混用必死。我的建议是选定一种之后，在注释里把语义写死，改代码的人一看就不敢乱动。

症状二：数据量小时一切正常，数据量一大就崩。先查栈容量和压栈策略。把top打个日志出来，正常应该稳定在一个小数字上波动，如果看到它单调递增到几十、上百，那就是两边都压栈或者压小处理大了。还有一种可能是assert被关掉了（NDEBUG 定义了），溢出被静默吃掉，表现成别的乱象。

症状三：排序结果大部分正确，局部区间没排好。这种最磨人。通常是压栈时坐标写错，比如该压p + 1写成了p，导致某段被重复处理、另一段被漏掉。排查方法很土但有效：在小数组上（比如 20 个元素）加断言，每次弹出区间后检查lo <= hi且区间不重叠，跑几百组随机数据，问题立刻暴露。

5.2 排查速查表

5.3 用对拍验证正确性

算法改造最怕的是“看起来对”。我现在的习惯是写完任何排序，都拿std::sort跑对拍：生成随机长度（0 到 500）、随机内容（含大量重复值、全相同、已排序、逆序四种极端分布）的数组，跑一千组，逐元素比对。

这个习惯帮我抓到过一个很隐蔽的 bug：三路划分版本里，当整个区间全部相等时，lt停在lo、gt停在hi，左右两段都为空，压栈前我忘了判空，空区间进栈后弹出时lo > hi，插入排序的循环条件i <= hi不成立直接跳过，看起来没事，但下一次弹出的区间坐标已经错位了。这种问题在常规随机数据下根本不出现，只有全相等才触发。

对拍的另一个价值是测边界：长度为 0、1、2、3 的数组，全相同、只有两个元素逆序、只有最后一个元素错位。这些用例手写不了几条，但用随机生成加std::sort对比，几百行代码就能覆盖得相当全。我建议你在改任何一个排序实现之后，第一件事就是把这套对拍搭起来，别靠肉眼。

最后分享一个我自己的小技巧：迭代版快排调试的时候，把那个定长栈数组的前top个元素打印出来，格式化成[lo, hi]的列表，和递归版的调用栈对比着看，两者应该完全一致（顺序可能不同）。这个对比能让你在十分钟内确认自己的迭代改造是不是真的等价，比逐行读代码快得多。这个内容往下还能扩展的方向，是把显式栈换成一个可以序列化的结构，做到排序中途存档、跨进程续跑，这个我在分布式场景里用过一次，比重跑一遍整个排序省事不少。