三年前带一个小项目做日志分析需求很简单把几百万条带时间戳的记录按时间排一遍再做统计。当时我随手写了个递归的快速排序算法交差本地拿随机数据跑几十毫秒就结束了一切看起来都没问题。上线当天同事把一份从旧系统导出的日志丢进去——那份数据本身就是按时间追加写入的天然接近有序。程序跑了半分多钟最后直接崩掉报的是栈溢出。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[i1]交换还是留在右边区间然后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 -stdc11 -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 下主线程默认栈 8MBpthread 创建的线程默认也是 8MB 但很多框架会调小到 1MB 甚至 256KBWindows 下默认 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还停在higha[high]的值还没被保存直接就被覆盖了数据丢失。反过来先动jj找到小于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, low1, 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还是lowgt还是high递归的两次调用分别是(low, low-1)和(high1, 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三数取中插入排序三路划分版本完全随机基准 1.00.65 左右0.75 左右已升序基准 1.00.7 左右0.8 左右已降序基准 1.00.7 左右0.8 左右全部相等基准 1.01.0 左右0.25 左右两组值交替基准 1.01.0 左右0.3 左右自己写的版本能比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问题写法风险正确做法#define SWAP(a,b) {int ta;ab;bt;}传SWAP(a[i], a[j])时i被加两次用static inline函数或do{...}while(0)包裹int mid (low high) / 2;大下标时整型溢出变负数low (high - low) / 2if (a[j] pivot)里把写成全相等元素时指针推不动退化成 O(n²)按分区方案核对不变量递归前没判low high空数组或单元素时下标为负越界读入口处统一判用int接收sizeof结果超大数组时截断用size_t或显式转换并检查只测随机数据有序和重复数据下的崩溃被完全掩盖至少覆盖五种数据形态第二条和第三条我在不同项目里都见过真实事故。第一条相对少见但只要踩上一次症状是数据偶尔错位比直接崩溃难查十倍——因为出错的概率和编译器的优化等级相关-O0下可能完全正常-O2下就出错。还有一条不在表里但同样重要快速排序是不稳定排序。相等元素的相对顺序会被打乱。如果业务上依赖这个顺序比如按时间排序之后再按状态分组希望同状态内保持时间序就得换成归并排序或者加一个原始下标作为第二关键字。这个在需求评审阶段就该确认清楚等上线了才发现就麻烦了。6.3 一份可以直接拿去用的完整实现最后把前面所有优化合到一起给一份完整的、可以直接编译运行的代码。这份代码我做过去重和整理接口跟常规习惯保持一致。/* quicksort.c —— C11 编译gcc -O2 -stdc11 -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 -marchnative但拿-O2的数据做决策比较稳妥也最接近实际发布产物。另一件事是调试边界问题时先把INSERTION_THRESHOLD临时改成 1 再测这样小数组也走完整的快排路径能把藏在阈值切换处的 bug 暴露出来等验证完了再改回去。这个手法在处理任何加了优化之后才出错的问题时都很好使。
