C语言实现快速排序：分区策略、递归深度与栈溢出优化

三年前带一个小项目做日志分析，需求很简单：把几百万条带时间戳的记录按时间排一遍再做统计。当时我随手写了个递归的快速排序算法交差，本地拿随机数据跑，几十毫秒就结束了，一切看起来都没问题。上线当天，同事把一份从旧系统导出的日志丢进去——那份数据本身就是按时间追加写入的，天然接近有序。程序跑了半分多钟，最后直接崩掉，报的是栈溢出。C语言实现快速排序算法这件事，代码不到二十行，几乎每个学过数据结构的人都能默写出来，但真正决定它能不能在真实数据上干活的，是分区策略、基准值选择、递归深度控制这些细节。这篇就把我自己反复改过的几版实现摊开讲，从最朴素的 Lomuto 分区一路写到三路划分和显式栈版本，附上完整可编译的源码，顺便把代码评审里被挑出来的坑一次说清楚。

1. 快排跑得快的真正原因，不在"分治"两个字上

1.1 同样是分治，归并和快排的常数差了一截

很多人第一次学排序，会觉得归并排序更"优雅"——稳定、最坏情况也是 O(n log n)，教科书上画的分治树整整齐齐。可实际跑起来，随机数据下归并往往比快排慢一截，差距有时候能到三成以上。原因不在算法复杂度，而在内存访问模式。归并排序每一趟合并都要把数据搬到一个 O(n) 大小的临时数组里，再从临时数组搬回来，等于每个元素至少被完整读写两次，而且这两次访问的地址跨度很大，缓存基本帮不上忙。快速排序是原地交换，一趟分区只在原数组上做读写，指针从左往右推进的时候，CPU 的预取器能提前把后面的缓存行拉进来，命中率高得多。

我用生活场景打个比方：归并排序像把一摞乱牌分成两堆放桌上，按顺序一张张挑出来再叠回去，手要在两个桌面之间来回伸；快排像直接在这摞牌内部左右手交换位置，从头到尾只碰这一个桌面。工作量看着差不多，但手上动作的跨度完全不是一个量级。这也是为什么标准库里的通用排序函数、多数语言内建排序，在内存数组上优先选快排系（或它的变种 introsort），而归并只在需要稳定性、或者数据在外部存储上时才更划算。

不过有个前提要说清楚：快排这个"快"是建立在分区均衡的基础上的。分成两半的时候，它是所有原地排序里常数最小的那个；分歪了，它就退化成 O(n²)，比冒泡还难看。后面几节的内容，本质上都是在处理"怎么保证不分成歪的"这一个问题。

1.2 递归树的分叉形状决定了总工作量

拆开看，快排的递归结构是这样的：每次选一个基准值，把数组划分成"小于等于基准"和"大于等于基准"两段，然后对两段分别递归。如果每次都能恰好对半分，递归树的高度是 log2(n)，每一层的所有分区加起来刚好扫描完整数组一遍，总比较次数约为 n·log2(n)。一百万条数据，log2(1000000) 大约是 20，总操作量两千万次量级，在现代 CPU 上确实就是百毫秒以内的事情。

但如果每次分区只能切掉一个元素呢？递归树就退化成了链表，高度变成 n，总操作量变成 n² 级别，而且每一层都伴随着一次递归调用。一百万条数据，两千万次变成一万亿次，这不是"慢一点"的问题，是根本跑不完。更致命的是递归深度也跟着变成了一百万层，每个栈帧按 48 到 64 字节算，光栈就要吃掉几十兆，而线程栈默认只有 1MB 到 8MB，直接就是栈溢出崩溃。

所以判断一份快排实现好不好，标准其实很朴素：在随机数据、已排序、逆序、全相等等几种极端形态下，它的递归深度是不是都能压在 O(log n) 附近。能做到，它就是可靠的；做不到，它在实验室里跑得再快也没意义。

1.3 分区函数里的那个不变量，是全部正确性的来源

写分区函数的时候，脑子里必须时刻装着一个"循环不变量"——在循环的每一步，数组的几个区间各自满足什么性质。以经典的 Lomuto 方案为例，循环过程中始终保持三个区间：[low, i]里的元素全部小于等于基准值，(i, j)里的元素全部大于基准值，[j, high-1]是还没检查的部分。每读一个a[j]，根据它和基准值的关系决定是把它并入左边区间（通过和a[i+1]交换）还是留在右边区间，然后j前进一格。

这个不变量写清楚了，代码的正确性几乎是自明的，调试的时候也知道该在哪一行打日志。反之，如果只是背下了那几行代码，遇到边界条件（比如空数组、单元素、全相等）就很容易改错一个<=或++的位置，然后陷入"结果大部分对，偶尔错几个"的噩梦。我见过不少人的实现是在某个<和<=上翻车的，症状是数组里有大量重复元素时顺序错乱，但随机数据测试完全正常，特别隐蔽。

2. 第一版 Lomuto 分区：最好写，也最容易翻车

2.1 二十行就能跑起来的完整代码

先给一版最直白的实现，选最后一个元素作为基准，用单指针扫描。这版代码我建议每个人都手敲一遍，因为它是后面所有优化的出发点。

#include <stdio.h> static void swap_int(int *a, int *b) { int t = *a; *a = *b; *b = t; } /* Lomuto 分区：以 a[high] 为基准 */ static int partition_lomuto(int a[], int low, int high) { int pivot = a[high]; int i = low - 1; /* i 指向"小于等于区"的最后一个位置 */ for (int j = low; j < high; j++) { if (a[j] <= pivot) { i++; swap_int(&a[i], &a[j]); } } swap_int(&a[i + 1], &a[high]); /* 基准归位 */ return i + 1; } void quick_sort_basic(int a[], int low, int high) { if (low >= high) return; int p = partition_lomuto(a, low, high); quick_sort_basic(a, low, p - 1); quick_sort_basic(a, p + 1, high); }

i初始化为low - 1表示"小于等于区"一开始是空的，这个写法在low == 0的时候依然是合法的，因为i只是个下标变量，low - 1不会真的被解引用。分区结束后i + 1就是基准值的最终位置，它左边的都不大于它，右边的都不小于它，位置已经确定，后续递归不用再碰它。

顺手给一个能直接编译跑的测试主函数：

int main(void) { int a[] = {5, 2, 9, 1, 5, 6, 3, 8, 5, 0}; int n = (int)(sizeof(a) / sizeof(a[0])); quick_sort_basic(a, 0, n - 1); for (int i = 0; i < n; i++) printf("%d ", a[i]); putchar('\n'); return 0; }

编译命令用gcc -O2 -std=c11 -Wall -Wextra -o qsort_demo qsort_demo.c，-Wall -Wextra一定要开，它至少能帮你挡住"有符号和无符号比较"这类隐性错误。

2.2 有序数组上退化成 O(n²) 的完整推演

现在把刚才那份接近有序的日志数据代入这套代码，看看会发生什么。假设数组已经升序排列[1, 2, 3, ..., n]，每次取a[high]作为基准，也就是当前区间的最大值。分区的时候，a[j] <= pivot对每一个j都成立，所以i会一路跟到high - 1，最后基准值留在原地，p返回high。递归的下一层是quick_sort_basic(a, low, high - 1)——只把区间缩小了一个元素。

换成递推关系就是 T(n) = T(n-1) + O(n)，解开是 O(n²)。同时递归深度是 n，每层一个栈帧。我实测过，一百万个已排序的 int，这版代码在常规桌面环境上跑了两分多钟还没结束（后来手动掐掉了），而随机数据只需要几十毫秒，差距接近四个数量级。这个对比我建议每个写快排的人都亲手做一遍，印象比看十遍复杂度分析都深。

逆序数据是一模一样的结局，因为基准值每次都是当前区间的最小值，同样只能切掉一个元素。这就解释了一个反直觉的现象：很多排序算法在"看起来最容易处理"的有序数据上表现最差。做性能测试如果只测随机数据，等于把最危险的情况整个跳过了。

2.3 递归深度和栈帧大小，决定了它会在什么时候崩

栈溢出的临界点可以直接算。Linux 下主线程默认栈 8MB，pthread 创建的线程默认也是 8MB 但很多框架会调小到 1MB 甚至 256KB；Windows 下默认 1MB。每个递归栈帧里保存返回地址、上一层的low/high/p等局部变量，在 x86-64 上通常 48 到 64 字节，加上编译器的对齐填充，实际可能到 80 字节。

按 64 字节保守估算，1MB 栈最多容纳大约 16000 层递归。也就是说，只要数据量超过一万六千且恰好有序，这版实现在默认线程栈上就会崩。嵌入式环境更夸张，有的 RTOS 任务栈只有 4KB，几百层就爆了。这也解释了为什么很多老代码里会看到quick_sort(a, low, high)前面加了个if (high - low < SOME_LIMIT)的判断然后转去调用插入排序——那不是在优化性能，纯粹是在保命。

3. 换成 Hoare 双边扫描：指针怎么走才不越界

3.1 挖坑法为什么必须先从右边开始动

Hoare 原始版思路是左右两个指针相向而行，左边找比基准大的，右边找比基准小的，找到就交换。具体实现上有两种风格：交换式和挖坑式。我偏爱挖坑式，代码更短，交换次数也更少。

/* 挖坑法：先把 a[low] 存起来，这个位置变成"坑" */ static int partition_pit(int a[], int low, int high) { int pivot = a[low]; int i = low, j = high; while (i < j) { while (i < j && a[j] >= pivot) j--; /* 从右往左找小于 pivot 的 */ a[i] = a[j]; /* 填到左边的坑里，j 位置变成新坑 */ while (i < j && a[i] <= pivot) i++; /* 从左往右找大于 pivot 的 */ a[j] = a[i]; /* 填到右边的坑里，i 位置变成新坑 */ } a[i] = pivot; /* 最后剩下的坑放基准值 */ return i; }

这里有个被问过无数遍的问题：为什么必须先动j而不是先动i？因为a[low]的值已经被pivot保存了，low位置是初始的"坑"。如果先动i往右走，找到大于pivot的元素后执行a[j] = a[i]，而此时j还停在high，a[high]的值还没被保存，直接就被覆盖了，数据丢失。反过来先动j，j找到小于pivot的值填进low的坑，low的值已经在pivot里了，安全。

这个顺序本质上是由"坑在哪一侧"决定的，记住这个原理就永远不会记反。顺带说一句，挖坑法在数组元素是大结构体的时候优势明显——交换式每次要搬整个结构体，挖坑式只搬两次赋值，能省一半的写入量。如果是几百字节的结构体，这个差距相当可观。

3.2 三数取中：把最坏情况的概率压下去

挖坑法本身不解决有序数据退化的问题，因为基准还是取第一个元素，有序时依然只切掉一个。必须在选基准上做文章。常见的三种做法：随机取、三数取中、九数取中。

随机取需要调用rand()，一是本身有开销（即使是很便宜的 PRNG，每层递归调一次累积起来也不少），二是结果不可复现，调试的时候很痛苦。九数取中效果好但常数大，对小数组不划算。折中的三数取中是工程上最常用的：

static void swap_int(int *a, int *b) { int t = *a; *a = *b; *b = t; } /* 取 a[low]、a[mid]、a[high] 的中位数，换到 a[low] 位置 */ static int median_of_three(int a[], int low, int high) { int mid = low + (high - low) / 2; if (a[mid] < a[low]) swap_int(&a[mid], &a[low]); if (a[high] < a[low]) swap_int(&a[high], &a[low]); if (a[high] < a[mid]) swap_int(&a[high], &a[mid]); /* 三步之后 a[low] <= a[mid] <= a[high] */ swap_int(&a[mid], &a[low]); return a[low]; }

注意mid的算法写的是low + (high - low) / 2而不是(low + high) / 2。后者在low和high都接近INT_MAX时会整型溢出变成负数，导致数组越界访问。虽然实际业务里数组下标不太可能逼近二十亿，但这个写法属于"零成本的正确性"，没有任何理由不用。这个坑在二分查找里更出名，快排这里原理一样。

三数取中之后，已排序数组的最坏情况基本被消灭了——因为有序时a[mid]天然就是中位数，每次都精准对半分。但要注意，它只是"大幅降低"最坏情况出现的概率，不是"杜绝"。构造一组专门针对三数取中的对抗数据，还是能让它退化成 O(n²)。真要彻底防住，得上 introsort 那种"递归深度超过 2·log2(n) 就切堆排序"的兜底策略，那是另一个层面的工程问题了。

3.3 小区间切插入排序，省掉的是函数调用不是比较

递归到区间只剩七八个元素的时候，继续快排其实很亏。一层层递归下去的基准值选择、分区扫描、函数调用压栈，开销加起来可能比直接把这几元素排序还大。而且小数组上快排的"分而治之"优势完全体现不出来——你分得再细，也还是要处理同样多的元素。

业界通行的做法是设一个阈值，区间长度小于阈值时直接上插入排序。通常取 8 到 32 之间，不同测试环境下最优值略有浮动，16 是个很稳的选择。

#define INSERTION_THRESHOLD 16 static void insertion_sort(int a[], int low, int high) { for (int i = low + 1; i <= high; i++) { int key = a[i]; int j = i - 1; while (j >= low && a[j] > key) { a[j + 1] = a[j]; j--; } a[j + 1] = key; } }

插入排序在这里的另一个隐性优势是：它对"接近有序"的小数组特别快，而快排分区之后的小块往往本身就是半有序的，插入排序正好能吃到这个红利。这也是为什么 STL 的 sort 和小数组排序的连接处用的都是插入排序，这不是拍脑袋定的，是反复测出来的。

4. 大量重复元素时，二路划分彻底失效

4.1 全等数组上发生了什么

前面两种分区方案有个共同的隐含假设：数组元素是"近似互不相同的"。一旦数据里全是重复值，比如一个统计结果数组里百分之九十都是 0，情况会变得非常难看。

以挖坑法为例，假设数组全部等于 5。基准pivot = 5，进入循环后while (i < j && a[j] >= pivot) j--会一路把j降到low，然后a[i] = a[j]自己赋值给自己；接着while (i < j && a[i] <= pivot) i++因为i已经不小于j了，直接跳过。循环结束，i == low，分区返回low。递归变成quick_sort(a, low, low-1)（空区间）和quick_sort(a, low+1, high)，每次还是只切掉一个元素。

结果就是 O(n²)，和有序数组的问题一模一样，只是原因从"基准选偏了"变成了"重复值让两个指针都推不动"。这类数据在真实业务里其实非常常见：状态字段、性别字段、评分字段，取值就那么几个，大量重复。

4.2 荷兰国旗划分：一趟把数组切成三段

解决办法是三路划分，也叫荷兰国旗问题（因为荷兰国旗是三色条纹，正好对应小于、等于、大于三段）。核心思路是在一趟分区里同时处理等于基准值的元素，把它们全部聚到中间，下次递归完全跳过这一段。

void quick_sort_3way(int a[], int low, int high) { if (low >= high) return; int pivot = a[low]; int lt = low; /* [low, lt) 小于 pivot */ int gt = high; /* (gt, high] 大于 pivot */ int i = low + 1; /* [lt, i) 等于 pivot，[i, gt] 未处理 */ while (i <= gt) { if (a[i] < pivot) { swap_int(&a[i], &a[lt]); i++; lt++; } else if (a[i] > pivot) { swap_int(&a[i], &a[gt]); gt--; /* 换过来的元素还没检查，i 不动 */ } else { i++; /* 等于 pivot，直接并入中段 */ } } quick_sort_3way(a, low, lt - 1); quick_sort_3way(a, gt + 1, high); }

三个指针的分工要理解透：lt左边全是小于基准的，i前面到lt之间全是等于基准的，gt右边全是大于基准的。i和gt之间是未处理区。每次循环处理a[i]：

• 小于基准，就把它换到lt位置（那个位置存的是等于基准的值，换过来放i位置后仍然在中段范围内），然后i和lt一起前进；
• 大于基准，就把它换到gt位置，gt后退一格。注意这里i不能动，因为从gt换过来的值还没检查过；
• 等于基准，直接i++，把它留在中段。

用全等数组验证一下：每次都是走else分支i++，循环跑一遍结束，lt还是low，gt还是high，递归的两次调用分别是(low, low-1)和(high+1, high)，都是空区间，直接返回。一趟 O(n) 搞定，完美。

4.3 选哪个版本，看数据分布而不是看谁"高级"

三路划分不能无脑替代二路。它的常数更大——每次循环要做两次比较（<和>），而二路只需要一次。在元素几乎互不相同的随机数据上，三路划分的实测耗时要高出 10% 到 15%。

所以选型逻辑应该反过来：先看数据分布，再定方案。业务里如果排序的是 ID、时间戳、金额这类天然高基数的字段，老老实实用二路 + 三数取中就够了。如果是状态码、等级、类别这类低基数字段，或者数据来源不明（比如用户上传的、外部接口来的），直接上三路划分更保险，宁可慢那百分之十几，也不能让它在某个特定输入上炸掉。

保守一点的做法是把两者结合起来：先跑一次三路划分，如果发现中间段的长度超过区间的一半，说明数据重复率很高，接下来继续用三路；否则剩下的子区间切换回二路。libstdc++ 里的std::sort大致就是这种混合思路，只不过实现更复杂。

5. 把递归换成显式栈，控制权拿回自己手里

5.1 先处理小区间，栈深自然就压到了 log n

上一节的三路划分解决了重复元素的问题，递归深度还是会受数据影响。递归深度不可控这件事在某些场合是真要命的：跑在 RTOS 小栈任务里的代码、跑在协程里的代码、深度不可预知的外部输入，一旦爆栈整个进程就没了，而且崩的位置和原因都很随机，排查极困难。

有两个层次的解法。轻量的那个叫尾递归消除，思路是：每次分区后，只对较短的那一半做递归，较长的那一半用循环继续处理。

void quick_sort_tail(int a[], int low, int high) { while (low < high) { if (high - low + 1 <= INSERTION_THRESHOLD) { insertion_sort(a, low, high); return; } int p = partition_pit(a, low, high); if (p - low < high - p) { quick_sort_tail(a, low, p - 1); /* 短的递归 */ low = p + 1; /* 长的用循环 */ } else { quick_sort_tail(a, p + 1, high); high = p - 1; } } }

因为每次递归处理的都是不超过一半的区间，递归深度被数学上限制在 log2(n) 以内。一百万数据最多 20 层，一亿数据也就 27 层，这个深度对任何正常栈来说都是安全的。这个改动只有几行，但效果立竿见影，是所有快排实现里性价比最高的优化。

5.2 显式栈版本：完全不用递归也可以

如果连 log n 层的递归都不想要（比如目标平台的栈只有几 KB），那就得上显式栈。用数组模拟一个后进先出的栈，把待处理的区间下标对压进去，循环里不断弹出处理。

#define STACK_CAP 64 void quick_sort_iter(int a[], int n) { if (n < 2) return; int stack[STACK_CAP][2]; int top = 0; stack[top][0] = 0; stack[top][1] = n - 1; top++; while (top > 0) { top--; int low = stack[top][0]; int high = stack[top][1]; while (low < high) { if (high - low + 1 <= INSERTION_THRESHOLD) { insertion_sort(a, low, high); break; } int p = partition_pit(a, low, high); /* 与尾递归消除同样的策略：短的直接处理，长的压栈 */ if (p - low < high - p) { if (p + 1 < high) { stack[top][0] = p + 1; stack[top][1] = high; top++; } high = p - 1; } else { if (low < p - 1) { stack[top][0] = low; stack[top][1] = p - 1; top++; } low = p + 1; } } } }

这里的关键是压栈顺序。每次分区后，选择较长的那半边压栈、较短的那半边当场继续。这样栈里保存的永远是"待处理的较大区间"，而它们的长度是逐层递减的：第一层压进去的最多 n/2，第二层最多 n/4，以此类推。所以栈的最大深度是 log2(n) + 1。

STACK_CAP取 64 意味着能支持 2^64 量级的数组，实际上 32 就绰绰有余了（2^32 是四十多亿个元素）。留 64 是为了对齐和留余量，栈上多占 64×2×4 = 512 字节，可以忽略不计。如果真怕溢出，可以在top++之前加一句if (top >= STACK_CAP) abort();做个断言，虽然按上面的分析不可能触发。

用显式栈还有个附带好处：整个函数没有递归调用，栈帧大小固定，通过-fstack-usage编译选项能精确知道它占多少字节，这对嵌入式场景的栈规划很有用。

6. 实测对比与几个在评审里最常被挑出来的问题

6.1 和标准库 qsort 的横向对比

写完自己的实现，最自然的疑问是：跟 C 标准库的qsort比怎么样？我做过一轮测试，一百万个 int，同一台机器，gcc -O2，结果大致是这样的形态（给相对倍数，绝对值受机器差异太大意义不大）：

自己写的版本能比qsort快三成左右，主要原因不是算法更好，而是qsort的比较必须通过函数指针进行，编译器没法内联，每次比较都是一次真实的间接调用跳转，分支预测和寄存器分配都被打断。自己实现的版本里a[j] <= pivot是内联的直接比较，快得多。

全相等数据那一栏也验证了前面的分析：三路划分赢了四倍，而二路方案（无论有没有三数取中）跟qsort打平——说明标准库的实现面对重复元素同样没什么好办法，这是二路划分的固有限制，不是实现质量的问题。

顺带提一句qsort的另一个隐性短板：它的比较函数返回int，做整型比较时很多人写成return a - b;，在a是INT_MIN、b是正数的时候直接溢出，返回值的符号就错了，排序结果跟着乱。安全写法是return (x > y) - (x < y);，两个布尔表达式相减，结果只有 -1、0、1 三种，永远不会溢出。这个技巧值得记住，凡是涉及到"三向比较"的地方都能用。

6.2 代码评审里最常被点名的几个写法问题

把这几版代码发给同事看，反复被挑出来的问题集中在这么几个地方，都是小细节但都能真的引发 bug：

第二条和第三条我在不同项目里都见过真实事故。第一条相对少见，但只要踩上一次，症状是"数据偶尔错位"，比直接崩溃难查十倍——因为出错的概率和编译器的优化等级相关，-O0下可能完全正常，-O2下就出错。

还有一条不在表里但同样重要：快速排序是不稳定排序。相等元素的相对顺序会被打乱。如果业务上依赖这个顺序（比如按时间排序之后再按状态分组，希望同状态内保持时间序），就得换成归并排序或者加一个原始下标作为第二关键字。这个在需求评审阶段就该确认清楚，等上线了才发现就麻烦了。

6.3 一份可以直接拿去用的完整实现

最后把前面所有优化合到一起，给一份完整的、可以直接编译运行的代码。这份代码我做过去重和整理，接口跟常规习惯保持一致。

/* quicksort.c —— C11 编译：gcc -O2 -std=c11 -Wall -Wextra quicksort.c */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #define INSERTION_THRESHOLD 16 #define STACK_CAP 64 static inline void swap_int(int *a, int *b) { int t = *a; *a = *b; *b = t; } static void insertion_sort(int a[], int low, int high) { for (int i = low + 1; i <= high; i++) { int key = a[i]; int j = i - 1; while (j >= low && a[j] > key) { a[j + 1] = a[j]; j--; } a[j + 1] = key; } } static int median_of_three(int a[], int low, int high) { int mid = low + (high - low) / 2; if (a[mid] < a[low]) swap_int(&a[mid], &a[low]); if (a[high] < a[low]) swap_int(&a[high], &a[low]); if (a[high] < a[mid]) swap_int(&a[high], &a[mid]); swap_int(&a[mid], &a[low]); return a[low]; } static int partition_pit(int a[], int low, int high) { int pivot = median_of_three(a, low, high); int i = low, j = high; 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; } /* 统一入口，内部用显式栈，任意数据形态下栈深都不超过 log2(n)+1 */ void quick_sort(int a[], int n) { if (a == NULL || n < 2) return; int stack[STACK_CAP][2]; int top = 0; stack[top][0] = 0; stack[top][1] = n - 1; top++; while (top > 0) { top--; int low = stack[top][0], high = stack[top][1]; while (low < high) { if (high - low + 1 <= INSERTION_THRESHOLD) { insertion_sort(a, low, high); break; } int p = partition_pit(a, low, high); if (p - low < high - p) { if (p + 1 < high) { stack[top][0] = p + 1; stack[top][1] = high; top++; } high = p - 1; } else { if (low < p - 1) { stack[top][0] = low; stack[top][1] = p - 1; top++; } low = p + 1; } } } } /* 对拍验证：与标准库 qsort 逐字节比对 */ static int cmp_int(const void *pa, const void *pb) { int x = *(const int *)pa, y = *(const int *)pb; return (x > y) - (x < y); } static void fill_case(int a[], int n, int kind) { unsigned seed = 12345u; for (int i = 0; i < n; i++) { seed = seed * 1103515245u + 12345u; int r = (int)((seed >> 16) & 0x7fff); switch (kind) { case 0: a[i] = r; break; /* 随机 */ case 1: a[i] = i; break; /* 已升序 */ case 2: a[i] = n - i; break; /* 已降序 */ case 3: a[i] = 7; break; /* 全部相等 */ case 4: a[i] = (i & 1) ? 1 : 0; break; /* 两组交替 */ default: a[i] = r; break; } } } int main(void) { const int n = 200000; int *a = malloc(sizeof(int) * (size_t)n); int *b = malloc(sizeof(int) * (size_t)n); if (!a || !b) { free(a); free(b); return 1; } const char *names[] = {"随机", "升序", "降序", "全相等", "两组交替"}; for (int k = 0; k < 5; k++) { fill_case(a, n, k); memcpy(b, a, sizeof(int) * (size_t)n); quick_sort(a, n); qsort(b, (size_t)n, sizeof(int), cmp_int); printf("%-8s : %s\n", names[k], memcmp(a, b, sizeof(int) * (size_t)n) == 0 ? "通过" : "失败"); } free(a); free(b); return 0; }

这个对拍思路我觉得比任何单元测试都省钱：直接把标准库的排序结果当成基准答案，逐字节比对。标准库实现经过几十年打磨，正确性上基本不需要怀疑，用它当参照可以一次性覆盖所有边界情况。测试数据构造上我放了五种形态，涵盖随机、有序、逆序、重复和部分重复，正好对应前面分析的几类高危场景。

要真跑性能对比，再把quick_sort前后用clock_gettime(CLOCK_MONOTONIC, ...)卡一下时间就行。注意在较老的 glibc 上可能需要链接-lrt，并且要在文件最前面加#define _POSIX_C_SOURCE 199309L才能让clock_gettime的声明可见，这个坑我在不同发行版上踩过好几次，症状是"隐式声明警告 + 运行结果偶尔不对"。

最后分享一个我自己踩出来的小经验：调快排这类代码，编译器优化等级对结论影响极大。-O0下测出来的结果基本没有参考价值，因为它把内联优化全关了，连swap_int都要真的走一次函数调用。做任何性能判断统一用-O2，要更激进可以试-O3 -march=native，但拿-O2的数据做决策比较稳妥，也最接近实际发布产物。另一件事是，调试边界问题时先把INSERTION_THRESHOLD临时改成 1 再测，这样小数组也走完整的快排路径，能把藏在阈值切换处的 bug 暴露出来，等验证完了再改回去。这个手法在处理任何"加了优化之后才出错"的问题时都很好使。