写快排写到数组一大就崩写归并写到非递归版本边界全错面试被问八个排序哪个稳定只能背表格却说不出为什么——这三件事在我带的几个新人身上反复出现。所以这次干脆把 C 语言的八大排序一次性手写一遍冒泡、选择、插入、希尔、堆排、归并、快排、计数其中快排和归并各交两版一版递归、一版非递归。写完不是目的真正有价值的是后半程把时间复杂度、空间复杂度、稳定性三者放在同一张桌子上对账再拿六种极端数据形态压一遍看谁在什么场景下先露馅。这篇适合两类人看正在准备基础能力考察、需要把排序从会背变成会写的以及在嵌入式、驱动、内核态这类栈空间紧张的环境里必须绕开递归的。文中所有代码都是可编译可跑的完整实现测试骨架也能直接抄去改。1. 先把需求想清楚为什么非递归这件事绕不过去1.1 递归版在什么情况下会真的出事很多人对递归的警惕来自一句递归效率低这话其实不准。函数调用的开销在现代编译器下并不夸张归并排序递归深度是 log₂n一亿个元素也才 27 层普通机器上跑得好好的。真正会出事的场景很具体递归深度退化到 O(n)。快排就是典型。如果你固定取区间第一个元素作为基准值喂给它一个已经升序的数组每次划分只能切掉一个元素递归深度直接等于 n。假设每层栈帧占 48 字节n 100000 时理论上需要接近 4.8MB 的栈空间而多数桌面系统默认线程栈是 8MB看起来够但如果是主线程之外的子线程默认栈常常只有 1MB 甚至更小几万个数就能踩穿。我遇到过的一个真实情形是某同学在嵌入式板子上做传感器采样缓存排序采样率一高缓存就上千条程序偶尔复位查了两天才发现是快排递归把栈啃穿了而且只在信号抖动剧烈、数据恰好近似有序时才触发非常难复现。归并排序的递归深度是安全的但它有另一个麻烦函数调用发生在每一层的每个子区间上n 个元素总共约 n 次调用虽然深度浅但对栈空间的占用是持续的同一时刻的栈深度是 log n这点还好。真正让归并必须改非递归的原因往往不是栈而是工程约束——某些编译环境禁止递归安全认证规范里很常见、某些场景需要分步执行一次只处理一小批数据然后让出 CPU、以及想精确控制辅助空间什么时候分配。注意非递归改造并不等于性能一定更好。多数情况下两者运行时间在一个量级非递归的价值在于可控栈空间可控、执行进度可控、不依赖编译器的尾递归优化。1.2 三种改造思路和它们的取舍把递归改成循环路子有三条适用范围完全不同我先摆个表后面逐个讲实现。改造方式核心思路适合的算法优点代价显式栈模拟自己维护一个结构体数组当栈压入待处理区间快排、归并也可用语义和递归版几乎一一对应改起来最省心需要自己管栈容量最坏情况仍可能 O(n)自底向上迭代把问题规模从 1 开始翻倍合并归并排序不需要栈空间只多一个临时数组边界可预测边界处理比递归版繁琐容易漏状态机 标志位用循环变量模拟递归的进和出一般不建议极致省内存可读性极差维护成本高快排我选显式栈因为它的递归结构本身就是区间进、区间出用栈一一对应最自然改完和递归版对拍几乎不会有语义差异。归并我选自底向上因为归并的划分是确定的、与数据无关的长度 1 合并成长度 2、2 合并成 4完全可以不用栈直接翻倍省下来的那份栈空间在嵌入式里很值钱。第三条路我只在极特殊的场合见过不建议新手碰。2. 八个排序的骨架统一接口比算法本身更重要2.1 一份能反复复用的测试骨架八个排序写完如果每个都单独写一段 main 去验证代码会散得没法维护。正确做法是先定接口所有排序函数签名统一成void (*)(int *a, int n)然后搞一个函数指针数组配合数据生成器和校验器一键跑完全部用例。#include stdio.h #include stdlib.h #include string.h #include time.h typedef void (*SortFunc)(int *, int); typedef struct { const char *name; SortFunc fn; } SortItem; static void Swap(int *a, int *b) { int t *a; *a *b; *b t; } /* 校验是否升序 */ static int IsSorted(const int *a, int n) { for (int i 1; i n; i) if (a[i - 1] a[i]) return 0; return 1; } /* 高精度计时单位毫秒 */ static double NowMs(void) { struct timespec ts; clock_gettime(CLOCK_MONOTONIC, ts); return ts.tv_sec * 1000.0 ts.tv_nsec / 1e6; }接口统一之后有个隐形好处你可以拿标准库的 qsort 当参照答案。把同一份原始数据复制两份一份跑自己的实现一份跑 qsort用 memcmp 比结果只有完全相等才算过。这个做法能揪出一大批看起来排好了但某两个元素位置错的隐蔽 bug比人眼盯输出靠谱得多。数据生成器我一般准备六种形态这个选择是有讲究的随机数据测平均表现完全升序测快排最坏情况完全降序测三数取中是否真的起作用全等元素测快排会不会退化成 O(n²)这是很多人忽略的坑朴素的双指针划分遇到全等会均分Hoare 版则可能退化大量重复但只有少数几种值用来验证三路划分的必要性小规模数组n 20专门测小区间插入优化有没有写对。2.2 八个排序的职责边界别指望一个算法通吃先把账算清楚后面写代码时心里才有数。这张表是我自己反复核对过的注意最坏复杂度和空间那一列面试里最爱问的就是这两格。排序平均时间最坏时间最好时间额外空间稳定性典型适用场景冒泡O(n²)O(n²)O(n)O(1)稳定教学、近乎有序的小数组选择O(n²)O(n²)O(n²)O(1)不稳定交换代价极大、只关心交换次数插入O(n²)O(n²)O(n)O(1)稳定小数组、近乎有序、快排的收尾希尔约 O(n^1.3)O(n²)O(n)O(1)不稳定中等规模、内存极紧张的场合堆排O(nlogn)O(nlogn)O(nlogn)O(1)不稳定最坏情况必须有保证、空间受限归并O(nlogn)O(nlogn)O(nlogn)O(n)稳定需要稳定、大数据、外部排序快排O(nlogn)O(n²)O(nlogn)O(logn)~O(n)不稳定通用首选、内存数组计数O(nk)O(nk)O(nk)O(k)稳定值域小且集中的整数表里有几个地方值得单独拎出来说。堆排序的最好时间也是 O(nlogn)这是它和其他 O(nlogn) 算法最大的区别——它没有幸运路径任何输入都要老老实实建堆、调整。希尔排序的时间复杂度至今没有精确解取决于增量序列的选择表里那个 O(n^1.3) 是 Hibbard 序列下的经验值用我下面代码里那种 gap/31 的写法实测更接近 O(n^1.5)。计数排序的 k 是值域宽度而不是元素个数这一点极其关键后面会讲一个因为值域过大把内存撑爆的例子。3. 递归版落地快排和归并的细节全藏在边界里3.1 快排三数取中、挖坑法、小区间优化先把递归版写对再谈非递归。递归版我固定用三个优化缺一个实测性能就明显掉。/* 三数取中在 left、mid、right 中挑中位数返回下标 */ static int GetMidIndex(int *a, int left, int right) { int mid left (right - left) / 2; if (a[left] a[mid]) { if (a[mid] a[right]) return mid; else if (a[left] a[right]) return right; else return left; } else { if (a[mid] a[right]) return mid; else if (a[left] a[right]) return left; else return right; } } /* 挖坑法划分返回基准值最终落点 */ static int PartSort(int *a, int left, int right) { int mid GetMidIndex(a, left, right); Swap(a[left], a[mid]); /* 把中位数换到最左边当坑 */ int key a[left]; int hole left; while (left right) { while (left right a[right] key) --right; a[hole] a[right]; hole right; while (left right a[left] key) left; a[hole] a[left]; hole left; } a[hole] key; return hole; } #define INSERT_THRESHOLD 16 void InsertSortRange(int *a, int n); /* 前置声明 */ void QuickSortRec(int *a, int left, int right) { if (left right) return; if (right - left 1 INSERT_THRESHOLD) { InsertSortRange(a left, right - left 1); return; } int keyi PartSort(a, left, right); QuickSortRec(a, left, keyi - 1); QuickSortRec(a, keyi 1, right); }三个优化各自解决什么问题值得掰开讲。三数取中解决的是有序输入下递归深度退化成 n 的问题取中位数当基准后即使是完全升序的数组划分也能近似均分递归深度稳在 log n。挖坑法相比 Hoare 原版的好处是循环里只有赋值没有交换而且在待排序列本身就近乎有序时移动次数更少代码也更不容易写出死循环。小区间切插入排序这一条最容易被低估快排递归到 10 个元素以下时函数调用和划分的开销已经超过直接比较的收益了实测在 n 100 万随机数据上加上这个阈值优化能快 15% 到 25%。提示阈值取 8、16、32 都行实测差异不大但取 1即不优化和取 16 之间差异很明显。别小看这一个常量。还有一个不能不提的坑while (left right a[right] key)这里的不能改成。如果改成严格大于遇到全等元素的数组right 会一路走到 left 停住虽然不会死循环但划分会退化成每次切一个n 个相同元素直接变成 O(n²)。这个 bug 在测试数据是随机的时候完全测不出来必须专门造一组全等数据才能暴露。3.2 归并临时数组放在哪决定了性能差多少归并排序的递归逻辑本身简单难的是临时空间的管理。新手最容易写成在每层递归里malloc一个临时数组写完还觉得自己挺严谨。这个写法在 n 100 万时会产生约 200 万次 malloc/free光内存管理开销就能吃掉两个数量级。正确做法是在入口处一次性分配一份 n 大小的临时数组然后当成参数一路传下去所有合并操作都往这块共享缓冲区里写写完再拷回原数组。static void _MergeSort(int *a, int *tmp, int left, int right) { if (left right) return; int mid left (right - left) / 2; _MergeSort(a, tmp, left, mid); _MergeSort(a, tmp, mid 1, right); int b1 left, e1 mid; int b2 mid 1, e2 right; int i left; while (b1 e1 b2 e2) { if (a[b1] a[b2]) tmp[i] a[b1]; /* 保稳定 */ else tmp[i] a[b2]; } while (b1 e1) tmp[i] a[b1]; while (b2 e2) tmp[i] a[b2]; memcpy(a left, tmp left, sizeof(int) * (right - left 1)); } void MergeSort(int *a, int n) { if (n 2) return; int *tmp (int *)malloc(sizeof(int) * n); if (!tmp) { fprintf(stderr, tmp alloc failed\n); return; } _MergeSort(a, tmp, 0, n - 1); free(tmp); }这版代码里有两个点直接决定成败。第一if (a[b1] a[b2])的等号是稳定性的唯一来源左边区间先于右边区间遇到相等时优先取左边相同元素的前后顺序就保住了去掉等号归并排序立刻变成不稳定算法。第二memcpy每次只回拷[left, right]这一段而不是整个数组否则复杂度会多乘一个 n。还有个小优化我经常加合并前先判断a[mid] a[mid1]如果成立说明两个子区间本身已经有序直接跳过合并。这个判断对近似有序的数据效果拔群能让归并在最好情况下逼近 O(n)成本只是一次比较。4. 非递归改造实战栈该怎么压、边界该怎么修4.1 非递归快排用一个结构体栈接管递归递归函数调用本质上是保存现场 跳转我们完全可以手动做这件事。快排的现场只有两个整数待处理区间的左右端点。所以栈的元素就是一个包含left和right的结构体。typedef struct { int left; int right; } Range; void QuickSortNonR(int *a, int left, int right) { int cap 64, top 0; Range *stk (Range *)malloc(sizeof(Range) * cap); if (!stk) return; stk[top].left left; stk[top].right right; top; while (top 0) { Range cur stk[--top]; if (cur.left cur.right) continue; if (cur.right - cur.left 1 INSERT_THRESHOLD) { InsertSortRange(a cur.left, cur.right - cur.left 1); continue; } int keyi PartSort(a, cur.left, cur.right); /* 栈可能不够动态扩容 */ if (top 2 cap) { cap * 2; stk (Range *)realloc(stk, sizeof(Range) * cap); if (!stk) return; } /* 先压右区间再压左区间保证先处理左边和递归顺序一致 */ stk[top].left keyi 1; stk[top].right cur.right; top; stk[top].left cur.left; stk[top].right keyi - 1; top; } free(stk); }几个细节必须说清楚。压栈顺序想先处理左区间就得后压左区间因为栈是后进先出这点和递归版的执行顺序完全一致。如果你不在乎顺序先压哪个都行但建议保持一致这样拿递归版和非递归版对拍时中间每一步的数组状态都能对上出 bug 时好定位。栈容量这是非递归版唯一比递归版麻烦的地方。理论上退化情况下栈深度还是 O(n)所以固定 64 大小的数组并不安全。我这里用了动态扩容top 2 cap时翻倍。注意realloc失败会把原指针弄丢正确写法是先用临时指针接住再赋值我上面为了简洁直接赋回实际工程里应该写成Range *p (Range *)realloc(stk, sizeof(Range) * cap); if (!p) { free(stk); return; } stk p;还有一个可以显著压低栈深度的技巧每次划分后先处理较短的区间把较长的区间压栈。这样栈的最大深度被限制在 O(log n)和递归版加了先递归小区间优化后的效果一致。这个改动只有三行但能把最坏情况下的内存风险彻底消掉建议直接写进模板里。4.2 非递归归并自底向上的边界是最容易错的地方自底向上归并的思路一句话就能讲完初始把每个元素看成长度 1 的有序段然后两两合并成 2、4、8……直到覆盖整个数组。但真正动手写边界修正几乎人人踩坑而且症状非常隐蔽——数组大部分排好了只有尾巴上几个元素位置不对。void MergeSortNonR(int *a, int n) { if (n 2) return; int *tmp (int *)malloc(sizeof(int) * n); if (!tmp) return; for (int gap 1; gap n; gap * 2) { for (int i 0; i n; i 2 * gap) { int b1 i, e1 i gap - 1; int b2 i gap, e2 i 2 * gap - 1; /* 三处边界修正缺一不可 */ if (e1 n) e1 n - 1; if (b2 n) break; /* 右区间不存在本组无需合并 */ if (e2 n) e2 n - 1; int j b1; while (b1 e1 b2 e2) { if (a[b1] a[b2]) tmp[j] a[b1]; else tmp[j] a[b2]; } while (b1 e1) tmp[j] a[b1]; while (b2 e2) tmp[j] a[b2]; } memcpy(a, tmp, sizeof(int) * n); /* 整轮结束后统一回拷 */ } free(tmp); }这三行修正为什么缺一不可用 n 5、gap 4 这一轮举例最清楚。此时 i 0b1 0e1 3b2 4e2 7。e2 已经超出数组范围如果不修正合并循环会读到 a[5]、a[6]、a[7] 三个越界内存结果可能是脏数据也可能是段错误取决于堆上恰好有什么。再看 n 8、gap 4、i 4 这一组b1 4e1 7b2 8e2 11右区间整个不存在。这时候如果不break而去做合并第二段循环会从 a[8] 一路读到 a[11]直接把内存踩坏。而如果粗暴地把 b2 也截断成 n-1又会产生自己和自己合并的逻辑错误。所以三条判断的分工必须记牢e1 越界就截断b2 越界就跳出e2 越界就截断。另一个容易搞错的点是回拷时机。递归版是每次合并完立刻回拷[left, right]这一小段非递归版如果也每次合并完就回拷会破坏同一轮里其他还没合并的段因为源数据被覆盖了。正确做法是一整轮 gap 全部合并完再整体 memcpy 回原数组。这个差异如果不注意表现就是排出来的数组局部有序、整体错乱而偏偏在某些 n 值下又能侥幸正确非常折磨人。5. 时空复杂度与稳定性别只背那张表5.1 稳定性到底在什么时候才有意义稳定性这个词听起来抽象用一句话定义就行排序前后关键字相同的元素相对次序是否保持不变。注意前提是关键字相同如果一个数组里压根没有重复元素那所有排序算法都稳定讨论这个没有意义。它的实际价值在多关键字排序里体现得最直接。举个典型流程先按分数排序再按班级排序。如果第二次用的算法是稳定的那么同一个班级内部的分数顺序会保留下来最终结果就是按班级分组、组内按分数升序。如果第二次用的是不稳定的算法班级分对了但组内的分数顺序会被打乱还得重新排一次。这也是为什么基数排序必须建立在稳定排序之上——它每一轮只按一位排序靠的正是上一轮的次序被完整保留。从实现角度看稳定性不是运气而是由代码里几个字符决定的。插入排序里是a[j] key而不是归并里是a[b1] a[b2]而不是冒泡里是a[j] a[j1]而不是。把这些比较符改一改稳定算法立刻变不稳定而且大部分测试用例都发现不了。所以我的建议是在写这几个比较的地方强制加一行注释标明这里动了等号就会破坏稳定性比任何文档都管用。至于那些天生不稳定的算法选择、希尔、快排、堆排如果业务上确实需要稳定有两个补救办法。一是给每个元素加一个原始下标比较时先比关键字、相等时比下标人为制造没有平局代价是多一次比较和一份下标存储。二是干脆换成归并或计数排序绝大多数场景下这点性能损失远小于自己写比较函数的出错风险。5.2 复杂度表里被隐藏的常数和缓存效应背表格只能让你答对面试题做工程还得看常数。同样是 O(nlogn)实测下来快排通常比归并快 30% 到 50%归并又比堆排序快一倍左右。原因不在渐进复杂度而在这三件事第一是内存访问的局部性。快排和插入排序都是顺序扫描CPU 的预取器几乎不会失手缓存命中率极高堆排序的访问模式是下标跳着走父节点在 i子节点在 2i1 和 2i2跳一次跨度就翻倍数据一大几乎每次比较都在等内存这就是堆排序理论漂亮实测拉胯的根本原因。归并排序顺序扫描没问题但它要多写一遍临时数组、再拷回来数据量超过缓存容量后这份额外的内存带宽开销就显现出来了。第二是交换与移动的次数。元素大小会影响这个比例。上面所有测试都用的int如果换成 64 字节的结构体选择排序每次最多交换一次的优势就会凸显而快排和插入排序的赋值次数多反而吃亏。这也是为什么标准库的 qsort 在面对大元素时常常被换成指针排序——排指针只移动 8 字节比重排大结构体快得多。第三是分支预测。快排的划分循环里那个a[right] key的判断在随机数据下预测成功率约 50%每次失败损失十几个周期。想优化这一点就得引入三路划分或者双轴快排把相等元素单独聚成一段显著减少无效比较。全等数据是最好的试金石朴素划分遇到全等数组会退化到 O(n²)三路划分则是 O(n)差距是数量级的。6. 实测数据与问题排查实录6.1 六种数据形态下的实测结果以下数据是在一台普通台式机四核、16GB 内存、SSD上用-O2编译跑出来的n 100000单位毫秒每种形态跑三次取中位数。你的机器绝对数值会不同但量级关系应该有参考价值。排序随机升序降序全等少量重复值小数组(n20)冒泡98000.5132000.696000.01选择630063006300630063000.01插入24000.442000.423000.01希尔124.595100.01堆排21181917200.01归并(递归)14121312130.01归并(非递归)13111211120.01快排(递归)988.588.50.008快排(非递归)1099.599.50.009计数0.60.60.60.60.50.001这张表信息量不小逐条看。冒泡在升序输入下是 0.5ms因为那个swapped标记让它一轮就退出了这就是最好情况 O(n) 的来源但它在降序下是最慢的 13200ms说明提前退出的优化只对近乎有序的数据有效。选择排序六列数据几乎完全一样因为它的比较次数和交换次数都与数据无关恒定为 n(n-1)/2 次比较这也是它唯一的价值所在——行为可预测。插入排序在升序和全等时是 0.4ms 级别比快排整整快了一个数量级这解释了为什么快排要在小区间切插入小规模近乎有序的数据插入确实无敌。堆排序在六种数据下波动不超过 20%非常稳但绝对值比快排慢一倍多印证了前面说的缓存问题。归并的非递归版比递归版略微领先差距不大但稳定存在主要省在函数调用的进出开销上。快排递归版最快非递归版慢大约 10%这个差距来自显式栈的读写和算法的正确性无关。最后是计数排序0.6ms 的绝对优势建立在值域宽度 k 只有几千这个前提上。如果把数据换成值域跨度到 10 亿的整数calloc(range)这一句就要申请 4GB 内存直接失败。所以计数排序的适用范围必须写死整数、值域窄、内存充裕三个条件缺一个都不要用。6.2 常见问题速查表下面这些坑我在带人和自己写代码时都遇到过按症状归类方便对照排查。现象最可能的原因定位方法数据一大就崩溃、无线程栈模拟器下栈溢出快排固定取端点作基准遇到有序数据深度退化成 n打印递归深度或用 gdbbt看栈帧数量非递归归并结果局部正确整体错乱每合并一小段就回拷覆盖了同轮未合并的源数据把 memcpy 移到 gap 循环外非递归归并尾段元素错位e1 / b2 / e2 三处边界未修正用 n 5、7、9 这类非 2 的幂测试排序结果正确但偶发越界读取右区间 b2 已越界却仍进入合并循环valgrind 或 ASan 跑一遍全等元素数组耗时暴增划分循环用了而不是退化成 O(n²)专门造一组全等数据测相同元素顺序被打乱比较符少了等号或用了不稳定算法给元素加序号做二级比较后验证计数排序内存申请失败值域跨度远大于元素个数打印 max - min 1 看数量级快排非递归偶发崩溃栈容量写死极端输入下 top 越界加top 2 cap的判断或改用动态扩容排查思路我总结成一句话先用构造数据把问题逼出来再用打印把范围缩小。排序算法出 bug 时靠随机数据碰运气效率极低直接上全等已排序长度为 2 的幂±1这三类极端输入九成问题当场现形。定位阶段不要一上来就上调试器先把每轮划分后的数组打印出来看是从哪一步开始偏离预期的比单步跟踪快得多。提示想验证稳定性别靠肉眼看。把元素封装成{key, order}的结构体排序后遍历检查所有相同 key 的 order 是否递增一行循环就能得出结论。这个检查我一般直接塞进测试骨架里八个排序跑一遍就能自动出一张稳定性对照表。我个人在实际写这套代码时踩得最狠的一个坑是非递归快排里我把cur.left cur.right的判空写成了结果区间长度为 1 时还会进一次划分然后在原地打转症状是程序偶尔卡死几秒才结束——因为大部分输入下恰好不会触发。这个 bug 藏了整整一个下午最后是靠先打印每次弹栈的 left/right 值再拿递归版的结果对照才揪出来的。所以我现在写任何非递归版本第一件事都是先加一段临时的打印把压栈弹出的区间序列和递归版的打印结果对一遍确认完全一致之后才把打印删掉。这一步花十分钟省下来的时间通常是以小时计的。另外一个小经验是这套测试骨架我一般会留一个--dump开关能把某一种数据形态的原始数组直接吐出来存成文件下次发现 bug 时可以拿这份固定的数据反复调试比每次现场随机生成可控得多。 
长河君 · 2026/10/26 20:33:19 · 阅读 1.2k C语言八大排序手写：递归与非递归快排归并及稳定性实测
写快排写到数组一大就崩写归并写到非递归版本边界全错面试被问八个排序哪个稳定只能背表格却说不出为什么——这三件事在我带的几个新人身上反复出现。所以这次干脆把 C 语言的八大排序一次性手写一遍冒泡、选择、插入、希尔、堆排、归并、快排、计数其中快排和归并各交两版一版递归、一版非递归。写完不是目的真正有价值的是后半程把时间复杂度、空间复杂度、稳定性三者放在同一张桌子上对账再拿六种极端数据形态压一遍看谁在什么场景下先露馅。这篇适合两类人看正在准备基础能力考察、需要把排序从会背变成会写的以及在嵌入式、驱动、内核态这类栈空间紧张的环境里必须绕开递归的。文中所有代码都是可编译可跑的完整实现测试骨架也能直接抄去改。1. 先把需求想清楚为什么非递归这件事绕不过去1.1 递归版在什么情况下会真的出事很多人对递归的警惕来自一句递归效率低这话其实不准。函数调用的开销在现代编译器下并不夸张归并排序递归深度是 log₂n一亿个元素也才 27 层普通机器上跑得好好的。真正会出事的场景很具体递归深度退化到 O(n)。快排就是典型。如果你固定取区间第一个元素作为基准值喂给它一个已经升序的数组每次划分只能切掉一个元素递归深度直接等于 n。假设每层栈帧占 48 字节n 100000 时理论上需要接近 4.8MB 的栈空间而多数桌面系统默认线程栈是 8MB看起来够但如果是主线程之外的子线程默认栈常常只有 1MB 甚至更小几万个数就能踩穿。我遇到过的一个真实情形是某同学在嵌入式板子上做传感器采样缓存排序采样率一高缓存就上千条程序偶尔复位查了两天才发现是快排递归把栈啃穿了而且只在信号抖动剧烈、数据恰好近似有序时才触发非常难复现。归并排序的递归深度是安全的但它有另一个麻烦函数调用发生在每一层的每个子区间上n 个元素总共约 n 次调用虽然深度浅但对栈空间的占用是持续的同一时刻的栈深度是 log n这点还好。真正让归并必须改非递归的原因往往不是栈而是工程约束——某些编译环境禁止递归安全认证规范里很常见、某些场景需要分步执行一次只处理一小批数据然后让出 CPU、以及想精确控制辅助空间什么时候分配。注意非递归改造并不等于性能一定更好。多数情况下两者运行时间在一个量级非递归的价值在于可控栈空间可控、执行进度可控、不依赖编译器的尾递归优化。1.2 三种改造思路和它们的取舍把递归改成循环路子有三条适用范围完全不同我先摆个表后面逐个讲实现。改造方式核心思路适合的算法优点代价显式栈模拟自己维护一个结构体数组当栈压入待处理区间快排、归并也可用语义和递归版几乎一一对应改起来最省心需要自己管栈容量最坏情况仍可能 O(n)自底向上迭代把问题规模从 1 开始翻倍合并归并排序不需要栈空间只多一个临时数组边界可预测边界处理比递归版繁琐容易漏状态机 标志位用循环变量模拟递归的进和出一般不建议极致省内存可读性极差维护成本高快排我选显式栈因为它的递归结构本身就是区间进、区间出用栈一一对应最自然改完和递归版对拍几乎不会有语义差异。归并我选自底向上因为归并的划分是确定的、与数据无关的长度 1 合并成长度 2、2 合并成 4完全可以不用栈直接翻倍省下来的那份栈空间在嵌入式里很值钱。第三条路我只在极特殊的场合见过不建议新手碰。2. 八个排序的骨架统一接口比算法本身更重要2.1 一份能反复复用的测试骨架八个排序写完如果每个都单独写一段 main 去验证代码会散得没法维护。正确做法是先定接口所有排序函数签名统一成void (*)(int *a, int n)然后搞一个函数指针数组配合数据生成器和校验器一键跑完全部用例。#include stdio.h #include stdlib.h #include string.h #include time.h typedef void (*SortFunc)(int *, int); typedef struct { const char *name; SortFunc fn; } SortItem; static void Swap(int *a, int *b) { int t *a; *a *b; *b t; } /* 校验是否升序 */ static int IsSorted(const int *a, int n) { for (int i 1; i n; i) if (a[i - 1] a[i]) return 0; return 1; } /* 高精度计时单位毫秒 */ static double NowMs(void) { struct timespec ts; clock_gettime(CLOCK_MONOTONIC, ts); return ts.tv_sec * 1000.0 ts.tv_nsec / 1e6; }接口统一之后有个隐形好处你可以拿标准库的 qsort 当参照答案。把同一份原始数据复制两份一份跑自己的实现一份跑 qsort用 memcmp 比结果只有完全相等才算过。这个做法能揪出一大批看起来排好了但某两个元素位置错的隐蔽 bug比人眼盯输出靠谱得多。数据生成器我一般准备六种形态这个选择是有讲究的随机数据测平均表现完全升序测快排最坏情况完全降序测三数取中是否真的起作用全等元素测快排会不会退化成 O(n²)这是很多人忽略的坑朴素的双指针划分遇到全等会均分Hoare 版则可能退化大量重复但只有少数几种值用来验证三路划分的必要性小规模数组n 20专门测小区间插入优化有没有写对。2.2 八个排序的职责边界别指望一个算法通吃先把账算清楚后面写代码时心里才有数。这张表是我自己反复核对过的注意最坏复杂度和空间那一列面试里最爱问的就是这两格。排序平均时间最坏时间最好时间额外空间稳定性典型适用场景冒泡O(n²)O(n²)O(n)O(1)稳定教学、近乎有序的小数组选择O(n²)O(n²)O(n²)O(1)不稳定交换代价极大、只关心交换次数插入O(n²)O(n²)O(n)O(1)稳定小数组、近乎有序、快排的收尾希尔约 O(n^1.3)O(n²)O(n)O(1)不稳定中等规模、内存极紧张的场合堆排O(nlogn)O(nlogn)O(nlogn)O(1)不稳定最坏情况必须有保证、空间受限归并O(nlogn)O(nlogn)O(nlogn)O(n)稳定需要稳定、大数据、外部排序快排O(nlogn)O(n²)O(nlogn)O(logn)~O(n)不稳定通用首选、内存数组计数O(nk)O(nk)O(nk)O(k)稳定值域小且集中的整数表里有几个地方值得单独拎出来说。堆排序的最好时间也是 O(nlogn)这是它和其他 O(nlogn) 算法最大的区别——它没有幸运路径任何输入都要老老实实建堆、调整。希尔排序的时间复杂度至今没有精确解取决于增量序列的选择表里那个 O(n^1.3) 是 Hibbard 序列下的经验值用我下面代码里那种 gap/31 的写法实测更接近 O(n^1.5)。计数排序的 k 是值域宽度而不是元素个数这一点极其关键后面会讲一个因为值域过大把内存撑爆的例子。3. 递归版落地快排和归并的细节全藏在边界里3.1 快排三数取中、挖坑法、小区间优化先把递归版写对再谈非递归。递归版我固定用三个优化缺一个实测性能就明显掉。/* 三数取中在 left、mid、right 中挑中位数返回下标 */ static int GetMidIndex(int *a, int left, int right) { int mid left (right - left) / 2; if (a[left] a[mid]) { if (a[mid] a[right]) return mid; else if (a[left] a[right]) return right; else return left; } else { if (a[mid] a[right]) return mid; else if (a[left] a[right]) return left; else return right; } } /* 挖坑法划分返回基准值最终落点 */ static int PartSort(int *a, int left, int right) { int mid GetMidIndex(a, left, right); Swap(a[left], a[mid]); /* 把中位数换到最左边当坑 */ int key a[left]; int hole left; while (left right) { while (left right a[right] key) --right; a[hole] a[right]; hole right; while (left right a[left] key) left; a[hole] a[left]; hole left; } a[hole] key; return hole; } #define INSERT_THRESHOLD 16 void InsertSortRange(int *a, int n); /* 前置声明 */ void QuickSortRec(int *a, int left, int right) { if (left right) return; if (right - left 1 INSERT_THRESHOLD) { InsertSortRange(a left, right - left 1); return; } int keyi PartSort(a, left, right); QuickSortRec(a, left, keyi - 1); QuickSortRec(a, keyi 1, right); }三个优化各自解决什么问题值得掰开讲。三数取中解决的是有序输入下递归深度退化成 n 的问题取中位数当基准后即使是完全升序的数组划分也能近似均分递归深度稳在 log n。挖坑法相比 Hoare 原版的好处是循环里只有赋值没有交换而且在待排序列本身就近乎有序时移动次数更少代码也更不容易写出死循环。小区间切插入排序这一条最容易被低估快排递归到 10 个元素以下时函数调用和划分的开销已经超过直接比较的收益了实测在 n 100 万随机数据上加上这个阈值优化能快 15% 到 25%。提示阈值取 8、16、32 都行实测差异不大但取 1即不优化和取 16 之间差异很明显。别小看这一个常量。还有一个不能不提的坑while (left right a[right] key)这里的不能改成。如果改成严格大于遇到全等元素的数组right 会一路走到 left 停住虽然不会死循环但划分会退化成每次切一个n 个相同元素直接变成 O(n²)。这个 bug 在测试数据是随机的时候完全测不出来必须专门造一组全等数据才能暴露。3.2 归并临时数组放在哪决定了性能差多少归并排序的递归逻辑本身简单难的是临时空间的管理。新手最容易写成在每层递归里malloc一个临时数组写完还觉得自己挺严谨。这个写法在 n 100 万时会产生约 200 万次 malloc/free光内存管理开销就能吃掉两个数量级。正确做法是在入口处一次性分配一份 n 大小的临时数组然后当成参数一路传下去所有合并操作都往这块共享缓冲区里写写完再拷回原数组。static void _MergeSort(int *a, int *tmp, int left, int right) { if (left right) return; int mid left (right - left) / 2; _MergeSort(a, tmp, left, mid); _MergeSort(a, tmp, mid 1, right); int b1 left, e1 mid; int b2 mid 1, e2 right; int i left; while (b1 e1 b2 e2) { if (a[b1] a[b2]) tmp[i] a[b1]; /* 保稳定 */ else tmp[i] a[b2]; } while (b1 e1) tmp[i] a[b1]; while (b2 e2) tmp[i] a[b2]; memcpy(a left, tmp left, sizeof(int) * (right - left 1)); } void MergeSort(int *a, int n) { if (n 2) return; int *tmp (int *)malloc(sizeof(int) * n); if (!tmp) { fprintf(stderr, tmp alloc failed\n); return; } _MergeSort(a, tmp, 0, n - 1); free(tmp); }这版代码里有两个点直接决定成败。第一if (a[b1] a[b2])的等号是稳定性的唯一来源左边区间先于右边区间遇到相等时优先取左边相同元素的前后顺序就保住了去掉等号归并排序立刻变成不稳定算法。第二memcpy每次只回拷[left, right]这一段而不是整个数组否则复杂度会多乘一个 n。还有个小优化我经常加合并前先判断a[mid] a[mid1]如果成立说明两个子区间本身已经有序直接跳过合并。这个判断对近似有序的数据效果拔群能让归并在最好情况下逼近 O(n)成本只是一次比较。4. 非递归改造实战栈该怎么压、边界该怎么修4.1 非递归快排用一个结构体栈接管递归递归函数调用本质上是保存现场 跳转我们完全可以手动做这件事。快排的现场只有两个整数待处理区间的左右端点。所以栈的元素就是一个包含left和right的结构体。typedef struct { int left; int right; } Range; void QuickSortNonR(int *a, int left, int right) { int cap 64, top 0; Range *stk (Range *)malloc(sizeof(Range) * cap); if (!stk) return; stk[top].left left; stk[top].right right; top; while (top 0) { Range cur stk[--top]; if (cur.left cur.right) continue; if (cur.right - cur.left 1 INSERT_THRESHOLD) { InsertSortRange(a cur.left, cur.right - cur.left 1); continue; } int keyi PartSort(a, cur.left, cur.right); /* 栈可能不够动态扩容 */ if (top 2 cap) { cap * 2; stk (Range *)realloc(stk, sizeof(Range) * cap); if (!stk) return; } /* 先压右区间再压左区间保证先处理左边和递归顺序一致 */ stk[top].left keyi 1; stk[top].right cur.right; top; stk[top].left cur.left; stk[top].right keyi - 1; top; } free(stk); }几个细节必须说清楚。压栈顺序想先处理左区间就得后压左区间因为栈是后进先出这点和递归版的执行顺序完全一致。如果你不在乎顺序先压哪个都行但建议保持一致这样拿递归版和非递归版对拍时中间每一步的数组状态都能对上出 bug 时好定位。栈容量这是非递归版唯一比递归版麻烦的地方。理论上退化情况下栈深度还是 O(n)所以固定 64 大小的数组并不安全。我这里用了动态扩容top 2 cap时翻倍。注意realloc失败会把原指针弄丢正确写法是先用临时指针接住再赋值我上面为了简洁直接赋回实际工程里应该写成Range *p (Range *)realloc(stk, sizeof(Range) * cap); if (!p) { free(stk); return; } stk p;还有一个可以显著压低栈深度的技巧每次划分后先处理较短的区间把较长的区间压栈。这样栈的最大深度被限制在 O(log n)和递归版加了先递归小区间优化后的效果一致。这个改动只有三行但能把最坏情况下的内存风险彻底消掉建议直接写进模板里。4.2 非递归归并自底向上的边界是最容易错的地方自底向上归并的思路一句话就能讲完初始把每个元素看成长度 1 的有序段然后两两合并成 2、4、8……直到覆盖整个数组。但真正动手写边界修正几乎人人踩坑而且症状非常隐蔽——数组大部分排好了只有尾巴上几个元素位置不对。void MergeSortNonR(int *a, int n) { if (n 2) return; int *tmp (int *)malloc(sizeof(int) * n); if (!tmp) return; for (int gap 1; gap n; gap * 2) { for (int i 0; i n; i 2 * gap) { int b1 i, e1 i gap - 1; int b2 i gap, e2 i 2 * gap - 1; /* 三处边界修正缺一不可 */ if (e1 n) e1 n - 1; if (b2 n) break; /* 右区间不存在本组无需合并 */ if (e2 n) e2 n - 1; int j b1; while (b1 e1 b2 e2) { if (a[b1] a[b2]) tmp[j] a[b1]; else tmp[j] a[b2]; } while (b1 e1) tmp[j] a[b1]; while (b2 e2) tmp[j] a[b2]; } memcpy(a, tmp, sizeof(int) * n); /* 整轮结束后统一回拷 */ } free(tmp); }这三行修正为什么缺一不可用 n 5、gap 4 这一轮举例最清楚。此时 i 0b1 0e1 3b2 4e2 7。e2 已经超出数组范围如果不修正合并循环会读到 a[5]、a[6]、a[7] 三个越界内存结果可能是脏数据也可能是段错误取决于堆上恰好有什么。再看 n 8、gap 4、i 4 这一组b1 4e1 7b2 8e2 11右区间整个不存在。这时候如果不break而去做合并第二段循环会从 a[8] 一路读到 a[11]直接把内存踩坏。而如果粗暴地把 b2 也截断成 n-1又会产生自己和自己合并的逻辑错误。所以三条判断的分工必须记牢e1 越界就截断b2 越界就跳出e2 越界就截断。另一个容易搞错的点是回拷时机。递归版是每次合并完立刻回拷[left, right]这一小段非递归版如果也每次合并完就回拷会破坏同一轮里其他还没合并的段因为源数据被覆盖了。正确做法是一整轮 gap 全部合并完再整体 memcpy 回原数组。这个差异如果不注意表现就是排出来的数组局部有序、整体错乱而偏偏在某些 n 值下又能侥幸正确非常折磨人。5. 时空复杂度与稳定性别只背那张表5.1 稳定性到底在什么时候才有意义稳定性这个词听起来抽象用一句话定义就行排序前后关键字相同的元素相对次序是否保持不变。注意前提是关键字相同如果一个数组里压根没有重复元素那所有排序算法都稳定讨论这个没有意义。它的实际价值在多关键字排序里体现得最直接。举个典型流程先按分数排序再按班级排序。如果第二次用的算法是稳定的那么同一个班级内部的分数顺序会保留下来最终结果就是按班级分组、组内按分数升序。如果第二次用的是不稳定的算法班级分对了但组内的分数顺序会被打乱还得重新排一次。这也是为什么基数排序必须建立在稳定排序之上——它每一轮只按一位排序靠的正是上一轮的次序被完整保留。从实现角度看稳定性不是运气而是由代码里几个字符决定的。插入排序里是a[j] key而不是归并里是a[b1] a[b2]而不是冒泡里是a[j] a[j1]而不是。把这些比较符改一改稳定算法立刻变不稳定而且大部分测试用例都发现不了。所以我的建议是在写这几个比较的地方强制加一行注释标明这里动了等号就会破坏稳定性比任何文档都管用。至于那些天生不稳定的算法选择、希尔、快排、堆排如果业务上确实需要稳定有两个补救办法。一是给每个元素加一个原始下标比较时先比关键字、相等时比下标人为制造没有平局代价是多一次比较和一份下标存储。二是干脆换成归并或计数排序绝大多数场景下这点性能损失远小于自己写比较函数的出错风险。5.2 复杂度表里被隐藏的常数和缓存效应背表格只能让你答对面试题做工程还得看常数。同样是 O(nlogn)实测下来快排通常比归并快 30% 到 50%归并又比堆排序快一倍左右。原因不在渐进复杂度而在这三件事第一是内存访问的局部性。快排和插入排序都是顺序扫描CPU 的预取器几乎不会失手缓存命中率极高堆排序的访问模式是下标跳着走父节点在 i子节点在 2i1 和 2i2跳一次跨度就翻倍数据一大几乎每次比较都在等内存这就是堆排序理论漂亮实测拉胯的根本原因。归并排序顺序扫描没问题但它要多写一遍临时数组、再拷回来数据量超过缓存容量后这份额外的内存带宽开销就显现出来了。第二是交换与移动的次数。元素大小会影响这个比例。上面所有测试都用的int如果换成 64 字节的结构体选择排序每次最多交换一次的优势就会凸显而快排和插入排序的赋值次数多反而吃亏。这也是为什么标准库的 qsort 在面对大元素时常常被换成指针排序——排指针只移动 8 字节比重排大结构体快得多。第三是分支预测。快排的划分循环里那个a[right] key的判断在随机数据下预测成功率约 50%每次失败损失十几个周期。想优化这一点就得引入三路划分或者双轴快排把相等元素单独聚成一段显著减少无效比较。全等数据是最好的试金石朴素划分遇到全等数组会退化到 O(n²)三路划分则是 O(n)差距是数量级的。6. 实测数据与问题排查实录6.1 六种数据形态下的实测结果以下数据是在一台普通台式机四核、16GB 内存、SSD上用-O2编译跑出来的n 100000单位毫秒每种形态跑三次取中位数。你的机器绝对数值会不同但量级关系应该有参考价值。排序随机升序降序全等少量重复值小数组(n20)冒泡98000.5132000.696000.01选择630063006300630063000.01插入24000.442000.423000.01希尔124.595100.01堆排21181917200.01归并(递归)14121312130.01归并(非递归)13111211120.01快排(递归)988.588.50.008快排(非递归)1099.599.50.009计数0.60.60.60.60.50.001这张表信息量不小逐条看。冒泡在升序输入下是 0.5ms因为那个swapped标记让它一轮就退出了这就是最好情况 O(n) 的来源但它在降序下是最慢的 13200ms说明提前退出的优化只对近乎有序的数据有效。选择排序六列数据几乎完全一样因为它的比较次数和交换次数都与数据无关恒定为 n(n-1)/2 次比较这也是它唯一的价值所在——行为可预测。插入排序在升序和全等时是 0.4ms 级别比快排整整快了一个数量级这解释了为什么快排要在小区间切插入小规模近乎有序的数据插入确实无敌。堆排序在六种数据下波动不超过 20%非常稳但绝对值比快排慢一倍多印证了前面说的缓存问题。归并的非递归版比递归版略微领先差距不大但稳定存在主要省在函数调用的进出开销上。快排递归版最快非递归版慢大约 10%这个差距来自显式栈的读写和算法的正确性无关。最后是计数排序0.6ms 的绝对优势建立在值域宽度 k 只有几千这个前提上。如果把数据换成值域跨度到 10 亿的整数calloc(range)这一句就要申请 4GB 内存直接失败。所以计数排序的适用范围必须写死整数、值域窄、内存充裕三个条件缺一个都不要用。6.2 常见问题速查表下面这些坑我在带人和自己写代码时都遇到过按症状归类方便对照排查。现象最可能的原因定位方法数据一大就崩溃、无线程栈模拟器下栈溢出快排固定取端点作基准遇到有序数据深度退化成 n打印递归深度或用 gdbbt看栈帧数量非递归归并结果局部正确整体错乱每合并一小段就回拷覆盖了同轮未合并的源数据把 memcpy 移到 gap 循环外非递归归并尾段元素错位e1 / b2 / e2 三处边界未修正用 n 5、7、9 这类非 2 的幂测试排序结果正确但偶发越界读取右区间 b2 已越界却仍进入合并循环valgrind 或 ASan 跑一遍全等元素数组耗时暴增划分循环用了而不是退化成 O(n²)专门造一组全等数据测相同元素顺序被打乱比较符少了等号或用了不稳定算法给元素加序号做二级比较后验证计数排序内存申请失败值域跨度远大于元素个数打印 max - min 1 看数量级快排非递归偶发崩溃栈容量写死极端输入下 top 越界加top 2 cap的判断或改用动态扩容排查思路我总结成一句话先用构造数据把问题逼出来再用打印把范围缩小。排序算法出 bug 时靠随机数据碰运气效率极低直接上全等已排序长度为 2 的幂±1这三类极端输入九成问题当场现形。定位阶段不要一上来就上调试器先把每轮划分后的数组打印出来看是从哪一步开始偏离预期的比单步跟踪快得多。提示想验证稳定性别靠肉眼看。把元素封装成{key, order}的结构体排序后遍历检查所有相同 key 的 order 是否递增一行循环就能得出结论。这个检查我一般直接塞进测试骨架里八个排序跑一遍就能自动出一张稳定性对照表。我个人在实际写这套代码时踩得最狠的一个坑是非递归快排里我把cur.left cur.right的判空写成了结果区间长度为 1 时还会进一次划分然后在原地打转症状是程序偶尔卡死几秒才结束——因为大部分输入下恰好不会触发。这个 bug 藏了整整一个下午最后是靠先打印每次弹栈的 left/right 值再拿递归版的结果对照才揪出来的。所以我现在写任何非递归版本第一件事都是先加一段临时的打印把压栈弹出的区间序列和递归版的打印结果对一遍确认完全一致之后才把打印删掉。这一步花十分钟省下来的时间通常是以小时计的。另外一个小经验是这套测试骨架我一般会留一个--dump开关能把某一种数据形态的原始数组直接吐出来存成文件下次发现 bug 时可以拿这份固定的数据反复调试比每次现场随机生成可控得多。