写排序这件事很多人是在面试前夜才临时抱佛脚。我最近一次认真手写快排是因为一个跑在低配设备上的日志统计小工具隔三差五就崩一次最后定位到 sorter 里那句int pivot a[hi]——输入数据恰好是按时间戳递增的固定枢轴退化成最坏情况递归深度直接顶到了几万层。这就是为什么标题里我特意加了随机两个字排序算法的正确性只是及格线随机化才是让它在真实数据上不翻车的那道保险。这篇我把 C 语言版随机快排从思路、分割推演、完整代码、性能优化到踩坑排查全流程写一遍代码可以直接抄参数为什么这么选也会讲清楚。适合两类人看一是有 C 语法基础、想搞明白快排到底快在哪、又会慢在哪的同学二是手上有真实业务数据、被固定枢轴坑过一次想找个能直接落地的实现的开发者。全篇不玩虚的代码都可编译可复现。1. 为什么要在 C 里手写一个随机快排1.1 固定枢轴的坑往往栽在看起来很正常的数据上教科书上的快排第一版通常长这样取区间最后一个元素当枢轴然后递归左右两半。这个版本在随机的测试数据上跑得飞快于是很容易让人产生快排就这样了的错觉。问题在于真实数据几乎从来不是随机的。按时间戳追加的日志、按自增主键导出的记录、按 ID 顺序写入的缓存条目全都是已经有序或近似有序的序列。面对这种输入固定取末元素做枢轴会得到最糟糕的划分每次只能把区间砍掉一个元素递归树退化成一条链时间复杂度从O(n log n)掉到O(n²)。十万条数据大概要多跑几十亿次比较同时还伴随几万层的函数调用栈在默认 8MB 栈空间的桌面环境里勉强能撑住在栈更小的嵌入式环境里就是直接段错误。更隐蔽的一种情况是重复元素。假设数据里 90% 的值是同一个状态码用最朴素的 Lomuto 分割严格小于才换位每一轮枢轴落到数组末尾左半边装进去几乎所有元素右半边只装枢轴自己。表面上代码没问题跑起来却是标准的O(n²)。这种 bug 特别难查因为它在小数据集上完全正常只有数据量上去、重复率变高之后才暴露。所以手写快排的第一件事不是写循环而是先想清楚我的数据长什么样最坏情况会以什么姿势出现。想清楚这一点后面的设计取舍才有依据。1.2 随机化到底解决了什么问题它的代价又是什么随机化的核心动作只有一个在划分之前从当前区间[lo, hi]里随机挑一个下标把它和枢轴位置交换。就这么一步把输入数据决定划分质量变成了随机数决定划分质量。这一步的意义在于打断了输入与划分之间的人为关联——哪怕你喂给它一个完全有序的数组随机选中的枢轴落在哪个位置也是均匀分布的期望上每次能比较均衡地把区间切成两半。从期望角度算一笔账随机枢轴下任意两个元素被比较的概率约为2/(j-i1)把所有元素对加起来期望比较次数约为2n ln n ≈ 1.39 n log₂n。也就是说平均情况下比理想的对半分多出约 39% 的比较量。这个数字看着有点亏但换来的是最坏情况从必然发生变成概率极低。真正最坏的情况需要随机数连续多次都挑到极值位置对于 n 等于一百万这个概率低到在宇宙寿命内也基本遇不上。代价有三个得提前说清楚。第一是随机数本身的开销每次划分都要取一个随机数如果直接用rand() % n在标准库里可能带锁、带函数调用开销递归层数多的时候累计起来不便宜所以我在下面给了个自实现的 xorshift几条位运算就搞定。第二是结果不可复现出问题时不能靠固定种子重跑调试时我会临时把随机源换成固定序列。第三是随机化只降低最坏情况的概率并不消除它真要彻底兜底还得配合三路划分和深度限制这两块在第 4 节展开。1.3 和标准库 qsort 比手写特化版本值不值有人会问stdlib.h里现成的qsort不香吗为什么要自己写。答案取决于场景。qsort是泛型实现每个元素比较都要走一次函数指针调用一次间接跳转加上无法内联的比较逻辑对int这种小元素来说开销占比极高。我实测过一百万随机int-O2下特化的手写快排大约是qsort的 2 到 3 倍速度差距主要就来自函数指针和元素拷贝方式qsort按字节拷贝int还好换成 8 字节以内的小结构体也还行换成几十字节的结构体就更明显。另外qsort内部实现是各家编译器自己定的标准没规定它必须是快排也没规定它怎么选枢轴你没法针对自己的数据分布做调整。如果数据类型固定、性能敏感、或者需要可控的最坏情况行为手写一个特化版本是合理的。反过来如果调用频率很低、数据量也就几百个直接用qsort完全没问题别为了优化一个占整体耗时不到 1% 的环节浪费两天。2. 快排的核心分割partition到底在干什么2.1 用一组具体数字手工走一遍 Lomuto 分割不管代码写多少行快排的骨架永远是选一个枢轴把小的挪左边、大的挪右边然后对两边递归。真正容易写错的是中间那步搬迁。我用 Lomuto 方案先走一遍数组是[3, 8, 2, 5, 1, 4, 7, 6]取末尾的6当枢轴维护一个指针i指向小于枢轴区域的右边界后一格另一个指针j从左往右扫描。j0a[0]3 6交换a[i]和a[j]自己和自己换i变成 1j1a[1]8不小于 6跳过j2a[2]2 6交换a[1]和a[2]数组变[3,2,8,5,1,4,7,6]i变成 2j3a[3]5 6交换a[2]和a[3]变[3,2,5,8,1,4,7,6]i变成 3j4a[4]1 6交换a[3]和a[4]变[3,2,5,1,8,4,7,6]i变成 4j5a[5]4 6交换a[4]和a[5]变[3,2,5,1,4,8,7,6]i变成 5j6a[6]7不小于 6跳过。扫描结束后把枢轴从hi换到i5的位置得到[3,2,5,1,4,6,7,8]返回下标 5。可以看到左边五个都小于 6右边两个都大于等于 6划分成立。这个手推过程建议自己在纸上走一遍因为几乎所有的下标越界问题都来自对i语义的误解——i不是当前元素而是小于区的下一个空位。2.2 Hoare 分割快在哪边界又为什么容易写崩Hoare 版本是双指针从两端往中间夹遇到左边不小于枢轴、右边不大于枢轴的就交换直到两指针交错。它比 Lomuto 少做很多次交换Lomuto 每个小于枢轴的元素都要换一次包括自己跟自己换平均性能更好而且天然能把等于枢轴的元素分散到两边面对全相等数组时不会退化。但它有个著名的坑返回值的语义不一样。Hoare 返回的j是左半边的最后一个位置左半区间是[lo, j]右半区间是[j1, hi]跟 Lomuto 返回枢轴最终位置、左半是[lo, p-1]完全不同。很多人在网上抄了一段 Hoare 的代码又配上 Lomuto 的递归写法结果就是死循环或者漏排。我见过最常见的表现是数组大部分排好了但中间某几个元素始终在原地因为区间被重复划分了。还有一个细节是哨兵。Hoare 里那两句do { i; } while (a[i] pivot);不需要额外的边界判断靠的是枢轴本身一定会在数组里拦住两个指针——前提是枢轴值确实取自当前区间内。如果枢轴取成了区间外的值或者用了写成指针就可能冲出去。这也是我建议初学先用 Lomuto 的原因慢一点但逻辑直白不容易写出隐蔽的越界。等彻底理解了再换 Hoare。对比项Lomuto 分割Hoare 分割指针数量单指针从左扫双指针两端夹交换次数较多含自交换较少重复元素表现差全相等退化为 O(n²)较好从中间分开返回值语义枢轴最终下标 p左区间[lo,p-1]分界点 j左区间[lo,j]、右区间[j1,hi]越界风险低j hi写死即可较高依赖枢轴作哨兵适合人群入门、教学、需要清晰调试追求性能、已理解边界语义2.3 一个容易被忽略的点比较符号决定重复元素的归属a[j] pivot还是a[j] pivot这一符号的差别在数据无重复时完全看不出来但在重复率高时影响巨大。用严格小于等于枢轴的元素全被推到最后那次交换的右侧导致左右极不平衡用小于等于等于枢轴的元素全被塞进左侧同样不平衡只是方向反了。所以单靠改符号解决不了重复元素问题正道是三路划分把区间切成小于、等于、大于三段等于段直接跳过不再递归。第 4 节会给完整实现。我的经验是只要业务数据里可能出现大量相同值状态字段、分桶编号、评分等级就别犹豫直接上三路划分。多写二十行代码换来的是从O(n²)到O(n log n)的差别这笔账怎么算都值。3. 完整的随机快排实现与逐段拆解3.1 随机源为什么我不用 rand()标准库的rand()有三个问题。第一返回值范围由RAND_MAX决定很多实现只有 32767对大数组来说能选到的枢轴位置太少随机性打折扣。第二它不是线程安全的多线程同时排序会互相干扰内部状态。第三某些实现的低位随机性很差rand() % n恰恰用的就是低位。排序场景对随机质量要求不高但也没必要踩这些坑自己写个 xorshift 就十几行速度快、可复现、无全局锁。#include stdint.h static uint64_t rng_state 0x9E3779B97F4A7C15ULL; static inline uint64_t xorshift64(void) { uint64_t x rng_state; x ^ x 13; x ^ x 7; x ^ x 17; rng_state x; return x; } /* 返回 [lo, hi] 闭区间内的随机下标 */ static inline int rand_index(int lo, int hi) { uint64_t span (uint64_t)(hi - lo) 1ULL; return lo (int)(xorshift64() % span); }0x9E3779B97F4A7C15这个种子来自黄金分割比例异或移位之后分布比较散比随手写个 12345 强。xorshift 的周期是2^64 - 1排序过程中调用几百万次完全够用。注意xorshift64() % span存在取模偏差低位区间会略微偏多。选枢轴时这点偏差完全无所谓但如果哪天你要用它做洗牌或者抽奖得换成乘法取高位(uint64_t)span * x 32那种写法否则分布不均会被放大。如果想要每次运行结果可复现把rng_state改成从命令行参数或者固定常量初始化即可想要每次不同就在程序入口用当前时间戳初始化一次。注意只初始化一次别在排序函数内部反复重置那样每次划分拿到的随机序列都一样等于白随机。3.2 交换函数与 Lomuto 分割的完整实现static inline void swap_int(int *a, int *b) { int t *a; *a *b; *b t; } /* 前置条件枢轴已经换到 a[hi] */ static int partition_lomuto(int *a, int lo, int hi) { int pivot a[hi]; int i lo; for (int j lo; j hi; j) { if (a[j] pivot) { swap_int(a[i], a[j]); i; } } swap_int(a[i], a[hi]); return i; }swap_int加inline是有意义的-O2下编译器能把它完全展开成三条寄存器指令省掉函数调用。有人喜欢用异或交换a ^ b; b ^ a; a ^ b;炫技我不推荐第一当a和b指向同一地址时它会把值清零而 Lomuto 里自己跟自己交换是常态第二现代编译器对临时变量版本优化得更好异或版本反而多两条依赖链。这个坑我在早期代码里踩过排查了半天才想明白为什么数组里莫名多出一堆零。for (int j lo; j hi; j)这里的千万别写成。写成会把枢轴自己参与比较当枢轴是最小值时i会多走一步交换后枢轴位置错乱结果就是数组看起来排好了但某几个元素顺序不对。这种 bug 用眼睛看很难发现必须靠后面第 6 节的对拍测试兜住。3.3 随机化 小区间优化 尾递归消除的主函数#define INSERTION_THRESHOLD 16 static void insertion_sort(int *a, int n) { for (int i 1; i n; i) { int key a[i]; int j i - 1; while (j 0 a[j] key) { a[j 1] a[j]; j--; } a[j 1] key; } } void quick_sort(int *a, int lo, int hi) { while (lo hi) { int len hi - lo 1; if (len INSERTION_THRESHOLD) { insertion_sort(a lo, len); return; } /* 随机枢轴换到 hi 位置交给 Lomuto */ int r rand_index(lo, hi); swap_int(a[r], a[hi]); int p partition_lomuto(a, lo, hi); /* 哪边短就先递归哪边长的那边用循环处理 */ if (p - lo hi - p) { quick_sort(a, lo, p - 1); lo p 1; } else { quick_sort(a, p 1, hi); hi p - 1; } } }这段代码里有三个设计决策值得解释。为什么小区间切插入排序。递归到 16 个元素以下时函数调用、栈帧、随机数生成这些固定开销已经超过了比较本身的价值。插入排序在近乎有序的小数组上表现极好因为快排划分之后小区间本来就接近有序而且没有递归开销、缓存友好。阈值取多少常见的取值是 8 到 32 之间我用 16 是因为在几种不同数据分布下测下来比较稳。这个值跟机器、编译器优化等级都有关想较真的话自己跑一组基准测试别盲目抄。为什么先递归短的一边。这个技巧叫尾递归消除或者递归深度优化。两边都递归的话递归深度等于递归树的深度最坏O(n)先处理短的、长的用while循环接着处理递归栈深度就被限制在O(log n)因为每次真正压栈的区间长度至少减半。对于一百万条已排序数据虽然随机化后基本不会退化但万一随机数抽风这个改动能把栈溢出风险降到几乎为零。为什么随机交换放在最前面。顺序不能乱必须先换到hi再调用 Lomuto因为 Lomuto 是拿a[hi]当枢轴的。如果先划分再随机等于没随机。主函数入口建议包一层对外只暴露一个参数更友好的接口void sort_ints(int *a, int n) { if (a NULL || n 2) return; quick_sort(a, 0, n - 1); }n 2的提前返回看着多余实际上能省掉空数组和单元素数组走一遍完整流程的麻烦也顺手挡住了hi -1这种诡异入参。3.4 编译与第一次跑通gcc -O2 -Wall -Wextra -stdc11 quicksort.c -o quicksort-Wall -Wextra一定要开。手写快排最常见的错误是有符号无符号混用、下标比较类型不匹配这些警告能提前捞出来一大半。别用-O0跑性能测试那个数据毫无参考价值优化前后差三五倍很正常。跑通之后先别急着测性能第一件事是拿小数组手工验算。{3,8,2,5,1,4,7,6}排完应该是{1,2,3,4,5,6,7,8}{1}、{}、{2,1}、{1,1,1}这几个边界各跑一遍。{1,1,1}用 Lomuto 版本会跑得很慢但结果正确这一步只是验证功能性能问题后面用三路划分解决。4. 让它跑得更快四个实战优化4.1 三路划分重复元素多的数据必须上三路划分的思路是把区间分成三段小于枢轴、等于枢轴、大于枢轴中间那段直接跳过不再递归。这一招对大量重复值的数据效果立竿见影——如果整个数组都相等一趟划分就结束复杂度直接从O(n²)降到O(n)。static void quick_sort_3way(int *a, int lo, int hi) { while (lo hi) { int len hi - lo 1; if (len INSERTION_THRESHOLD) { insertion_sort(a lo, len); return; } int r rand_index(lo, hi); swap_int(a[lo], a[r]); int pivot a[lo]; int lt lo; /* [lo, lt-1] pivot */ int i lo 1; /* 当前扫描位置 */ int gt hi; /* [gt1, hi] pivot */ while (i gt) { if (a[i] pivot) { swap_int(a[lt], a[i]); lt; i; } else if (a[i] pivot) { swap_int(a[i], a[gt]); gt--; /* 注意i 不自增换过来的元素还没检查 */ } else { i; } } /* 此时 [lo,lt-1] p[lt,gt] p[gt1,hi] p */ if (lt - lo hi - gt) { quick_sort_3way(a, lo, lt - 1); lo gt 1; } else { quick_sort_3way(a, gt 1, hi); hi lt - 1; } } }这段代码里最容易写错的是a[i] pivot那个分支交换之后i不能自增因为从gt位置换过来的元素还没被检查过得留在原地再判一次。写成i会导致漏检结果是某些元素位置不对而且因为数据量小时看不出来很容易漏测。另一个坑是循环条件写成i gt那会漏掉最后一个元素gt位置的值永远不参与比较。lt和gt的初始值也要注意lt lo是因为枢轴本身就在lo它天然属于等于区所以等于区初始就是[lo, lo]gt hi表示大于区初始为空。这套下标语义建议在纸上画格子标出来比在脑子里想靠谱得多。4.2 三数取中叠加随机兼顾质量和不可预测性纯随机枢轴的平均划分质量是够的但偶尔抽到极值仍然会得到很差的划分。一个常见的加强做法是三数取中取区间首、中、尾三个位置的元素排一下序用中位数当枢轴。这样在近似有序的数据上枢轴天然就是中间值划分质量直接拉满。问题在于三数取中一旦固定下来它就又变成确定性的了——攻击者或者特定的数据分布可以构造出让三数取中每次都取到极值的输入。所以我的做法是把两者叠起来先随机挑一个下标把这个元素换到末尾再在首、中、尾三个位置里取中位数。这样既拿到了中位数带来的划分质量又保留了随机性带来的不可预测。int mid lo (hi - lo) / 2; if (a[lo] a[mid]) swap_int(a[lo], a[mid]); if (a[lo] a[hi]) swap_int(a[lo], a[hi]); if (a[mid] a[hi]) swap_int(a[mid], a[hi]); swap_int(a[mid], a[hi]); /* 中位数挪到 hi交给 Lomuto */lo (hi - lo) / 2这种写法而不是(lo hi) / 2是为了防止两个大下标相加溢出int。虽然在 64 位平台上int溢出后是未定义行为往往碰巧算对但这是标准的隐患养成习惯就好。三数取中在完全随机的数据上其实略有开销多两次比较收益主要体现在近似有序和存在少量异常值的数据上。如果你的数据已经确认是均匀随机分布这一步可以省如果不确定加上更保险。4.3 深度限制兜底把最坏情况按死随机化之后最坏情况概率极低但不是零。如果这段代码要跑在不能崩溃的环境里比如守护进程、嵌入式设备加一层深度限制比较稳妥记录当前递归深度超过2 * log2(n)就改用堆排序保证最坏也是O(n log n)。这个思路就是所谓的内省排序主流标准库的排序实现基本都是这个套路。static void introsort(int *a, int lo, int hi, int depth_limit) { while (lo hi) { int len hi - lo 1; if (len INSERTION_THRESHOLD) { insertion_sort(a lo, len); return; } if (depth_limit 0) { heap_sort_range(a lo, len); /* 需要自己实现一个堆排 */ return; } depth_limit--; int r rand_index(lo, hi); swap_int(a[r], a[hi]); int p partition_lomuto(a, lo, hi); if (p - lo hi - p) { introsort(a, lo, p - 1, depth_limit); lo p 1; } else { introsort(a, p 1, hi, depth_limit); hi p - 1; } } }深度限制的初值一般取2 * floor(log2(n))。计算方式有两种一种是用循环移位数一种直接用__builtin_clz这类内建函数都行。堆排的代码这里就不铺开了网上有大量成熟实现重点是把排序区间的堆化写对——建堆要从最后一个非叶节点往前调整别从根往后调。要不要加这一层看你的容错要求。做算法练习、跑离线批处理随机化加三路划分已经足够写长期驻留的服务加上更安心。4.4 优化效果对比与一个反直觉的结论我在自己的机器上跑了一组对比一百万个int-O2取多轮中位数数据仅供感受量级不代表你的机器方案随机数据已排序数据全相等数据固定末元素枢轴 Lomuto快极慢退化极慢退化随机枢轴 Lomuto快快慢重复元素退化随机枢轴 三路划分快快极快随机 三数取中 三路 插入排序最快最快极快表格里有一点值得注意三路划分在纯随机、无重复的数据上比普通两路划分略慢一点点因为每次元素要判三次而不是两次交换也稍多。所以它不是无脑全上的银弹。判断标准很简单跑一遍你的真实数据统计一下不同值的个数。如果唯一值数量远小于元素总数比如十万条数据只有几百个不同状态三路上如果唯一值几乎等于元素总数两路就够。反直觉的另一个结论是插入排序阈值调大不一定变慢。理论上阈值越大插入排序的O(k²)开销越明显但实测在 16 到 32 之间几乎是平的甚至 32 有时更快因为递归层数减少带来的栈和分支预测收益抵消了插入排序的额外比较。这种地方不要凭理论拍板一定要测。5. 常见问题与排查技巧实录5.1 死循环、结果错乱、越界三大高频故障死循环几乎百分之百出在递归区间上。三路划分里如果写成quick_sort_3way(a, lo, lt)而不是lt - 1等于区间里还包含枢轴下次划分枢轴还在区间不缩小无限递归。Hoare 版本里如果返回j却按 Lomuto 的方式递归[lo, j-1]和[j1, hi]同样会漏元素或者死循环。排查方法很土但有效在递归入口打印lo和hi看区间是不是在单调收缩如果某次调用前后区间完全一样问题就锁定了。结果错乱排完序但个别元素位置不对通常来自边界条件的差一错误。两个高发点Lomuto 的循环写成j hi三路划分的a[i] pivot分支里多写了i。这类 bug 用随机小数组跑一百次基本能抓到如果只测了{5,3,1}这种三元素数组很可能一次都碰不上。越界访问最隐蔽因为有时候它不崩溃只是读到垃圾值。Hoare 分割里如果枢轴取得不对比如从区间外取两个指针可能一路冲出数组边界。用-fsanitizeaddress编译跑一遍基本上能揪出所有越界和 use-after-free这个工具强烈建议在手写数据结构、算法的时候常开。5.2 栈溢出与性能异常两个方向完全不同的排查路径栈溢出的表现是程序在数据量增大到某个阈值时直接崩溃报段错误。原因有两种一是没做尾递归消除遇到退化输入递归深度到O(n)二是虽然做了消除但没做小区间优化递归树叶子太多。判断方法很简单把数据量从一万逐步加到十万、百万看崩溃点是不是跟数据量线性相关。修复就是第 3.3 节和 4.3 节那两招。顺带提一句Linux 上默认栈是 8MBWindows 上通常是 1MB同一份代码在两个平台上的崩溃阈值可能差好几倍别拿一个平台的表现推断另一个。性能异常是另一条线。如果排序跑得比预期慢很多按这个顺序查第一确认编译开了-O2或更高-O0下跑出来的数据没有任何意义第二确认随机数初始化只做了一次如果每次划分都重置种子随机序列退化成了固定序列第三统计数据的唯一值数量重复率高就上三路划分第四检查是不是在循环里反复调用排序函数导致缓存失效或者每次排序都重新malloc临时数组。还有一种很坑的情况是性能测试本身写错了。比如用clock()测时间但没排除生成测试数据的开销或者在多线程环境里测单线程性能被其他线程干扰。我的习惯是生成数据、排序、校验、计时四段严格分开计时只包住排序那一行并且跑多轮取中位数别只看一次结果。5.3 常见问题速查表现象最可能的原因排查手段处理方式程序卡死无输出递归区间未收缩打印递归入口的 lo/hi检查lt/gt/p的边界写法数据量大时崩溃递归过深导致栈溢出逐步加大数据量找崩溃点尾递归消除 小区间插入排序排完仍有元素错位循环边界差一随机小数组跑一百轮检查与、i位置全相等数据极慢两路划分退化统计唯一值个数改用三路划分已排序数据极慢固定枢轴退化用手工递增数组测试随机枢轴 / 三数取中多次运行结果不同随机源未固定检查种子初始化位置调试期固定种子发布期放开偶发读到垃圾值数组越界-fsanitizeaddress编译修正指针边界与哨兵比 qsort 还慢未开优化 / 函数指针开销判断失误对比-O2下的多轮中位数检查 inline、元素拷贝方式5.4 几条只有踩过才知道的经验第一条调试期一定要能关掉随机。我会在代码里留一个编译开关把rand_index换成固定的lo (hi - lo) / 2这样出问题时能稳定复现。等逻辑确认无误再打开随机重新跑一遍全部测试用例。第二条别在排序函数里调用printf调试。数据量一大输出本身就把性能特征全毁了而且日志刷屏会盖住真正有用的信息。要看中间状态用条件编译只在特定数据量下打开或者干脆用调试器打断点看。第三条小数组的正确性测试比大数组更能抓 bug。所有边界情况——空、单元素、双元素、全相等、已排序、逆序、只有两个不同值——都能在十个元素以内构造出来。我习惯写一个用例数组每次改完代码全跑一遍几秒钟的事能挡掉绝大多数低级错误。6. 测试与验证怎么证明你的快排是对的6.1 对拍用标准库当裁判自己写的排序靠肉眼验算是不可靠的正确做法是拿一个已知正确的实现当参照随机生成大量小数组两边各排一份逐元素比对。标准库的qsort就是现成的裁判虽然它慢但正确性经过充分验证。#include stdio.h #include stdlib.h #include string.h static int cmp_int(const void *x, const void *y) { int a *(const int *)x, b *(const int *)y; return (a b) - (a b); } static int check_once(int n, int max_val) { int *src malloc(sizeof(int) * (size_t)n); int *ref malloc(sizeof(int) * (size_t)n); if (!src || !ref) { free(src); free(ref); return -1; } for (int i 0; i n; i) { src[i] (int)(xorshift64() % (uint64_t)max_val); } memcpy(ref, src, sizeof(int) * (size_t)n); sort_ints(src, n); qsort(ref, (size_t)n, sizeof(int), cmp_int); int ok (memcmp(src, ref, sizeof(int) * (size_t)n) 0); if (!ok) { printf(mismatch at n%d, max_val%d\n, n, max_val); for (int i 0; i n; i) { if (src[i] ! ref[i]) { printf( idx %d: got %d, want %d\n, i, src[i], ref[i]); break; } } } free(src); free(ref); return ok; }cmp_int里那个(a b) - (a b)写法是为了避免直接相减溢出虽然对一般数据范围没问题但养成习惯没坏处。对拍的关键是max_val要能调小把它设成 3 就能构造出大量重复值专门测三路划分设成INT_MAX就接近全不同值测普通路径。n 从 0 到 500 各跑几十轮覆盖各种规模。6.2 边界用例清单与性能压测方法对拍之外我会固定准备一组手工用例每次改动后全跑一遍用例目的空数组n0验证提前返回不访问任何元素单元素{7}验证不进入划分流程双元素{2,1}与{1,2}验证一次交换与不交换两条路径全相等{5,5,5,5,5}验证三路划分不退化、不死循环已排序1..1000验证随机化生效不退化完全逆序1000..1同上另一方向的退化只有两个值{1,2,1,2,...}验证等于区处理含负数与极值验证比较逻辑没有无符号陷阱性能压测和对拍要分开做别混在一个程序里互相干扰。压测时数据规模取一千万左右重复五轮每轮重新生成数据记录耗时取中位数。测之前记得把 CPU 频率调节、后台任务这些干扰因素考虑进去笔记本插不插电测出来的数字都能差一截。我还喜欢做一个退化压力测试构造一个专门针对三数取中的对抗性输入看看加入随机化之后耗时是否还在正常范围。这个测试在纯随机化版本上意义不大因为不知道会挑到哪个下标但能验证三数取中叠加随机之后确实没有被固定模式打穿。6.3 我个人长期保留的一组回归习惯改排序代码这事最怕的是改了一处另一处悄悄坏了。我现在的习惯是任何一次修改不管是换分割方案、调阈值还是加优化都先把对拍程序跑满两千轮再跑一遍手工边界用例表最后才看性能。顺序不能反——先看性能容易被数字迷惑为了快 5% 引入一个隐蔽的边界 bug得不偿失。另外我会在代码里留一段#ifdef DEBUG_SORT的自检每次划分结束后断言左半区所有元素都小于等于枢轴、右半区都大于等于枢轴。这个断言在-O2下会被编译掉调试时打开能第一时间定位到哪一次划分出了问题比等到最后比对整个数组高效得多。这套组合拳用下来我手写的排序实现已经很久没有在线上出过问题了。