写 C 语言的人迟早会撞上排序这道坎。初学者往往第一反应是撸一个冒泡排序、选择排序撸得满头大汗工作几年后回头看才发现标准库早就埋了一个几乎通用的排序工具——qsort。但 qsort 这个函数有个奇怪的脾气它本身好像“什么都不会排”真正决定结果的是你递给它的那个“比较函数”。很多朋友栽就栽在比较函数上——整数排序抄一段return *(int *)a - *(int *)b;勉强能用换成浮点立刻翻车换成字符串直接懵住换成结构体更是无从下手。这篇文章就把 qsort 从原理到实战彻底捋一遍。内容包括qsort 的四个参数到底怎么理解、比较函数的三态返回值为什么如此重要、整数/浮点/字符串/结构体四类数据分别怎么写比较函数以及平时最容易踩到的一批坑。刚学完指针和数组的 C 语言初学者可以看想把手头排序代码写得更稳的工程开发者同样可以参考。1. qsort基础想用对排序先看懂这4个参数1.1 函数原型到底在说什么qsort 是 C 标准库stdlib.h里提供的排序函数原型长这样#include stdlib.h void qsort(void *base, size_t num, size_t size, int (*compar)(const void *, const void *));第一次看到这个原型的人多半会被一堆void *和函数指针吓住。拆开看其实不复杂base待排序数组的首地址也就是数组名。因为 C 语言里数组传参会退化成指针所以不管你排的是int数组、double数组还是结构体数组到了 qsort 手里都统一变成void *也就是“一个不知道类型的内存地址”。num数组元素个数告诉 qsort 一共有多少块要排序的对象。size每个元素占的字节数。qsort 不知道元素类型移动元素时只能靠字节数“整块搬”所以你必须告诉它每块多大。compar指向比较函数的指针。每当你需要判断两个元素谁在前、谁在后qsort 就会调用这个函数根据返回值来做决定。这里最核心的思想是qsort 只是一个“分拣工人”它不关心你排的是苹果还是砖头只关心分拣规则。分拣规则由比较函数提供。之所以把类型信息全部抹掉换来的是通用性。一个排序算法可以同时服务于int、double、char *、结构体代价是类型安全没了所有转换都要靠比较函数内部自己做。这也解释了为什么标准库不提供qsort_int、qsort_double这类细分版本——一个通用函数加一个回调就能覆盖全部场景。// 一个典型的调用示例 int arr[10] {5, 2, 9, 1, 7, 6, 3, 8, 4, 0}; qsort(arr, 10, sizeof(int), cmp_int);有人会问sizeof(int)每次都要写为什么不直接用sizeof(arr)因为arr传进函数后会退化成指针sizeof(arr)得到的可能是指针大小而不是整个数组的大小。所以写成sizeof(int)是最稳妥、最明确的写法。1.2 一次完整的整数升序排序先看一个最小可运行的完整示例把整条链路跑通#include stdio.h #include stdlib.h int cmp_int(const void *a, const void *b) { int x *(const int *)a; int y *(const int *)b; return (x y) - (x y); } int main(void) { int arr[] {42, 7, 18, 99, 3, 56, 21}; size_t n sizeof(arr) / sizeof(arr[0]); qsort(arr, n, sizeof(int), cmp_int); for (size_t i 0; i n; i) printf(%d , arr[i]); printf(\n); return 0; }运行结果3 7 18 21 42 56 99这个例子里cmp_int的写法值得反复琢磨先把两个const void *强转成const int *再解引用得到具体的整数值。(x y) - (x y)是一个很优雅的整数比较写法当x y时前者为 1后者为 0返回 1当x y时前者为 0后者为 1返回 -1当两者相等时两个表达式都是 0返回 0。到这里你已经能完成最基本的整数升序排序了。但真正的坑从“为什么必须自己写比较函数”这个问题开始。2. 比较函数才是灵魂三态返回值决定了整个排序结果2.1 回调机制与三态语义很多人把 qsort 和比较函数的关系理解反了。qsort 不是“知道怎么排序顺便借用你的比较函数”而是“完全不知道排序规则每一步都要问比较函数”。整个排序过程可以类比成一个外包分拣员他面前有两个盒子每个盒子里的内容他不认识于是他把盒子里的东西拿给你看一眼实际上是给你地址你告诉他把哪个放前面他照做再换两个盒子再问你不断重复直到所有盒子排好。这个“问你是如何拿主意”的过程就是比较函数的工作方式。比较函数的签名固定如下int compar(const void *a, const void *b);返回值只有三种方向语义非常明确返回值含义小于 0a应排在b前面等于 0a、b视为相等先后顺序不保证大于 0a应排在b后面注意这里说的是“小于 0”“大于 0”不是“必须等于 -1 或 1”。只要符号对哪怕返回 -100 也没有问题。这属于 C 语言排序回调的约定俗成与某些语言里“必须返回 -1/0/1”的约定略有差别。为什么返回的是 int 而不是 bool因为 bool 只有真和假根本表达不了“谁前谁后”的三种关系。两个元素要么你在前、我在前要么等价而“等价”这个概念对于排序非常重要只有把相等元素视为没有先后排序算法才能把所有元素组织成一个稳定的线性序列。C 语言里另一个常见的误区是把比较函数和“大小比较”直接划等号。实际上比较函数定义的是一个“偏序关系”qsort 内部通过不断比较、交换来找到满足这个偏序关系的一个排列。你可以让比较函数按绝对值排、按个位数排、按字符串长度排只要它是一个合法的全序关系qsort 就能按你的规则排出结果。这可比冒泡排序写死在“大于小于”上灵活得多。2.2 升序降序的自由切换理解了三态返回值升降序就不再需要死记硬背了。升序时我们希望小的在前、大的在后所以当x y时返回负值降序时反过来当x y时返回负值。最简单的降序实现是交换比较函数里两个参数的“角色”int cmp_int_desc(const void *a, const void *b) { int x *(const int *)a; int y *(const int *)b; return (x y) - (x y); }也可以利用已有的升序函数取反int cmp_int_desc(const void *a, const void *b) { return -cmp_int(a, b); }这里要注意一个细节取反操作只针对比较函数的返回值。如果某个比较函数内部用了差值算法比如return x - y;那么当差值本身就是INT_MIN时取反会发生溢出结果还是INT_MIN符号没有翻转排序直接出错。所以相比之下我更推荐用交换参数位置来实现降序或者确保比较函数永远返回 -1/0/1 三值再放心取反。3. 常见的几类“比较函数”模板3.1 整数与浮点数比较函数整数比较函数已经有模板了但我强烈建议少用这种写法// 有隐患的写法 int cmp_bad(const void *a, const void *b) { return *(const int *)a - *(const int *)b; }隐患放在第 4 节细说先给出推荐的写法int cmp_int(const void *a, const void *b) { int x *(const int *)a; int y *(const int *)b; return (x y) - (x y); }浮点数的比较则要格外小心。最常见的错误是int cmp_double_bad(const void *a, const void *b) { double x *(const double *)a; double y *(const double *)b; return (int)(x - y); }这个写法有三个问题第一浮点数差值往往带有极小的小数例如0.1和0.2的差是-0.1强转成int变成0于是两个不相等的数被判定为“相等”排序结果随机而不可控。第二即使两个数的差值大于 1强转成int后也可能丢掉符号无法分辨比如差值1.9转成1这并不影响符号但遇到-0.1转成0就彻底错了。第三如果数组里出现NaN任何与NaN比较的结果都为假qsort 内部可能因此无法正确交换元素排序结果一团糟。稳妥的浮点比较函数长这样#include math.h int cmp_double(const void *a, const void *b) { double x *(const double *)a; double y *(const double *)b; if (x y) return -1; if (x y) return 1; return 0; }这个写法本质上就是“先比小于、再比大于”把等于单独拎出来返回 0。它依赖的是 C 语言里浮点比较的自洽性不会因为精度问题产生荒谬的返回值。如果你希望把NaN也纳入排序可以单独判断int cmp_double_nan(const void *a, const void *b) { double x *(const double *)a; double y *(const double *)b; if (isnan(x) isnan(y)) return 0; if (isnan(x)) return 1; // NaN 排在最后 if (isnan(y)) return -1; if (x y) return -1; if (x y) return 1; return 0; }浮点排序的实际业务里很少有人会专门处理NaN但如果你在写数值计算、金融相关的代码这个细节能省掉很多莫名其妙的 bug。3.2 字符串排序指针数组的必经之路字符串排序可能是 qsort 新手最先懵掉的场景。看一个常见需求对一个字符串指针数组排序。char *words[] {pear, apple, orange, banana};这里要非常清醒words是一个数组元素类型是char *指针不是char更不是char[20]这种定长字符串。qsort 排序时它比较的对象是“数组元素”也就是char *本身。比较函数拿到的是const void *里面存的是指向char *的地址。所以字符串比较函数的正确打开方式是这样#include string.h int cmp_str(const void *a, const void *b) { char * const *pa (char * const *)a; char * const *pb (char * const *)b; return strcmp(*pa, *pb); }一定要先解引用一层取出真正的char *再交给strcmp。很多人第一次会写成下面这样然后得到一堆奇怪的输出甚至段错误// 错误写法 int cmp_str_bad(const void *a, const void *b) { return strcmp((char *)a, (char *)b); }错误在于(char *)a被直接当成字符串首地址去读但它实际是一个指向char *的指针的地址读出来的是字符串指针本身而不是字符串内容。打个比方你想要的是“这盒子里装的纸条上写的名字”结果你直接去读盒子外壳上的编号两者自然对不上。为什么类型要写成char * const *而不是char **因为words数组的元素是char *qsort 回调的参数是const void *语义上这个void *指向的元素是不可修改的。还原时写成char * const *能保持 const 限定避免编译器警告也能提醒自己不要在比较函数里改数组内容。实际工程里很多人用char **也能编过但从严遵类型的角度char * const *更准确。如果要做“忽略大小写”的排序C 标准库没有直接提供跨平台的strcasecmp这是 POSIX 函数常见的做法是自己在比较函数里逐字符转换int cmp_str_nocase(const void *a, const void *b) { char * const *pa (char * const *)a; char * const *pb (char * const *)b; return strcasecmp(*pa, *pb); }如果是在纯 C89/C99 环境可以自己写一个忽略大小写的比较函数注意tolower的输入要转成unsigned char避免负值产生未定义行为。3.3 结构体多关键字排序实际项目里最常遇到的是结构体数组排序而且往往不止一个排序字段。所谓“多关键字排序”就是先按第一字段排第一字段相等时再按第二字段排依此类推。假设有一个学生结构体typedef struct { int id; char name[32]; int score; } Student;需求是按score从高到低排分数相同的人按id从小到大排。比较函数可以这样写int cmp_student(const void *a, const void *b) { const Student *sa (const Student *)a; const Student *sb (const Student *)b; if (sa-score ! sb-score) return (sa-score sb-score) ? 1 : -1; if (sa-id ! sb-id) return (sa-id sb-id) ? 1 : -1; return 0; }(sa-score sb-score) ? 1 : -1的含义值得展开一下当a的分数小于b的分数时我们希望高的在前也就是a要往后排返回正数所以这里返回1否则说明a的分数大于b返回负数a排前面。第二条if里的(sa-id sb-id) ? 1 : -1则是标准升序写法。这个嵌套 if 的模式可以无限扩展到第三、第四关键字只要按字段顺序逐层比较即可。你也可以把比较逻辑抽成更可读的函数比如int cmp_student(const void *a, const void *b) { const Student *sa (const Student *)a; const Student *sb (const Student *)b; int score_cmp (sa-score sb-score) ? 1 : (sa-score sb-score) ? -1 : 0; if (score_cmp ! 0) return score_cmp; return (sa-id sb-id) - (sa-id sb-id); }这种写法可维护性更好将来想改排序方向只需要调整局部变量那几行不会动整个嵌套结构。结构体排序还有一个隐藏很深的问题如果只按一个字段排序那么两个记录该字段相等时它们在数组里的先后顺序是不确定的。如果你希望“分数相同的老用户排前面”那就必须把“老用户”这个字段也纳入比较链。这正是多关键字排序的现实价值。4. 排序路上容易踩的坑与排查经验4.1 整数差值溢出一个看似正确的错误return *(int *)a - *(int *)b;大概是全网络流传最广的整数比较函数写法。它在大多数普通数据下都能正确工作但在两个极端整数相遇时会爆炸。假设a指向INT_MAXb指向INT_MIN那么数学上INT_MAX - INT_MIN的结果远远超出int的表示范围这在 C 语言标准里属于未定义行为。多数平台上实际发生的是整型回绕算出一个负数于是本应排在后面的INT_MAX被当成“小于”INT_MIN整个排序的顺序就崩了。我见过真实案例一个排序模块在普通测试数据上跑了一周都没事某天线上数据里混了一个INT_MIN结果列表底部的几个数据全部乱掉排查了很久才找到是这里溢出。所以整数比较函数请牢固树立“用关系表达式构造 -1/0/1”的习惯return (x y) - (x y);这个技巧对所有整数类型都适用包括unsigned int。注意如果你用unsigned int的减法无符号回绕是有定义的但语义也可能出乎预料所以统一用关系表达式最安全。4.2 浮点数比较的精度与NaN问题浮点比较除了 3.1 节提到的强转问题还有一个浅坑比较函数不能假设差值能精确表示两个浮点数的远近。例如// 仍然有问题的写法 return (x y) ? 1 : ((x y) ? -1 : 0);这个写法其实就是 3.1 节推荐写法的另一种展开没有问题。有问题的写法是试图“保留差值大小”的return (int)(x - y);另外浮点数判断相等最好不要带着业务上的“精度容忍”去做。比如你要求“两个浮点相差不超过 1e-6 视为相等”这在比较函数里做是危险的因为它破坏了排序必需的传递性A 和 B 相近、B 和 C 相近但 A 和 C 可能相差很大会导致 qsort 内部出现不一致的顺序判断。NaN的问题前面已经提过再补充一个现象如果数组里有NaN用简单的x y/x y比较函数NaN会被判定与所有数相等。在 qsort 里相等的元素不保证相对顺序所以NaN可能落在数组正中间而不是你以为的边界。处理办法就是显式判断isnan把它排到固定位置。4.3 稳定性、重复元素与结果验证qsort 是不稳定排序。所谓“不稳定”指的是相等元素在排序前后的相对次序可能改变。这一点和很多人熟悉的冒泡排序不同——冒泡排序只要实现得当是稳定的。什么时候会踩到稳定性问题比如你有一个“订单”结构体先按金额排好序然后又按用户 ID 排序。在第二次调用 qsort 时如果两个用户 ID 相等它们前后顺序取决于 qsort 的内部实现而不是你想保留的“按金额排序”结果。解决办法是引入第三个字段作为终极比较条件通常用原始索引typedef struct { int id; int score; int original_index; } Item; int cmp_item(const void *a, const void *b) { const Item *pa (const Item *)a; const Item *pb (const Item *)b; if (pa-id ! pb-id) return (pa-id pb-id) - (pa-id pb-id); return (pa-original_index pb-original_index) - (pa-original_index pb-original_index); }有了original_index兜底任何两个不同元素都不会被判定为“完全相等”排序结果就具有确定性了。由于 qsort 的不稳定性你可以用一个“自己先冒泡一遍再把同样比较函数塞给冒泡两边结果对照”的方式验证比较函数逻辑。如果比较函数本身有错误两份排序结果都可能是错的但它们的错误方向通常一致所以这个方法的真正用途是检查比较函数是否自洽把数组随机打乱后反复排序看结果是否始终一致如果每次排序结构变化很大说明比较函数存在非传递性问题。4.4 常见问题速查表现象原因解决办法return x - y在极端整数下排序错乱有符号整型溢出未定义行为用(x y) - (x y)浮点数排序结果随机差值强转int丢精度、丢符号用、逐层比较字符串排序段错误类型转换错误把指针当字符串先转char * const *再解引用结构体排序“看起来没排”只比较了指针本身没有比较字段类型转换到结构体指针后逐字段比较相同元素的相对顺序每次不同qsort 不稳定加入原始索引作为兜底字段数组含 NaN 时排序异常NaN 与任何数比较都为假显式判断isnan并设定位置比较函数里改动了原数据违反 const 语义引发不可预期行为一律使用const限定进行只读操作升降序搞反三态返回值的语义没吃透记住“负数表示 a 在前”自己推一遍5. 关于qsort的几点实践经验与个人体会5.1 qsort底层发生了什么用 qsort 时很多人会把它当成黑盒。它确实是一个黑盒但了解一点内部机制有助于你判断它的边界。标准库只规定 qsort 的行为没有规定算法。常用的 glibc 实现是快速排序的变体递归划分区间对小的子区间可能改用插入排序同时选择合适的 pivot 来避免最坏情况。所以 qsort 的平均时间复杂度是 O(n log n)但在某些极端的退化输入上也可能接近 O(n²)——这和你自己手写的“教科书快排”遇到有序数组会退化是一个道理。知道这一点有什么用如果你排序的数据量极大百万、千万级qsort 依然是默认首选因为它的平均表现很好。但如果你的系统对实时性要求极高最坏情况不可接受那么就值得考虑自建堆排序或其他更可控的方案。任何库函数都有适用边界理解边界比记住 API 更重要。5.2 我建议的排序决策思路很多朋友在写代码时会纠结是调 qsort 还是自己写一个排序我的建议很简单——如果你想做的是业务开发核心诉求是“把数据排好”直接用 qsort不要重复造轮子。qsort 的态度是“你给我规则我就好好干”只要比较函数写得对它比你自己手写的多数排序都高效、可靠。如果你正在学习数据结构或者刷算法题那么请务必亲手实现几遍快排、归并、堆排序理解分治、递归、稳定性、时间复杂度这些概念。这时候再用 qsort你反而能看懂它每一层递归的背后发生了什么。如果你在写底层库、嵌入式系统栈空间紧张或者对排序稳定性有明确需求那就认真评估 qsort 的递归深度和不稳定性是否可接受。必要时可以用自己的归并排序替代。这个决策思路说白了就是该用工具时用工具该练手艺时练手艺不要混为一谈。5.3 一个实用的小技巧最后分享一个让我少踩很多坑的小习惯把比较函数拆成两个层面。第一层是“数据层面的比较规则”第二层是“适配 qsort 签名的包装器”。例如// 数据层面的比较规则方便单独测试 int compare_student_by_score_asc(const Student *sa, const Student *sb) { if (sa-score ! sb-score) return (sa-score sb-score) - (sa-score sb-score); return (sa-id sb-id) - (sa-id sb-id); } // 适配 qsort 的包装器 int cmp_student_qsort(const void *a, const void *b) { return compare_student_by_score_asc( (const Student *)a, (const Student *)b); }这样做的价值在于compare_student_by_score_asc可以在单元测试里直接调用也可以在其他排序场景比如自己手写的归并排序里复用。一旦测试发现排序规则不符合预期故障点是清晰的——出在规则函数里不会牵连到 qsort 本身。我在项目里用这个模式重写过很多次排序每次都能快速定位问题比把全部逻辑塞在一个const void *函数里省心得多。回到文章开头那个问题排序这件事在 C 语言里从来不是“qsort 会不会排”而是“你的比较函数想让它怎么排”。把比较函数吃透qsort 立刻从一段需要死记硬背的代码变成一把真正顺手的瑞士军刀。