1. 为什么把非递归和稳定性分析放在同一篇里讲先说结论C语言快排非递归、归并非递归以及八大排序的时间复杂度、空间复杂度、稳定性分析这三件事在内核态、嵌入式、竞赛评测机、以及一些对栈深度敏感的场景里是绑在一起出现的。我不是为了凑一篇八股文才把它们放一起而是因为但凡你开始认真考虑递归会不会把栈打爆下一步就一定会追问那我把递归换成循环代价是什么、结论变不变再下一步就是既然要换那我干脆把八大排序的账一次性算清楚以后选型不再靠背表格。大多数人学排序的路子是背一遍八大排序的名字抄一份快排代码看一眼表格记住快排不稳定、归并稳定、堆排不稳定然后考试结束就还回去了。真到了写代码的时候遇到需要按两个字段排序的结构体数组随手qsort一调结果发现相同主键的元素顺序乱了回头查文档才知道qsort从来不保证稳定。或者在某次数据量上到几百万、递归深度接近极限的时候程序直接段错误调试半天才意识到是快排递归太深。这篇文章面向的读者范围我尽量放宽写过 C 语言、知道指针和数组区别的同学能看懂并直接抄走代码做过一段时间项目、但从来没系统算过各排序空间开销的开发者能从对照表和踩坑章节里补上这块。核心代码我会全部给全能直接编译运行参数怎么定、为什么这么定我也会把推导过程写出来而不是甩一句经验值了事。2. 快速排序非递归化的关键递归里真正被保存的只有区间2.1 递归快排到底压了什么进调用栈想清楚非递归怎么写第一步是搞清楚递归版本到底在保存什么。看这段最常见的递归快排void quick_sort(int *a, int left, int right) { if (left right) return; int mid partition(a, left, right); quick_sort(a, left, mid - 1); quick_sort(a, mid 1, right); }递归调用里真正影响后续计算的局部变量只有两个left和right。mid在返回后就不再需要了因为它指向的元素已经落在最终位置上左边和右边是两条独立的子问题。也就是说递归调用栈在这里承担的角色本质上只是一个待处理区间的容器它没有返回值参与运算也没有跨调用的状态累积。这个观察非常关键。既然栈里存的只是两个整数那完全可以自己拿一块内存当栈把(left, right)作为一对压进去循环从栈里弹出区间处理直到栈空。整个改造过程中排序逻辑也就是partition和小区间处理一行都不用改改的只是谁来记住还没处理的区间。我见过有人在改造的时候连partition一起重写最后改出个结果不对的版本其实没必要。非递归改造是纯粹的控制流重写算法内核不变把这两件事分开想出错概率会低很多。顺带说一个容易被忽略的点递归版本里mid本身不需要再入栈。因为partition返回的位置i满足左边全部 ≤ 它、右边全部 ≥ 它它自己的位置已经终局了。新手写非递归版最常见的 bug 就是把(left, mid)和(mid, right)压进去导致区间不收缩程序死循环。正确的入栈区间一定是(left, mid-1)和(mid1, right)并且入栈前要判断left mid-1、mid1 right。2.2 手写区间栈定长数组还是动态扩容栈的实现有两种常见路线。定长数组简单但长度怎么给是个问题动态扩容稳妥但多了一层malloc/realloc、多了一处失败检查。我的做法是动态扩容初始容量给 32满了就翻倍。理由是快排的最坏递归深度理论上可以到 O(n)如果数据是精心构造的比如每次都取到极值作为枢轴定长 64 的栈根本不够而这种数据在真实业务里并非不可能——比如一个已经是降序、且带大量重复值的数组。动态扩容能用几十行代码换掉一整类隐患很划算。typedef struct { int left; int right; } Range; typedef struct { Range *buf; int top; /* 栈中元素个数 */ int cap; /* 当前容量 */ } RangeStack; static int rs_init(RangeStack *s) { s-cap 32; s-top 0; s-buf (Range *)malloc(sizeof(Range) * s-cap); return s-buf ! NULL; } static void rs_free(RangeStack *s) { free(s-buf); s-buf NULL; s-top s-cap 0; } static int rs_push(RangeStack *s, int l, int r) { if (s-top s-cap) { int nc s-cap * 2; Range *nb (Range *)realloc(s-buf, sizeof(Range) * nc); if (nb NULL) return 0; /* 失败时不能丢原指针 */ s-buf nb; s-cap nc; } s-buf[s-top].left l; s-buf[s-top].right r; s-top; return 1; } static int rs_pop(RangeStack *s, Range *out) { if (s-top 0) return 0; s-top--; *out s-buf[s-top]; return 1; }realloc那一行有个经典陷阱不能写成s-buf realloc(s-buf, ...)因为一旦失败原指针就丢了内存泄漏。必须用临时指针接收返回值再赋值。这个坑我在别人的代码里见过不止一次尤其在资源受限、malloc真有可能失败的场景下这不是理论问题。提示栈里的元素类型用一个Range结构体比用两个平行数组一个存 left 一个存 right更不容易下标搞错。空间上因为结构体对齐可能会浪费几个字节但这点浪费换来的是可读性和正确性值。2.3 入栈顺序决定栈深度区间怎么压、先压哪个直接影响栈里同时存在多少个元素。这里有个很实用的技巧先压长区间后压短区间。因为栈是后进先出后压的短区间会先被弹出处理处理过程中长区间一直躺在栈底不动而如果反过来先压短的长区间会先出栈并立刻又产生两个子区间栈中元素数量会层层叠加。这个优化在最好的情况下能把栈深度维持在 O(log n) 量级相当于变相实现了尾递归消除里的那一步。代码上就是个简单的比较if (mid - 1 - left right - mid - 1) { if (mid 1 right) rs_push(st, mid 1, right); /* 长的先进 */ if (left mid - 1) rs_push(st, left, mid - 1); /* 短的后进先出 */ } else { if (left mid - 1) rs_push(st, left, mid - 1); if (mid 1 right) rs_push(st, mid 1, right); }不过要说明白这个技巧只降低平均栈深度不能改变最坏情况的 O(n) 上界。因为最坏情况下每次划分都极度不均比如 mid 就在最边上短的区间是空、长的区间是 n-1你怎么排顺序都得把长区间压进去长度就是 n。所以想真正压住最坏情况还是得在枢轴选取和划分策略上下功夫后面第 5 节会专门讲。2.4 小区间插排与三数取中在非递归版里的位置partition函数本身不用改但两处优化必须一起搬到非递归版里否则性能会明显差于标准库。第一处是三数取中。取left、mid、right三个位置的值排序把中位数换到一边当枢轴。目的是避免已有序数组这个最常见的退化场景——如果直接拿a[left]当枢轴一个已经升序的数组每次划分都只能削掉一个元素退化到 O(n²)。第二处是小区间切插入排序。当区间长度小于等于某个阈值我习惯用 16时直接调插入排序后continue不再继续划分。原因有两个一是小数组上快排的递归/入栈开销摊薄了每个元素的处理成本插入排序的常数因子小得多二是插入排序在小规模、基本有序的数据上表现很好。static void insert_sort_range(int *a, int left, int right) { for (int i left 1; i right; i) { int key a[i]; int j i - 1; while (j left a[j] key) { a[j 1] a[j]; j--; } a[j 1] key; } }注意这个函数接收的是[left, right]闭区间和快排的语义保持一致。如果写成[left, right)半开区间调用处就得到处加一减一非常容易错。我在自己项目里有一条硬规矩所有排序函数统一用闭区间[left, right]参数语义不一致是排序代码 bug 的第一大来源。阈值取 16 不是随便定的。阈值太小比如 4快排划分的优势还没显现就切插入排序了整体变慢阈值太大比如 64插入排序 O(k²) 的代价开始显出来。8 到 16 这个区间在多数现代平台上差异不大取 16 是个稳妥的选择。真要抠这点差异得在自己的目标机器上做实测不同 CPU 的缓存行大小和分支预测行为会让最优点有所浮动。3. 归并排序去掉递归自底向上的步长推进法3.1 递归归并的分其实不干活归并排序和快排不太一样。快排的递归里partition是真的在干活做划分而递归归并的分这一步是纯下标计算没有任何数据移动void merge_sort(int *a, int *tmp, int left, int right) { if (left right) return; int mid left ((right - left) 1); merge_sort(a, tmp, left, mid); merge_sort(a, tmp, mid 1, right); merge(a, tmp, left, mid, right); }merge_sort里除了merge那一次调用其余全是递归下探。这意味着分的过程完全可以被一个循环替代从长度为 1 的有序段开始两两合并成长度 2再合并成 4、8……直到覆盖整个数组。这就是自底向上归并bottom-up merge sort。这个思路的好处不只是避免递归还有实际收益递归归并的访问顺序是深度优先的先一路切到最左边再一层层回来合并自底向上是宽度优先的同一轮里所有相邻段依次合并内存访问模式更规整对缓存和硬件预取更友好。在数组这种连续存储结构上自底向上版本实测往往略快于递归版即使不算栈开销。3.2 一趟归并的区间边界推导自底向上归并的骨架是两层循环外层控制段长gap从 1 开始倍增内层从左到右依次合并相邻两段void merge_sort_iter(int *a, int n, int *tmp) { if (n 2) return; for (int gap 1; gap n; gap * 2) { for (int left 0; left n; left 2 * gap) { int mid left gap - 1; if (mid n) break; /* 只剩左半段它已经有序 */ int right left 2 * gap - 1; if (right n) right n - 1; merge(a, tmp, left, mid, right); } } }边界推导值得单独说清楚因为这里是自底向上归并最容易写错的地方。设当前段长为gap那么这一轮要合并的是[left, leftgap-1]和[leftgap, left2*gap-1]两段。左段的右端点就是mid left gap - 1。右段的右端点理论上是left 2*gap - 1但可能越界所以取min(left 2*gap - 1, n - 1)。mid n这个判断的意思是左段本身都不完整了说明剩下的元素不足gap个。但这些元素在上一轮gap/2里已经被合并成一个有序段了所以直接跳过就行。注意这里用的是break不是continue——因为left是递增的后面的left更大mid只会更大于等于 n继续循环没有意义。merge函数本身和递归版完全一样static void merge(int *a, int *tmp, int left, int mid, int right) { int i left, j mid 1, k left; while (i mid j right) { if (a[i] a[j]) tmp[k] a[i]; /* 而非 这是稳定性的来源 */ else tmp[k] a[j]; } while (i mid) tmp[k] a[i]; while (j right) tmp[k] a[j]; memcpy(a left, tmp left, sizeof(int) * (size_t)(right - left 1)); }那个是归并排序稳定性的唯一来源必须记牢。当左右两段出现相等元素时优先取左段也就是原本位置更靠前的那个相对顺序才能保持。如果写成相等时取右段的稳定性立刻破坏。这是一个一字符之差改变算法性质的典型例子我建议在代码旁边直接写注释标出来防止以后重构时被简化掉。3.3 mid n 时该 break 还是 continue上面提到了但值得再展开一层因为这是我看过最多人写错的地方。假设n 10当前gap 4那么left的取值是 0、8。left 0时mid 3right 7正常合并[0,3]和[4,7]。下一轮left 8mid 11mid n成立break。剩下[8,9]这两个元素在这一轮没有被处理但它们在上轮gap 2时已经被合并成有序段了所以没关系。如果这里写成continueleft变成 16循环条件left n不成立循环自然退出。结果是一样的只是多绕了一圈。所以break和continue在这个特定位置结果相同但break语义更明确、效率更高。真正会出问题的是把mid n的判断漏掉——那样mid 11会传给mergej 12i mid的判断永远成立直接从数组外面读数据这是典型的越界访问往往不会立刻崩溃而是悄悄把脏数据排进去排查起来极其痛苦。注意自底向上归并的边界条件建议用n 0, 1, 2, 3, 5, 7, 8这几个特殊值各跑一遍。这些值分别对应空数组单元素刚好一段段长比 n 大右段缺失左右段都存在但都不满等情况能覆盖绝大多数边界错误。3.4 辅助数组的申请位置与复用递归归并每次调用都在栈上开临时数组是灾难性的标准做法是在最外层申请一块和原数组等大的tmp一路传下去复用。自底向上版本也一样tmp从外面传进来。申请位置建议在调用方用malloc在堆上开。原因是如果n比较大比如几十万栈上开sizeof(int) * n很可能直接爆栈而且不同平台的默认栈大小差异巨大有的是 1MB有的是 8MB代码的可移植性会被破坏。堆上申请虽然多一次系统调用但只发生一次成本可以忽略。int *tmp (int *)malloc(sizeof(int) * n); if (tmp NULL) { /* 处理失败 */ } merge_sort_iter(a, n, tmp); free(tmp);这里顺带说一个空间复杂度的细节自底向上归并的空间开销是 O(n)因为辅助数组必须和原数组等大。而递归归并除了 O(n) 的辅助数组还有 O(log n) 的调用栈。所以严格来说递归归并的空间复杂度是 O(n log n)通常简化记作 O(n)但如果你在做嵌入式开发、内存按字节抠这个 log n 的栈开销是要算进去的。还有一种原地归并的思路用三次旋转实现能把空间降到 O(1)但代价是时间复杂度退化到 O(n log²n)而且常数很大实践中基本不用。除非是在极端受限的环境里否则老老实实开 O(n) 的辅助数组更明智。4. 八大排序的时空与稳定性把表格背后的账算清楚4.1 稳定性到底在稳什么什么场景真的需要稳定性的定义很直白如果数组里有两个相等的元素 A 和 B排序前 A 在 B 前面排序后 A 仍然在 B 前面这个排序算法就是稳定的。这个性质单独看好像没什么用——相等的元素谁前谁后不都一样吗关键在于**相等只是在你关心的那个键上相等**。举个实际场景一个订单列表先按下单时间排好序现在要按金额再排一次。如果用的排序算法是稳定的那么金额相同的订单之间仍然保持原来的时间顺序如果是不稳定的金额相同的订单顺序就乱了你还得额外加一层时间比较作为次级键。在 C 语言里这个坑特别隐蔽因为qsort是标准库里最常用的排序函数而C 标准从来没有要求qsort稳定。多数实现用的是快排的某种变体不保证稳定。你在本地测出来是稳定的换个编译器、换个平台、甚至换个数据量导致实现走了不同分支结果就可能变。依赖qsort的稳定性是典型的在我机器上能跑陷阱。需要稳定排序时的务实做法要么自己写一个归并排序替换掉qsort要么在比较函数里加上能唯一确定顺序的次级键比如元素的内存地址或原始下标把相等的情况彻底消灭。后一种做法改动小但会增加比较函数的开销而且地址比较在数据搬移后可能失效得看具体场景。4.2 时间复杂度里被忽略的常数和缓存八大排序的时间复杂度表格人人会背但那张表只告诉你增长趋势不告诉你常数因子。两个都是 O(n log n) 的算法实际跑起来差两三倍是常事。快排为什么在实践中通常最快因为它的划分过程是顺序扫描、局部访问的。partition里i从左往右走、j从右往左走访问的都是紧挨着的内存缓存命中率高硬件预取器也能很好地工作。归并排序则需要额外的memcpy把临时数组内容搬回原数组数据量翻倍带宽压力大。堆排序的理论复杂度同样是 O(n log n)而且空间是 O(1)看起来很完美但实测常常比快排慢。原因是堆排序的下标跳跃幅度大i的父节点是(i-1)/2子节点是2i1和2i2这种访问模式对大数组来说缓存极不友好每次下沉都可能是一次缓存未命中。希尔排序更典型。它的时间复杂度取决于增量序列教科书上写 O(n^1.3) 到 O(n²) 不等没有紧确界。但就是这么一个理论不清不楚的算法在中规模几万到几十万数据上经常打得过堆排序因为它的移动次数少、访存连续。所以我在选型时的实际判断顺序是数据量小几十个以内直接插入排序数据量大、内存不紧张、需要稳定用归并数据量大、内存紧张、不需要稳定用快排带三数取中和小区间优化数据近乎有序用插入排序或带优化的快排数据是整数且范围不大考虑计数排序或基数排序能做到 O(n) 级别。4.3 空间复杂度递归栈也是空间空间复杂度这一栏很多人只算辅助数组忘了栈。快排的空间复杂度严格来写是 O(log n) 到 O(n)取决于递归深度递归归并是 O(n log n)堆排序才是真的 O(1)。这个区别在普通应用里无所谓但在两种场景下会要命一是嵌入式、单片机栈空间就几 KB二是深度递归处理超大数据比如对几千万个元素做快排递归深度哪怕只有几千层每层几十字节的栈帧也会吃掉几百 KB加上函数调用的其他开销风险不小。这也是我把快排改成非递归的主要动机之一。还有一点malloc出来的辅助数组虽然记作 O(n)但它的实际峰值取决于实现。比如归并排序如果在每层递归里都malloc和free虽然峰值可能还是 O(n)但malloc的元数据和管理开销会显著增加而且频繁分配释放本身就很慢。正确做法是最外层分配一次传指针复用这一点在 3.4 已经说过。4.4 八大排序对照表下面这张表是我自己常用的版本把关键参数都列全了。表里的八大按最常见的口径插入、希尔、冒泡、快速、选择、堆、归并、基数计数排序作为基数排序的特例一并讨论。k表示数据范围d表示位数r表示基数。排序方法平均时间最坏时间最好时间额外空间稳定性适用场景直接插入O(n²)O(n²)O(n)O(1)稳定小规模、近乎有序希尔排序约 O(n^1.3)O(n²)O(n)O(1)不稳定中等规模、内存受限冒泡排序O(n²)O(n²)O(n)O(1)稳定教学演示快速排序O(n log n)O(n²)O(n log n)O(log n)~O(n)不稳定大规模通用排序直接选择O(n²)O(n²)O(n²)O(1)不稳定交换代价大的场景堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定内存严格受限、要防最坏归并排序O(n log n)O(n log n)O(n log n)O(n)稳定需要稳定、链表排序基数排序O(d(nr))O(d(nr))O(d(nr))O(nr)稳定定长整数、字符串表格之外补几句说明这些是表里放不下的。希尔排序的稳定性为什么一定破坏因为它做的是跳跃式的插入相等的元素可能被分到不同组里跨组移动会打乱它们的相对顺序。再好的增量序列也救不回来这是算法结构决定的。直接选择排序的最坏、最好、平均都是 O(n²)因为无论数据什么样它都得完整扫描剩余部分找最小值没有任何提前退出的机会。这是它和插入排序、冒泡排序的关键区别——后两者在近乎有序时能退化到 O(n)。基数排序的复杂度里那个 r 是基数常见取 10十进制或 256按字节。基数小则 d 大、r 小基数大则 d 小、r 大需要一个平衡。而且基数排序需要额外的桶空间这是它空间复杂度 O(nr) 的来源。它还有个硬限制待排数据必须能按位拆分浮点数和有符号负数需要特殊处理负数可以整体加偏移量转成非负或者按符号位单独处理。稳定性的连锁反应基数排序能做到 O(n) 并且稳定靠的就是每一趟都必须用稳定排序通常是计数排序来分配和收集。如果中间某一趟用了不稳定排序前面几趟的成果就废了。这是稳定性作为算法组件的一个典型例子。5. 实测中真正会咬人的几个坑5.1 大量重复元素让快排退化成平方级这是个我必须单独拎出来讲的坑。三数取中能解决已排序数组的退化但它解决不了所有元素都相同的情况。回到 2.4 里提到的挖坑法划分。假设数组里全部是 5key 5那么while (i j a[i] key) i;这个条件恒成立i会一路走到j然后返回j也就是right。下一次划分的区间变成[left, right-1]每次只削掉一个元素退化成 O(n²)。数据里全相同元素的场景比想象中常见统计某字段的取值分布、日志按状态码聚合、成绩表里大量并列的情况。我碰到过一次真实事故对一个几十万条记录的日志数组排序因为大部分状态码都是同一个值程序跑了将近一分钟还没结束一度以为是死循环。解决办法有几个层次。最简单的补救是改划分策略。经典的 Hoare 双向划分版本用的是a[i] key就继续走遇到等于key就停下来交换这样相等元素会被均匀地分到两边全相同的情况下反而能完美二分。注意这个写法和填坑法的判断条件不一样填坑法用的和Hoare 版用和改的时候一定要整体改混着写会出错。更彻底的是三路划分荷兰国旗问题把数组分成小于、等于、大于枢轴三段递归只处理小于和大于两段等于段直接跳过。这样即使全是相同元素一趟划分就结束了时间复杂度是严格的 O(n)。三路划分的核心循环大概是这样/* a[left..right]pivot 取 a[left] */ int lt left, gt right, i left 1; int pivot a[left]; while (i gt) { if (a[i] pivot) { swap(a[i], a[lt]); lt; i; } else if (a[i] pivot) { swap(a[i], a[gt]); gt--; } else { i; } } /* 结束时a[left..lt-1] pivot, a[lt..gt] pivot, a[gt1..right] pivot */这段代码在非递归版本里同样能用只需要把两个新区间[left, lt-1]和[gt1, right]压栈即可。我现在的默认快排实现基本都带三路划分多写十行代码省掉一整类退化风险。还有一种做法是随机化枢轴用rand()随机选一个位置和left交换再划分。这能把被精心构造的数据打崩的概率降到极低但严格的算法分析上期望复杂度是 O(n log n)最坏还是 O(n²)。随机化的另一个副作用是引入了rand()调用每次划分一次开销不能完全忽略。我自己更偏好三路划分因为它是确定性的不依赖随机源。5.2 归并里的 gap 倍增与整型边界for (int gap 1; gap n; gap * 2)这行理论上存在溢出风险。如果n接近INT_MAX约 21 亿gap在某一轮会变成 2^30 左右再乘 2 就溢出了gap变成负数循环条件gap n永远成立程序死循环。现实中不会有这么大的数组21 亿个int就是 8GB所以这个风险基本可以忽略。但如果你的代码要作为通用库或者跑在 64 位、内存充足的服务器上处理超大数组还是防一手比较好。写法上可以改成for (int gap 1; gap n; gap (gap n / 2) ? n : gap * 2)或者干脆用long long做循环变量。另一个更现实的溢出点在left 2 * gap - 1。如果left接近n、gap又很大这个加法可能溢出。虽然循环里left n保证了left不会太大但保险起见计算right的时候先用long long或者用减法形式规避int right (n - 1 - left 2 * gap - 1) ? (n - 1) : (left 2 * gap - 1);这样写虽然啰嗦但完全避免了加法溢出的可能。我在写这类边界代码时有个习惯凡是可能超出数组范围的下标计算一律用目标值 - 当前位置这种减法形式先做比较再决定是否计算。5.3 非递归不等于不爆栈栈深度控制这里要澄清一个常见误解把递归改成非递归并不等于彻底解决了栈溢出问题它只是把调用栈换成了自己管理的堆内存。如果自己管理的这块内存用的是定长数组而且定得不够大一样会溢出——只是从段错误变成了数组越界可能更隐蔽。所以我的建议是要么用动态扩容第 2.2 节的做法要么在定长数组的版本里加显式的容量检查满了就返回错误码而不是继续写。绝对不能出现我觉得 64 应该够了这种假设。顺带说一个更快排的实际问题。即便用了先压长区间后压短区间的优化最坏情况下的栈深度仍然是 O(n)。如果一个数组在划分时每次都极不均匀栈里会堆积 n 个区间。这在动态扩容下不会崩但内存占用会到sizeof(Range) * n如果n是几千万就是几百 MB够呛。真正能把这个上界压住的是**内省排序introsort**的思路记录当前递归/栈深度超过 2 * log2(n) 就切换到堆排序。C 标准库的std::sort就是这么做的保证了最坏 O(n log n)。C 语言里如果需要这个保证可以自己加一个深度计数器超限就调堆排序。这个改动不大对于要写通用库的人来说值得做。5.4 用对拍和 sanitizer 把问题提前暴露排序算法的 bug 有个特点大部分时候结果是对的只在特定数据下出错。手工造测试用例很难覆盖到位所以必须靠自动化。我的标准做法是对拍写一个绝对正确的参考实现比如冒泡排序慢但绝不会错然后随机生成大量测试数据两个实现各跑一遍比较结果。数据生成要特别注意两点一是值域要小比如rand() % 10这样能大量产生相等元素把稳定性相关的 bug 逼出来二是长度要覆盖边界从 0 到 1000 都跑一遍其中 0、1、2、3 这些特别容易出问题。static int check_sorted(const int *a, int n) { for (int i 1; i n; i) if (a[i - 1] a[i]) return 0; return 1; }验证排序结果是否正确除了看是否有序还要看元素多重集合是否一致。因为一个把元素搞丢了的排序算法剩下的部分可能仍然是有序的。简单的做法是排完后对两个数组各求一次和或者异或比对一下。当然求和对某些数据不敏感更严谨的做法是再排一次参考数组然后逐元素比较。另一个必备工具是 sanitizer。编译时加上-fsanitizeaddress,undefined -g能把数组越界、释放后使用、有符号溢出这些问题直接报出来定位到行号。我在写这段归并代码的时候就靠它抓到过一次memcpy长度算错的问题——right - left少加了 1最后一个元素没被搬回去。这种错误如果不加 sanitizer可能几百次测试里才偶发一次而且表现是结果差一点特别难查。gcc -stdc11 -Wall -Wextra -O2 -fsanitizeaddress,undefined -g sort_test.c -o sort_test-Wall -Wextra也要加上。排序代码里常见的比较有符号和无符号警告、隐式截断警告往往指向真实的逻辑问题别习惯性地忽略。6. 一份能直接编译的完整骨架6.1 结构组织与头文件把上面所有片段拼成完整程序需要注意函数声明顺序。我用一个sort.h放声明sort.c放实现main.c做测试这样编译和替换都方便。如果想偷懒全放一个文件也行但要保证merge在merge_sort_iter之前定义或者提前声明。需要的头文件就这几个#include stdio.h #include stdlib.h #include string.h #include time.hstring.h是给memcpy用的time.h是给计时用的。这里我特意不用qsort做参考实现因为它的行为依赖实现细节作为标准答案不够可靠。6.2 快排非递归的完整实现static void swap_int(int *x, int *y) { int t *x; *x *y; *y t; } static int partition(int *a, int left, int right) { int mid left ((right - left) 1); if (a[mid] a[left]) swap_int(a[mid], a[left]); if (a[right] a[left]) swap_int(a[right], a[left]); if (a[right] a[mid]) swap_int(a[right], a[mid]); /* 现在 a[left] a[mid] a[right]a[mid] 是中位数 */ swap_int(a[mid], a[right]); /* 中位数挪到最右边当枢轴 */ int key a[right]; int i left, j right; while (i j) { while (i j a[i] key) i; a[j] a[i]; while (i j a[j] key) j--; a[i] a[j]; } a[i] key; return i; }配合第 2 节的RangeStack和insert_sort_range主循环void quick_sort_iter(int *a, int n) { if (a NULL || n 2) return; RangeStack st; if (!rs_init(st)) return; if (!rs_push(st, 0, n - 1)) { rs_free(st); return; } Range cur; while (rs_pop(st, cur)) { int left cur.left, right cur.right; if (right - left 16) { insert_sort_range(a, left, right); continue; } int mid partition(a, left, right); if (mid - 1 - left right - mid - 1) { if (mid 1 right) rs_push(st, mid 1, right); if (left mid - 1) rs_push(st, left, mid - 1); } else { if (left mid - 1) rs_push(st, left, mid - 1); if (mid 1 right) rs_push(st, mid 1, right); } } rs_free(st); }这段代码我在多个项目里用过处理千万级随机数据没问题。记住它不能防住全相同元素的退化需要的话把partition换成三路划分版本。6.3 归并非递归与计时对比归并的完整调用形式int merge_sort_wrapper(int *a, int n) { if (a NULL || n 2) return 1; int *tmp (int *)malloc(sizeof(int) * (size_t)n); if (tmp NULL) return 0; merge_sort_iter(a, n, tmp); free(tmp); return 1; }外面包一层把malloc和free收进去调用方不用关心tmp的存在。返回int表示成功与否比用void然后靠全局变量报错干净。计时用clock()就够虽然它测的是 CPU 时间而不是墙钟时间但对于单线程排序这种纯计算任务两者基本一致static double now_sec(void) { return (double)clock() / (double)CLOCKS_PER_SEC; } int main(void) { const int n 1000000; int *a (int *)malloc(sizeof(int) * n); int *b (int *)malloc(sizeof(int) * n); if (!a || !b) return 1; srand(12345); for (int i 0; i n; i) a[i] rand(); memcpy(b, a, sizeof(int) * (size_t)n); double t0 now_sec(); quick_sort_iter(a, n); double t1 now_sec(); double t2 now_sec(); merge_sort_wrapper(b, n); double t3 now_sec(); printf(quick_iter : %.3f s, sorted%d\n, t1 - t0, check_sorted(a, n)); printf(merge_iter : %.3f s, sorted%d\n, t3 - t2, check_sorted(b, n)); printf(same content: %d\n, memcmp(a, b, sizeof(int) * (size_t)n) 0); free(a); free(b); return 0; }memcmp比较两个结果数组是验证正确性的快捷方式但前提是两边都排序正确——如果两个实现有同样的 bug比如都不稳定但恰好结果一样memcmp是看不出来的。所以还得靠前面的对拍流程。6.4 测试矩阵怎么设计才有效我通常准备一张数据矩阵每种数据类型跑一遍所有排序实现观察结果和耗时。这张表比任何解释都更能说明问题数据类型生成方式主要想暴露的问题完全随机rand()全值域通用性能基线大量重复rand() % 10快排退化、稳定性问题已升序直接0..n-1枢轴选取不当导致退化已降序n-1..0同上另一侧近乎有序升序后随机交换少量元素插入排序类算法的优势场景全相同全部填同一个值最极端的退化场景极短数组n 0, 1, 2, 3边界条件、空指针单元素越界n不是 2 的幂归并最后一段的处理把这张矩阵的每一行都对所有实现跑一遍比对结果、记录耗时基本能在提交代码前把绝大多数问题挡掉。尤其是大量重复和全相同两行这两行几乎是我见过的所有手写快排事故的源头。还有个细节值得单独提测试时不要只比较最终结果还要在每次排序前把数据备份下来排完比对确保原数据没被意外篡改。归并排序里memcpy长度算错、快排里区间越界写都可能导致排完后某些位置的值是野数据而最终结果看起来差不多有序check_sorted也过了。加上内容一致性检查才能兜住。我在实际使用中的体会是非递归改造带来的最大收益其实不是性能而是行为的可预测性。递归版在数据量变化时栈深度会跟着变不同平台上还受栈大小限制影响出问题时往往表现为大数组才崩、小数组正常非常难定位。换成显式的栈结构以后深度是个可观测、可打印、可设上限的量调试时把栈的top最大值打印出来看一眼心里立刻有数。至于性能非递归版本和加了小区间优化的递归版本基本在同一水平线上快排的主要耗时还是在partition的分支预测和内存访问上控制流的写法反而没那么关键。所以我现在的习惯是凡是自己手写排序一律非递归加动态栈既不是为了炫技也不是为了跑分纯粹是让半夜报警的时候能少排查半小时。