有人觉得 qsort 难其实难点根本不在 qsort 本身而在那个你不得不亲手写、又总觉得可以随便写写就行的比较函数。在 C 语言里用 qsort 给数组排序流程说穿了就一行调用、四个参数首地址、元素个数、元素大小、比较函数。但真正决定排序方向和排序质量的只有最后这个比较函数。它可以让你按整数升序排、按浮点数排、按字符串字典序排、按结构体里的某个字段排也可以让你在“升序”和“降序”之间来回切换靠的都是一套相同的底层机制。这篇文章我准备用一线开发者的视角把 qsort 的底层逻辑、比较函数的设计原理、各种数据类型的写法、工程中的避坑点全部捋一遍。无论你是刚学 C 语言基本功的新手还是想快速搞定“对结构体数组按字段排序”这种实际需求的进阶读者这篇文章都能给你一套可以直接抄走的方法。1. 先把 qsort 的脾气摸清楚函数签名与底层逻辑1.1 一个签名搞清楚 qsort 四要素qsort 定义在stdlib.h里原型非常紧凑void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));参数就四个base数组首地址。因为是void *所以指向什么类型都行nmemb数组元素个数size每个元素占用的字节数compar函数指针指向你的比较函数。很多初学者第一次看到这个函数时会愣住为什么排序函数还需要传入“每个元素占多少字节”这不是多此一举吗原因是这样的。在 C 语言里void *是“无类型指针”它只告诉函数“内存地址在哪里”却没有告诉函数“这一片内存里一个量到底有多大”。而排序必然要做交换操作交换的前提就是知道元素边界。size参数解决的正是这个信息缺口。你可以想象有人让你把一排盒子按重量排序但每个盒子的尺寸不同如果你不知道每个盒子的宽度别说搬动它们了连哪个位置属于哪个盒子都分不清。这也是 qsort 能够做到“一个函数排所有类型”的原因。void *提供通用地址size提供元素跨度比较函数提供元素之间的大小关系三者一配合qsort 就成了一个与具体数据类型无关的通用排序工具。1.2 qsort 内部到底怎么排很多教材把 qsort 简单称为“快速排序”这个说法基本正确但实现细节不同平台上并不完全一样。标准委员会并没有规定 qsort 必须使用某一种具体算法只对它做了复杂度和行为上的约束。实际的主流实现比如 glibc 和 macOS libc内部大多是快速排序的变体或者干脆是快速排序加插入排序的混合策略。快速排序平均时间复杂度是 (O(n \log n))空间复杂度因为递归的存在通常为 (O(\log n))这也是它能在绝大多数场景下碾压冒泡和选择排序的原因。快速排序的核心思想是分治每次选一个元素作为基准把比基准小的放左边、比基准大的放右边然后分别对左右两边递归排序。这个过程拆到单元素时自然结束。但这里有一个公开的秘密快速排序是不稳定排序。所谓“不稳定”指的是如果数组里有两个值相等的元素排序后它们的相对顺序不保证保持不变。比如一组数据{2a, 1, 2b}两个 2 在逻辑上相等排序后2a未必还在2b前面。C 标准从未承诺过 qsort 是稳定的。如果你的业务要求“成绩相同的人按学号从小到大排”必须自己在比较函数里把学号作为次关键字带进去。这是一个非常关键的工程认知我会在后面的实战环节专门演示。1.3 手写排序和调用 qsort 的取舍很多培训班喜欢让学生手写冒泡排序和选择排序这当然没错它们逻辑简单、适合训练基础。但真实项目里如果只是需要一个常规排序反复造轮子并不划算。手写排序有一个隐藏成本你写的循环嵌套和交换逻辑未必有你自以为的那么可靠。拿冒泡排序举例把写成把i n-1写成i n都会导致排序结果出问题而这些错误在代码 review 时往往还很隐蔽。相比之下qsort 把“排”这个动作完全封装好了你只需要盯住比较函数这一亩三分地。而且 qsort 里排序算法经过长年优化同等数据量下往往比新手手写的冒泡排序快上一到两个数量级。数据量一上万差距就非常明显。所以我的态度很明确默认用 qsort除非你明确知道它不满足需求比如需要稳定排序、需要针对特殊数据结构做优化否则不要自己造轮子。2. 比较函数的设计原理从“裁判”到“秩序”2.1 三态返回值才是比较的真谛既然 qsort 自己管排序那它如何知道数组里任意两个元素谁大谁小答案就在比较函数里。比较函数的签名是int cmp(const void *a, const void *b);这里a和b并不指向具体的值而是指向待比较的两个元素的地址。函数返回值有三个语义区间返回负数a排在b前面也就是a小于b返回零a和b相等返回正数a排在b后面也就是a大于b。你可以把它理解成裁判员的判罚手势。qsort 内部每一次“谁先谁后”的决策都要来问一遍比较函数。这个函数写得对排序方向就对这个函数写得鸡飞狗跳整个数组就会排得莫名其妙。为什么返回值必须是“负、零、正”三态而不是简单的 0 和 1因为排序算法在知道“谁小于谁”之外还要知道“谁等于谁”。相等的元素在快速排序的划分过程中会被特殊对待如果所有情况都返回 1算法会误以为从不相等导致分区失衡最坏情况直接退化到 (O(n^2))。2.2 标准升序比较函数的四步写法我总结了一套写升序比较函数的固定套路新手直接照做就行。第一步把void *强转成你真实类型的指针。比如排序的是int数组就把const void *a转成const int *a。第二步解引用取出值。第三步用大于小于号比较返回(ia ib) - (ia ib)。第四步没有第四步了写完了。完整代码长这样int cmp_int_asc(const void *a, const void *b) { int ia *(const int *)a; int ib *(const int *)b; return (ia ib) - (ia ib); }为什么推荐(ia ib) - (ia ib)这种写法因为它同时覆盖了三种情况大于时第一个条件为真返回 1、第二个为假返回 0整体为 1小于时整体为 -1相等时整体为 0。它不会有溢出的问题语义清清楚楚而且编译器通常能把它优化得很干净。2.3 升降序切换的本质是“交换立场”很多第一次接触 qsort 的人会好奇我写好了升序比较函数想排降序怎么办最简单的做法是在比较函数里把a和b的角色对调。升序版本是return (ia ib) - (ia ib);降序版本只要把判断反过来return (ib ia) - (ib ia);你仔细观察就会发现这不只是把不等式符号换了它是把“第一个参数小于第二个参数”的语义传给 qsort 完全相反的结论。qsort 本身不关心你是升序还是降序它只相信比较函数告诉它的偏序关系。所以“升降序切换”的本质并不是在排序算法里做文章而是改变裁判的判罚标准。这种设计非常巧妙。排序算法是稳定的、可复用的变化的只有比较策略。你甚至可以构造出非常诡异的排序规则比如“绝对值大的排前面”“偶数优先偶数之间升序”“闪烁的霓虹灯色值排最后”这些都能通过一个自定义比较函数实现。这就是 qsort 架构的最大优势。3. 不同数据类型的比较函数写法3.1 int 类型正确写法与溢出风险整数排序最常用也是最容易出事的。我先说一个反例。网上到处都是这种写法int cmp_int_bad(const void *a, const void *b) { return *(const int *)a - *(const int *)b; }它看起来没问题前一个值减后一个值负数就是小于、正数就是大于、零就是相等。逻辑确实符合三态语义。但问题是int是有符号整数两个int相减的结果很容易溢出。举个具体例子a是INT_MAX2147483647b是INT_MIN-2147483648那么a - b 2147483647 - (-2147483648)数学上等于 4294967295这个数字超出了 32 位 int 的表示范围。在典型的补码机器上这个结果被截断成 -1于是 qsort 错误地判断“大的那个元素小于小的那个元素”。一系列这样的错误判断叠加起来排序结果能对就见鬼了。所以我的建议很明确整数排序老老实实用大于小于比较不要用减法取巧。现代编译器在-O2下一样能把它优化得很好你损失的只有几行代码的可读性换来的却是绝对的安全性。3.2 double 类型浮点数的额外隐患浮点数比较和整数稍有不同。double之间不能直接用减法比较大小原因和整数类似精度损失和溢出风险。更稳妥的方式仍然是用大于小于号int cmp_double_asc(const void *a, const void *b) { double da *(const double *)a; double db *(const double *)b; return (da db) - (da db); }这里有一个工程上必须注意的点NaNNot a Number。在 IEEE 754 浮点数体系里NaN 与任何值比较都返回假所以da db和da db都为 0比较函数会认为 NaN 和任何数都“相等”。如果数据里混入了 NaN排序结果会非常诡异NaN 可能出现在任意位置而且数组的顺序在这个位置前后可能完全不满足“左边全小于右边”的预期。严格来说这不是 qsort 的 bug而是浮点数比较规则带来的边界效应。如果你的业务场景允许出现 NaN我建议在排序之前先清洗数据把 NaN 单独剔除或映射成一个特殊值再交给 qsort。千万不要指望比较函数里那几行代码能“自动修复”NaN因为浮点数语义里它本来就不是一个有序的量。3.3 字符串排序一个最容易翻车的地方字符串排序是面试和作业里的大热门但也是最容易翻车的地方。因为它有两种常见形态一是指针数组二是二维字符数组。它们的比较函数写法是两套不能混用。第一种形态const char *names[] {zhangsan, lisi, wangwu};数组里的每个元素是“指向字符串的指针”。int cmp_str_ptr(const void *a, const void *b) { const char *sa *(const char * const *)a; const char *sb *(const char * const *)b; return strcmp(sa, sb); }关键点在于a和b指向的对象并不是字符串本身而是字符串的指针。所以必须先做一次解引用*(const char * const *)a拿到真正的const char *再交给strcmp。第二种形态char names[][16] {zhangsan, lisi, wangwu};数组里每个元素是一块固定大小的字符缓冲区。int cmp_str_arr(const void *a, const void *b) { return strcmp((const char *)a, (const char *)b); }这里的a和b直接就是指向每行缓冲区首地址的指针强转成const char *后就能直接交给strcmp。这两种写法之间差了整整一层“指针的指针”很多人没搞清楚就照抄网上的字符串排序代码结果怎么排都是乱的。我自己排查过不少类似问题最终结论基本都是同一个把char *数组和char[][]数组搞混了。3.4 结构体比较函数多字段排序的组合拳真实业务里需要排序的对象几乎不可能只是裸的整数更多时候是一堆“有名字的字段”。比如学生结构体typedef struct { int id; char name[32]; double score; int age; } Student;要按score降序排严格来说int cmp_student_by_score_desc(const void *a, const void *b) { const Student *sa (const Student *)a; const Student *sb (const Student *)b; if (sa-score sb-score) return -1; if (sa-score sb-score) return 1; return 0; }如果还要做到“成绩相同的按学号升序”就在score相等时继续比较idint cmp_student_rank(const void *a, const void *b) { const Student *sa (const Student *)a; const Student *sb (const Student *)b; if (sa-score sb-score) return -1; if (sa-score sb-score) return 1; if (sa-id sb-id) return 1; if (sa-id sb-id) return -1; return 0; }这就是前面说的“多关键字比较”。qsort 本身不保证稳定所以你必须把次关键字明确写进比较函数。这样做出来的排序结果是可预期的而且和“稳定排序”的效果几乎一致。我习惯把这类多字段比较函数写成“先比较主字段不等就返回相等再比较次字段不等就返回直到所有字段都比较完”。这套写法在写任何语言、任何比较器时都通用C 语言里也是这个套路。4. 实战案例结构体数组排序与性能对比4.1 一个完整的可运行示例下面这个例子演示了如何用 qsort 对结构体数组按多种规则排序。代码可以直接抄走运行为了可读性我把辅助函数也放进来。#include stdio.h #include stdlib.h #include string.h #include time.h typedef struct { int id; char name[32]; double score; } Student; int cmp_rank(const void *a, const void *b) { const Student *sa (const Student *)a; const Student *sb (const Student *)b; if (sa-score sb-score) return -1; if (sa-score sb-score) return 1; if (sa-id sb-id) return 1; if (sa-id sb-id) return -1; return 0; } void print_students(Student *arr, int n) { for (int i 0; i n; i) { printf(id%3d name%-10s score%.2f\n, arr[i].id, arr[i].name, arr[i].score); } printf(---\n); } int main(void) { Student students[] { {101, zhangsan, 88.5}, {105, lisi, 92.0}, {102, wangwu, 88.5}, {103, zhaoliu, 76.0}, {104, sunqi, 92.0}, }; int n (int)(sizeof(students) / sizeof(students[0])); qsort(students, n, sizeof(students[0]), cmp_rank); print_students(students, n); return 0; }运行结果是id104 namesunqi score92.00 id105 namelisi score92.00 id101 namezhangsan score88.50 id102 namewangwu score88.50 id103 namezhaoliu score76.00注意两个细节score都是 92.0 时id104排在id105前面因为我的比较函数在成绩相等时按id升序score都是 88.5 时也一样101排在102前面。这正好实现了“稳定化”的效果。4.2 qsort 性能实测和手写冒泡差距有多大只看功能不看性能容易吃亏。我做了一个简单实测生成 10 万个随机整数分别用 qsort 和手写冒泡排序在相同编译选项下比较耗时。qsort 的测试代码#define N 100000 int cmp_int_asc(const void *a, const void *b) { int ia *(const int *)a; int ib *(const int *)b; return (ia ib) - (ia ib); } int main(void) { int *arr malloc(sizeof(int) * N); srand(20240601); for (int i 0; i N; i) arr[i] rand(); clock_t start clock(); qsort(arr, N, sizeof(int), cmp_int_asc); clock_t end clock(); printf(qsort time: %.3f s\n, (double)(end - start) / CLOCKS_PER_SEC); free(arr); return 0; }冒泡测试就没必要贴完整代码了就是最朴素的二重循环。在我本机的实测里qsort 排 10 万个随机整数的耗时在 0.01 秒量级而冒泡排序要好几十秒。这个差距还会随数据量扩大急剧拉开。为什么会差这么多关键在于 qsort 的平均复杂度是 (O(n \log n))而冒泡是 (O(n^2))。当 n 从 1000 涨到 100000(n \log n) 只从约 10000 涨到约 170 万而 (n^2) 从 100 万暴涨到 100 亿。这种数学级别的差距不是编译器优化能弥补的。4.3 需要稳定排序怎么办前面已经提过qsort 不保证稳定。如果一个业务场景确实需要稳定排序我不建议你立刻去手写一个归并排序因为有一个更轻量的技巧给每个元素附加一个原始序号在比较函数里把原始序号作为次关键字。做法是额外定义一个包装结构体typedef struct { int value; int order; } IndexedItem;初始化时记录好每个元素在原始数组里的位置IndexedItem items[N]; for (int i 0; i N; i) { items[i].value arr[i]; items[i].order i; }比较函数在value相等时比较orderint cmp_stable_asc(const void *a, const void *b) { const IndexedItem *ia (const IndexedItem *)a; const IndexedItem *ib (const IndexedItem *)b; if (ia-value ! ib-value) { return (ia-value ib-value) - (ia-value ib-value); } return (ia-order ib-order) - (ia-order ib-order); }这样即使 qsort 底层的快速排序做了各种交换元素之间“值相等就按原始顺序”的关系都成立最终的输出就等同于一个稳定的排序。这个技巧在实践里非常实用因为它不改变排序算法“稳定”这个语义完全由你的比较函数来兜底。4.4 排序大结构体时的额外优化如果结构体特别大比如里面塞了几百字节的字段qsort 每次交换元素都要整体搬动这块内存代价很高。工程上一个经典做法是不排序结构体数组本身而是排序下标数组。int *idx malloc(sizeof(int) * n); for (int i 0; i n; i) idx[i] i; qsort(idx, n, sizeof(int), cmp_by_score_desc); // 排序后students[idx[0]] 是分数最高的比较函数的写法变了int cmp_by_score_desc(const void *a, const void *b) { int ia *(const int *)a; int ib *(const int *)b; if (students[ia].score students[ib].score) return -1; if (students[ia].score students[ib].score) return 1; return 0; }这里唯一要注意的是students必须在比较函数所在文件内可见或者作为外部全局变量。排序完之后你按idx数组的顺序遍历一遍原数组就得到了排好的结果而原数组本身完全没有移动过。对于大对象集合这个方案能显著减少交换成本。5. 常见问题与避坑清单5.1 别用 return a - b一个整数溢出引发的血案这个坑我一开始就提过但还是值得单独拿出来说一次。网上很多教程写整数排序时用return *(int*)a - *(int*)b正常数据量小也能跑通于是很多人就带着这个习惯进入生产环境。直到某一天数据里出现了接近INT_MAX和INT_MIN的极端值排序结果瞬间乱套。有符号整数溢出在 C 语言里是未定义行为。你可以把a - b理解成“在数学上先算出结果再截断到 int 范围”但编译器可能在你毫无防备的情况下把它优化成完全不同的行为。不要和未定义行为赌。正确做法永远是先取出两个值再用大于小于号手工判断最后返回(a b) - (a b)。这样写出来的比较函数在所有合法输入下都成立。5.2 字符串比较的隐藏坑你排的是地址还是内容字符串排序翻车最多的场景是拿字符串指针数组排序时写了下面这种比较函数int cmp_str_wrong(const void *a, const void *b) { const char *sa *(const char **)a; const char *sb *(const char **)b; return (sa sb) - (sa sb); }注意sa sb比较的是两个指针的数值大小也就是字符串在内存里的地址高低。地址大小和字符串内容的字典序没有一毛钱关系。一个字符串可能在内存地址 0x1000另一个在 0x2000地址大的按地址排序永远排在后面但它的内容可能从字母 A 到 Z 排第一。遇到这类问题我的排查工序很固定先确认数组到底是char *数组还是char[][]二维数组再确认比较函数里有没有正确地取出字符串内容最后确认是不是调用了strcmp而不是用了或比较指针。这三步走一遍基本能定位九成以上的字符串排序问题。5.3 老司机的三道排查工序如果你遇到“排序结果怪怪的”但一时看不出原因我建议按下面三个顺序排查。第一道检查四要素。base传的是不是数组首地址nmemb是不是元素个数而不是字节数size是不是sizeof(arr[0])比较函数类型是不是严格匹配int (*)(const void *, const void *)任何一个参数错了排序结果都不会正常。第二道检查返回语义。在比较函数里故意打印或者单测一下确认负数代表“第一个小于第二个”正数代表“第一个大于第二个”。顺着这个语义验证你的代码尤其注意有没有写成“返回-1 反而代表大于”这种方向性反转。第三道检查类型强转。比较函数里(const int *)a这种强转必须和base指向的真实类型一致。base是int数组强转成int *没问题base是结构体数组强转成int *或者char *就会取错数据。下面这张排查表可以直接保存参考错误现象可能原因解决方案编译报错函数指针类型不匹配比较函数参数不是const void *严格按int cmp(const void *, const void *)写签名排序后顺序反了返回语义与期望相反调整比较函数里a、b的位置关系大整数排序顺序错乱return a - b溢出改用(a b) - (a b)字符串排序不对比较的是指针地址而不是内容使用strcmp并区分指针数组和二维数组结构体排序时字段错位强转类型与数组元素类型不一致核对base的元素类型和比较函数的强转类型排序结果不稳定、相等元素乱序没有设置次关键字增加原始序号或附加字段作为次关键字5.4 全局变量控制排序方向的利与弊有时候你会遇到一个需求同一个结构体数组这次按成绩排下次按年龄排再下次按姓名排。最简单粗暴的写法是写三个不同的比较函数。但如果规则是动态的比如用户可以选择按哪个字段排序你可能会想到用一个全局变量来控制比较函数的走向static int sort_field 0; // 0score, 1age, 2name int cmp_dynamic(const void *a, const void *b) { const Student *sa (const Student *)a; const Student *sb (const Student *)b; switch (sort_field) { case 0: return (sa-score sb-score) - (sa-score sb-score); case 1: return (sa-age sb-age) - (sa-age sb-age); case 2: return strcmp(sa-name, sb-name); } return 0; }这个方案能跑但有一个明显的代价sort_field是静态全局变量在多线程环境下会有数据竞争。标准 qsort 接口比较函数没有上下文参数这是接口设计的历史局限。如果项目是 C 语言且在多线程环境下我更推荐的做法是写几个专门的比较函数每个字段一个主逻辑里根据用户选择直接调用对应的那个。代码稍微多几行但完全避开了全局状态引发的隐患。如果是 C则可以借助std::sort配合 lambda 动态捕获状态比硬套 C 风格接口舒服得多。最后再分享两个实操经验在 C 语言里写排序我个人的习惯是先写一个比较函数模板然后留到最后再来检查它。因为排序算法本身一般是稳定的、被反复验证过的任何“乱序”几乎都能从比较函数身上找到原因。与其在 qsort 调用那里反复纠结四要素不如把精力全部花在compar的实现上。还有一个经验拿到任何排序需求第一件事是明确“排序关键字有几个”“主关键字是哪一列”“次关键字要不要管”。把这两个问题回答清楚了再动手写比较函数基本一次通过。反之上来就写return a - b的同学十个里有九个都要在某个夜深人静的晚上面对一屏乱序数据怀疑人生。最后留一个小技巧如果排的是定长字符串数组也就是char name[][N]这种形态strcmp((const char *)a, (const char *)b)不要少写const char *的强转。不要觉得这是小事编译器环境下少了这层强转一旦警告等级高了直接就是编译错误。这类细节恰恰是手写冒泡排序时根本不会遇到、但用 qsort 时必须面对的工程现实。