今天聊的是C语言里一个出场率极高的排序函数——qsort函数。如果你刚接触指针和回调函数或者准备面试、刷题又或者工作中需要快速排序但不想手写快排那这个函数值得花一天搞明白。它虽然是标准库函数却一次性能带你摸清三个重要知识点void* 指针怎么用、函数指针怎么传、回调机制到底是什么。这篇文章我会把这几个点串起来讲透还会附上可以直接抄作业的代码和踩坑记录。先纠正一个常见误解很多人以为qsort是“C语言自带的库函数”只能用来排整数数组。其实qsort是C标准库stdlib.h里提供的快速排序实现名字里的q就是quick sort的意思。它厉害的地方在于通过函数指针这个机制一套代码就能排整型、浮点型、字符串、结构体甚至指针数组只要你给它提供“怎么比较两个元素”的规则就行。换句话说qsort负责“怎么排”你负责“怎么比”分工很清晰。qsort是20世纪60年代快速排序算法提出之后随之被吸收进标准库的经典实现。你现在用的编译器GCC、Clang、MSVC里它内部的具体策略可能各有微调比如数据量小时切到插入排序但对外接口和语义几十年没变过。这也是我喜欢它的原因接口极其稳定学会了到哪里都能写。这篇文章适合三类人看刚开始学指针、正被“回调函数”绕晕的C语言初学者准备校招或社招笔试面试想快速补上“排序函数指针”考点的人还有工作中经常需要处理数据排序但不想每次手写partition的开发者。我会尽量讲得通俗一点每个点都给出代码和实测结果。1. 为什么排序首选qsort而不是自己写快排1.1 自己写快排的真实成本我见过很多初学者包括当年的我第一次遇到排序需求时都摩拳擦掌打算亲手写一个快排。写出来运行没问题感觉也挺好。但多写几次你就会发现自己造轮子有几个隐藏成本第一边界条件容易错。快排的partition写法五花八门有Hoare版、Lomuto版还有各种“填坑法”。随便挑一种写空数组、单元素数组、全相等数组、已经有序的数组这些边界情况稍不注意就崩给你看。我之前见过一个同学写的快排随机数据好好的一遇到“所有元素都相等”的用例就栈溢出。第二只能排一种类型。如果你写了一个void sort_int(int *arr, int n)下次想排double数组要么复制粘贴改类型要么用宏去套模板维护起来很痛苦。qsort用void*指针把“元素类型”这件事完全抽象掉了一套接口通吃所有类型这种设计是教科书级别的。第三性能未必有保证。你手写的快排如果每次都选第一个元素做基准遇到基本有序的数据会退化到O(n²)。标准库的qsort则做了很多优化比如三数取中、小区间切换插入排序等实际表现通常比初学者自己写的稳定得多。所以我的建议是先把qsort用熟再自己写快排练手。工具归工具原理归原理两件事不冲突。1.2 qsort和其他排序方案怎么选很多C程序员会用STL的std::sort也有的人用mergesort、heapsort那你到底该用哪个看场景方案适用场景优点注意点qsortC代码、跨平台C项目、面试手写简洁排序标准库自带、类型通用、接口稳定需要写comparator回调函数std::sortC工程类型安全、内联优化后通常更快、可以配lambda仅C可用容器迭代器要求随机访问自己手写排序学习算法原理、特殊排序需求稳定排序、按绝对值等完全可控、可定制容易写错、容易选错算法如果你在C语言环境里qsort基本是唯一“零成本”的选择如果在C里我反而建议优先考虑std::sort因为类型安全上更稳。但话又说回来qsort的compartor写法能帮你理解函数指针的本质这些能力是通用的学完用在哪都值。2. 四个参数拆解每个参数都在解决什么问题2.1 函数原型与参数含义qsort的函数原型长这样#include stdlib.h void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));一共四个参数base待排序数组的首地址。因为可以是任意类型数组所以用void*来接收。nmemb数组中元素的个数。size数组中每个元素占用的字节数比如int数组就是sizeof(int)。compar函数指针指向一个“比较两个元素大小”的函数。qsort内部排序时每次需要判断谁大谁小都会调用这个回调函数。看到int (*compar)(const void *, const void *)这种声明很多人就开始犯怵。其实把它拆开看compar是一个指针指向一个函数这个函数接收两个const void*参数返回int。返回值的语义如下返回值 0第一个参数排在第二个参数前面返回值 0两个参数相等顺序不确定返回值 0第一个参数排在第二个参数后面一句话总结你告诉qsort“a和b谁大谁小”qsort帮你安排位置。2.2 为什么要用void*指针这个问题我当年也困惑过为什么数组首地址不直接声明成int*因为qsort想同时支持int、double、char、结构体如果写死成int*那其他类型全用不了。void在C语言里是“万能指针”任何类型的指针都能隐式转换成void反过来则必须显式强转。但void*也有代价它丢失了“当前指针指向的到底是什么类型、一次偏移多少字节”的信息。所以qsort才需要你额外传入size告诉它每个元素占多大内存。内部做移动和交换时qsort只能按字节来操作(char *)base i * size就是第i个元素的首地址。这也是为什么你在网上会看到很多qsort源码里频繁出现char*强转的原因——char占1字节用它做字节级偏移最方便。2.3 回调函数是怎么被调用的qsort并不会直接认识你的int、double或结构体它只认识void*。所以它排序时每次都比较两个字节块但“字节块谁大谁小”它说了不算得问你。于是就有了回调机制qsort内部排序到需要比较两个元素时会调用你传入的compar函数。这个过程就好比你让一个助理整理一摞文件助理不认识文件内容但他手里有一张“规则卡”每次拿两份文件按卡上的方法判断谁该放前面。这张规则卡就是compar函数。qsort是“怎么整理”的执行者你是“怎么判断”的规则制定者两者通过函数指针解耦。这就是回调函数的核心思想。3. 不同类型数组的排序实操3.1 整型数组排序最基础的上手案例先来一个最简单的例子把一组整型数据从小到大排序。#include stdio.h #include stdlib.h int cmp_int(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[] {34, 7, 23, 32, 5, 62, 31, 3}; 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 5 7 23 31 32 34 62。这段代码里最核心的是cmp_int里那两行强转int ia *(const int *)a;因为compar拿到的是const void*不能直接解引用。你要先告诉编译器“这个void*实际指向的是int”于是强转成const int*再解引用才能取到真实值。这个过程我建议你在脑子里多过几遍qsort传进来的是“指向元素的指针”的地址不是元素本身。所以在compar里你是先转成具体类型的指针再解引用。3.2 字符串数组排序别在指针上栽跟头字符串数组排序稍微绕一点因为这里有个经典大坑。先看代码#include stdio.h #include stdlib.h #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); } int main(void) { const char *names[] {banana, apple, cherry, date, blueberry}; size_t n sizeof(names) / sizeof(names[0]); qsort(names, n, sizeof(const char *), cmp_str); for (size_t i 0; i n; i) printf(%s\n, names[i]); return 0; }看到declarationchar * const *pa很多人就懵了。我们拆一下names是const char *的数组也就是说数组里每个元素是一个指针。qsort调用compar时传入的是“指向数组元素的指针”。数组元素是const char *所以指向它的指针就是const char **。在compar参数里以const void*呈现于是我们需要把它转成char * const *或者const char **取决于你数组元素的声明。我在实践中发现最容易出错的地方是写成了int cmp_wrong(const void *a, const void *b) { const char *sa *(const char **)a; const char *sb *(const char **)b; return strcmp(sa, sb); }其实这样写也能跑但中间的转型有点容易搞混。我自己学习时更喜欢用char * const *这种写法它更严谨地表达了“指向指针的指针”也和数组声明对应。另一个容易翻车的地方是给qsort传size参数时写成了sizeof(names)。这样会把整个数组字节数当成了单个元素大小排序直接乱套。正确的是sizeof(const char *)也就是一个指针的大小在64位平台上通常是8字节。3.3 结构体数组排序按关键字处理数据实际工作中排结构体数组是最常见的需求。比如学生成绩表按分数从高到低排。代码长这样#include stdio.h #include stdlib.h #include string.h typedef struct { char name[32]; int score; } Student; int cmp_by_score_desc(const void *a, const void *b) { const Student *sa (const Student *)a; const Student *sb (const Student *)b; return (sb-score sa-score) - (sb-score sa-score); } int main(void) { Student students[] { {Alice, 87}, {Bob, 92}, {Cindy, 78}, {David, 92}, }; size_t n sizeof(students) / sizeof(students[0]); qsort(students, n, sizeof(Student), cmp_by_score_desc); for (size_t i 0; i n; i) printf(%s: %d\n, students[i].name, students[i].score); return 0; }输出结果Bob: 92 David: 92 Alice: 87 Cindy: 78这里能看到结构体排序和基础类型排序的差别不大比较函数里先强转成const Student*再用-访问成员。当分数一样时Bob和David谁在前C标准没有保证我实测在GCC上通常维持原始相对顺序但这不是标准承诺不能依赖。如果你想做“先按分数降序分数相同再按姓名字典序升序”就要在compar里做二级判断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 (sb-score sa-score) - (sb-score sa-score); return strcmp(sa-name, sb-name); }这种“多级排序”写法在面试里很常见面试官通常考察的不只是你会不会排而是你会不会处理“比较规则相同但比较维度不止一个”的场景。3.4 double类型排序浮点数比较的隐藏风险double排序看着简单但很多人直接用return (int)(*(double*)a - *(double*)b)然后数据一复杂就出问题。原因在于浮点数的减法可能会得到很小的非整数值强制转成int后直接变成0排序结果就随机了。安全写法是用比较操作符int cmp_double(const void *a, const void *b) { double da *(const double *)a; double db *(const double *)b; return (da db) - (da db); }这样即使两个值差得极小也会返回正确正负号不会因为截断变成0。这里再补充一句(da db) - (da db)这个写法是C语言里比较保险的“返回-1/0/1”套路它避免了return a - b那种可能溢出或截断的问题。我后面会专门讲这个点。4. compar回调函数返回值的坑与正确姿势4.1 为什么必须返回“负、零、正”很多人以为compar里返回1和返回5没区别反正都是“大于”。在逻辑上确实没区别qsort只关心符号正负不关心绝对值大小。但如果你的compar返回一个你“以为正确”的数而那个数的符号其实是反的那就全乱了。比如最容易出现的错误写法int cmp_bad(const void *a, const void *b) { return *(int *)a - *(int *)b; }这种写法在int很大时可能溢出。比如a是INT_MAXb是-1a - b会溢出变成未定义行为极端情况下结果可能是负的排序方向直接反转。我在实测里遇到过好几次代码看起来没问题结果排序不稳定、乱序。所以稳妥起见用比较大小来产生-1/0/1。那有人问为什么标准不建议返回这么大的数呢因为在一些实现里qsort内部会把返回值直接转发给别的比较逻辑虽然规范只要求符号但保持“只返回-1/0/1”的习惯能避免在特殊实现、特殊编译器优化下的意外行为。4.2 降序排序一个符号搞定如果想让int从大到小排两个办法。办法一翻转让谁在前int cmp_int_desc(const void *a, const void *b) { int ia *(const int *)a; int ib *(const int *)b; return (ib ia) - (ib ia); }办法二在升序结果上把返回值取反return -cmp_int(a, b);这两个都行。我习惯用办法一因为“返回值的正负代表前后关系”这个逻辑更直观。但你只要记住一点(ia ib)表示a放前面等价于升序交换成(ib ia)就是降序。字符串降序也一样return strcmp(other, self);。4.3 为什么字符串比较不能直接返回数值差常见错误是写return *(char *)a - *(char *)b;如果你只排单字符那没问题。但如果排的是字符串这种做法根本不对你只比较了两个字符串第一个字符的数值差后面的字符根本没比较。比如apple和banana比第一个字符a(97)和b(98)能得到正确顺序但banana和blueberry首字符都是b直接相减得0相当于告诉qsort这两个字符串相等顺序就不可控了。正确做法是用strcmpreturn strcmp(*(char * const *)a, *(char * const *)b);strcmp会按字典序逐字符比较返回负、零、正正好符合qsort的期望。注意这里得先把const void*转成char* const*再解引用因为数组元素是指针。4.4 比较函数是“稳定排序”的天敌如果你问qsort是否稳定答案是不稳定。快速排序天然不是稳定排序。但如果你在compar里额外加入“原始下标”这个比较维度就可以模拟稳定排序。做法是把数组元素定义一个结构体结构体里存原始下标和值然后比较时先比值值相同再比下标。这算是面试里比较进阶的玩法原理上就一句话让比较函数能区分出原本相同大小的元素就能做到“看上去稳定”。5. 常见问题与排查技巧实录5.1 段错误八成是size写错了我见过最多的问题就是qsort一跑就Segmentation fault。几乎每次排查到最后都是size参数传错了。比如qsort(arr, n, sizeof(arr), cmp_int);这里sizeof(arr)是整个数组的字节数而不是单个元素大小。qsort内部用size做字节偏移一旦size是真实值的n倍访问地址直接飞出去了必然段错误。检查顺序我一般这样先确认nmemb是元素个数不是字节数。再确认size是单个元素大小不是数组总大小。最后确认compar里强转的类型和数组实际类型一致。这里还有个隐蔽情况如果你的数组是int arr[10]但compar里强转成了const double*那解引用取出来的值会完全错乱。因为qsort拿到的只是字节块它并不校验类型。所以compar的类型转换是“你保证它是对的”编译器不帮你检查。5.2 comparator返回值不对排序靠运气排序结果似是而非有时候对有时候错我第一个怀疑对象就是比较函数。用return a - b这种写法溢出风险我之前说过了。另一个常见问题是在compar里修改了数据。比如有人图省事在比较函数里交换了数组里的两个元素然后返回0。这绝对是错误用法qsort已经自己在交换元素了你再插一手数组可能被搞乱逻辑就乱套了。比较函数应该是纯函数只读不修改任何数据。我排查comparator问题时的经验是写一个小的printf看每次进了比较函数a和b到底是谁。虽然qsort里的比较顺序不一定总一致但你能确认数据有没有被意外修改。测试多用几组数据随机值、有序值、反序值、全相等值、单元素值、大数值触发溢出。5.3 结构体数组的sizeof陷阱结构体在内存里存在对齐padding所以sizeof(Student)可能比你手工算的所有成员字节数加起来还要大。这时候千万不要自己算边长直接写sizeof(Student)编译器会给你正确值。有的同学喜欢写sizeof(student[0])这也对而且当数组类型变化时不用改代码我推荐这种写法。有一个相关坑如果结构体里有指针成员排序时compar里比较的到底是“指针本身的值”还是“指针指向的内容”比如结构体里存了const char *name你想要按名字排序那compar里就应该先解引用结构体拿到name再用strcmp比较字符串内容。如果写成了直接比较两个name指针的数值大小那就变成按地址排序了结果看起来莫名其妙。这种问题编译期不会报错运行期结果也是合法的但就是不对。5.4 实测问题速查表症状可能原因解决办法段错误size传成数组总大小改为sizeof(arr[0])段错误nmemb传成数组字节数用sizeof(arr)/sizeof(arr[0])结果乱序compar返回值溢出或截断用(ab)-(ab)替代a-b字符串排序错误直接比较首字符或指针用strcmpdouble排序错乱(int)强转截断用比较操作符生成-1/0/1排序是反的compar正负语义理解反交换a和b的位置比较函数里改了数组违反纯函数约束只读参数不做任何赋值数组类型和强转类型不一致解引用取值错乱检查compar里的强转是否匹配实际类型5.5 比较函数里要不要处理NaN和NULL如果数据是浮点数NaN和普通数字比较时所有比较操作符都返回false这会导致“NaN既小于任何数又大于任何数”的混乱状态qsort的排序结果就可能不可预期。如果你在处理可能含NaN的double数据最好在compar开头专门处理一下比如把NaN排到末尾int cmp_double_strict(const void *a, const void *b) { double da *(const double *)a; double db *(const double *)b; int na isnan(da), nb isnan(db); if (na || nb) return na - nb; return (da db) - (da db); }如果是字符串指针数组中出现了NULL指针调用strcmp直接段错误。这时候也要在compar里判断一下if (sa NULL) return 1; if (sb NULL) return -1;这种边缘数据在实际业务中很常见尤其数据来源不可控的时候。我的建议是生产环境的比较函数初始化数据时就把脏数据清洗掉不要指望排序函数处理异常。排序只是手段数据质量还是要在前面把关。6. 从qsort延伸出去sort、lambda和函数指针6.1 C语言里的函数指针和C里的sort对比如果你把qsort的comparator搞明白了函数指针这个知识点基本就通了。它在C语言里无处不在回调、状态机、插件机制、信号处理全都在用类似模式。学qsort算是学函数指针性价比非常高的入口。到了C里你再看到std::sort函数的用法其实换了一层它不要求void*而是直接用模板推导出元素类型并用迭代器表示范围。C11之后还可以用lambda表达式直接在调用处写比较规则。初看很爽但如果你不清楚它底层还是“传入一个可调用对象在内部反复调用比较”那突然遇到lambda捕获、模板推导报错还是会一头雾水。所以qsort这个最原始的“函数指针排序”案例反而能帮你理解上层语法究竟在做什么。6.2 自己也写一个“通用排序”练手读完这篇文章我强烈建议你亲手封装一个“通用排序函数”来练手。做法是模仿qsort的接口但内部用冒泡排序或选择排序实现同样接受void* base、size_t nmemb、size_t size和比较函数指针。这个练习非常值因为它逼你处理void*强转、字节偏移、逐字节交换等细节。交换两个元素时因为人不知道具体类型只能按字节交换void swap_bytes(void *a, void *b, size_t size) { char *ca (char *)a; char *cb (char *)b; for (size_t i 0; i size; i) { char tmp ca[i]; ca[i] cb[i]; cb[i] tmp; } }这个函数虽然简单但写出来能帮你理解“void* size”这个组合到底是怎么运作的。如果你能自己实现一遍再回去看qsort的源码会觉得豁然开朗。7. 一次完整的实战用qsort处理命令行传入的学生成绩讲完理论我用一个完整场景收尾。假设你有一个学生成绩文件每行是“姓名 分数”要从命令行读进来按分数降序排序并输出。为了简单下面代码直接演示从命令行参数里读取姓名和分数字符串再排序#include stdio.h #include stdlib.h #include string.h typedef struct { char name[64]; int score; } Student; int cmp_student_desc(const void *a, const void *b) { const Student *sa (const Student *)a; const Student *sb (const Student *)b; return (sb-score sa-score) - (sb-score sa-score); } int main(int argc, char *argv[]) { if (argc 3 || argc % 2 ! 1) { fprintf(stderr, 用法: %s 姓名1 分数1 姓名2 分数2 ...\n, argv[0]); return 1; } int n (argc - 1) / 2; Student *students malloc(sizeof(Student) * n); if (!students) { perror(malloc); return 1; } for (int i 0; i n; i) { snprintf(students[i].name, sizeof(students[i].name), %s, argv[1 2 * i]); students[i].score atoi(argv[2 2 * i]); } qsort(students, n, sizeof(Student), cmp_student_desc); for (int i 0; i n; i) printf(%s %d\n, students[i].name, students[i].score); free(students); return 0; }这段代码有几点值得关注用malloc动态分配数组正好说明了qsort并不关心数组是栈上还是堆上用atoi解析字符串到int可能遇到非法输入生产环境里建议用更严格的解析snprintf复制字符串限制长度防止越界。排序部分和前面没有区别一个comparator搞定。我把这个程序编译运行了一下$ ./students Alice 87 Bob 92 Cindy 78 Bob 92 Alice 87 Cindy 78实际用起来效果很直接。这个案例也说明了qsort在业务代码里的典型用法数据常是动态读进来的数量不确定类型是结构体排序规则多样。我个人在实际操作中的一个体会是qsort用久了之后最值钱的不是“记住参数顺序”而是能把比较函数写得又快又对。写comparator时脑子里过三件事第一进来的void*应该转成什么类型第二返回的符号代表谁在前第三比较逻辑是否覆盖了所有相等和边界情况。这三件事想清楚qsort基本不会出问题。还有一个习惯可以分享凡是写排序代码我总会在旁边留一组小测试数据每次改完comparator就跑一遍确认正序、逆序、重复值、单元素这四种场景都对再提交进项目里。