指针使用回调函数模拟实现qsort在C语言的学习路线里几乎每个人都会遇到“指针”这个坎。很多朋友学到函数指针这一块就开始懵了尤其是看到int (*cmp)(const void *, const void *)这种声明时恨不得当场把书合上。但我想说如果你能亲手把qsort这类库函数“复刻”一遍那些曾经绕晕你的东西会一次性串通。这个项目看起来只是写一个排序工具实际上它把指针、类型擦除、函数指针、回调机制这些C语言里的硬骨头全揉在一起了。做完之后你再回头去看嵌入式里常见的定时器回调、串口中断处理甚至看一下Linux内核里大量使用的函数指针表思路会通透很多。我做这个项目之前一直觉得qsort就是个“能排任意类型数组”的黑盒子。直到自己动手实现了一个简化版才真正理解它为什么设计成那副“奇怪”的样子传入一个void* base当数组首地址传一个size_t width表示每个元素占多少字节再传一个函数指针让调用方决定“什么叫大、什么叫小、什么叫相等”。这三个参数缺一个都不行。去掉widthvoid*根本没法做指针运算去掉回调函数排序算法根本不知道两个元素谁大谁小去掉void*那你就得为每种数据类型写一套排序函数跟面向对象语言里的重载相比反而更麻烦。这个项目就是要把这三件事的内在逻辑讲透。整体设计思路为什么库函数要设计成这个样子先看标准库的头文件声明qsort长这样void qsort(void *base, size_t num, size_t width, int (*cmp)(const void *, const void *));我当年第一次看到这个函数原型第一反应是“为什么第一个参数不是int*或者char*而是个void*”后来才明白void*是C语言实现“泛型”的底层手段。它表示“我只是一个地址我不关心你指向什么类型”。因为C语言没有C的模板也没有Java的泛型想要一个函数既能排int数组又能排double数组还能排在堆上分配的结构体数组就必须把所有具体类型的信息“剥掉”。怎么剥就是让你把“每个元素占几个字节”当作参数传进来。这个思路很像送快递。快递公司要送一批包裹它不需要知道每个包裹里面装的是什么只需知道每个箱子多大、总共有几个箱子、放在哪个货架上就能准确地把第2个箱子搬到第5个位置。void*就是“不知道里面有什么”的货架地址width就是箱子的尺寸num就是箱子的数量。真正打开箱子、检查里面的东西、决定哪个箱子该放前面的那个人是调用方自己写的比较器回调函数。1.1 回调函数承担什么角色什么叫回调函数你可以这么理解我自己写排序算法我只负责“交换”和“比较”的流程控制但我不知道“怎么比较”两个元素。于是我把比较这件需要具体业务知识的事情外包出去让调用方提供一个函数给我。这个函数被当作参数传进来当我需要比较两个元素时我就回头调用你给我的这个函数。在C语言里“把函数当作参数传”这件事没有直接的第一步语法它必须通过函数指针来实现。函数指针的值就是函数的入口地址。一旦拿到这个地址我就可以用cmp(a, b)这样的方式去调用。对排序函数来说它不需要知道调用方比较的是整数、浮点数还是结构体里的某个字段它只需要知道如果cmp(a, b)返回值大于0就说明a应该排在b后面。1.2 类型信息丢失后指针运算怎么补回来用void*接收数组首地址后问题来了void*是不可以做指针运算的。在C语言里p 1这个操作对int*来说意味着地址增加4个字节对double*来说意味着增加8个字节但编译器看到void*时根本不知道元素宽度。所以qsort内部必须先把void*转成char*因为char*做指针运算时步长是1个字节然后手动用width来计算偏移量。假如我要访问下标为i的元素它的地址应该是(char*)base i * width。如果我要访问下标为j1的元素就是(char*)base (j 1) * width。这是整个模拟实现里最核心的指针运算技巧理解了这一行后面看代码就不会卡壳了。核心细节解析函数指针声明、字节交换与比较器封装别急着写排序主流程先打好两个地基函数指针怎么声明以及怎么安全地交换两个“不知道类型”的内存块。2.1 函数指针的“剥洋葱”读法int (*cmp)(const void *, const void *)这条声明很多人一眼就晕。教大家一个土办法从内往外剥和剥洋葱一样。先看最里面(*cmp)说明cmp是一个指针。往右看后面跟着(const void *, const void *)说明这个指针指向一个“有两个const void*参数”的函数。再往左看最左边是int说明这个函数的返回类型是int。所以合起来就是cmp是一个指向函数的指针这个函数接收两个const void*参数返回一个int。注意int *cmp(...)和int (*cmp)(...)完全是两码事。前者是“定义一个函数函数名叫cmp返回值是int*”后者才是“定义一个函数指针变量”。为什么参数要加const因为比较器不需要修改数组内容传const一方面能让标准库实现者有信心你不会在比较函数里偷偷改数据另一方面也允许调用者传入const修饰过的数据进行比较。2.2 交换任意类型数据的swap函数qsort内部的交换函数不能写成void swap(void* a, void* b) { int tmp *(int*)a; *(int*)a *(int*)b; *(int*)b tmp; }一旦这么写这个swap就绑死int类型了。通用的交换必须逐字节进行操作把“元素宽度”作为交换次数。实现也不复杂static void swap_bytes(char* a, char* b, size_t width) { char tmp; for (size_t i 0; i width; i) { tmp a[i]; a[i] b[i]; b[i] tmp; } }这段代码做的事情是把a地址开始的前width个字节和b地址开始的前width个字节逐一交换。看到这里你可能会担心效率问题的确逐字节比直接用机器字长拷贝慢不少标准库内部会做一些对齐优化但我们做这个项目的目的是搞懂原理不追求极致性能。顺着这个思路我习惯在交换前先用memcpy或者tmp分块拷贝但在教学版里逐字节交换最直观。实操过程基于冒泡排序模拟qsort主流程现在开始写主排序函数。我选择了冒泡排序来实现原因很简单冒泡排序的核心操作就是“相邻比较、必要时交换”这正好能最清晰地把比较器回调、地址偏移计算和交换函数串起来。主流商用库内部用的是快速排序或者混合排序但我们模拟实现的重点是机制不是性能。3.1 主体代码与逐步讲解#include stdio.h #include string.h static void swap_bytes(char* a, char* b, size_t width) { char tmp; for (size_t i 0; i width; i) { tmp a[i]; a[i] b[i]; b[i] tmp; } } void my_qsort(void* base, size_t num, size_t width, int (*cmp)(const void*, const void*)) { if (base NULL || cmp NULL || width 0) { return; } char* p (char*)base; for (size_t i 0; i num - 1; i) { for (size_t j 0; j num - 1 - i; j) { char* elem_j p j * width; char* elem_j1 p (j 1) * width; if (cmp(elem_j, elem_j1) 0) { swap_bytes(elem_j, elem_j1, width); } } } }这版代码里最关键的一行是char* p (char*)base;。base是void*不能直接做加减运算所以先转成char*。注意这里转成char*而不是unsigned char*也行因为我们只需要按字节访问和交换不关心符号。接下来每一轮冒泡我都算出相邻两个元素的起始地址p j * width和p (j 1) * width然后把这两个地址交给cmp。cmp和swap_bytes内部都只认字节地址不关心类型这就是整个模拟实现能“泛型”的原因。3.2 缺少width会发生什么你可以做个实验把width参数去掉直接用int的步长来访问数组。然后试着对double数组排序。结果必然是灾难性的p j在double数组里只前进1个字节找出来的“第2个元素”实际上是第一个元素中间的某个字节比较函数读出来的浮点数据完全错乱。这正是width参数存在的根本原因。类似的道理你写通用的序列化函数、内存池管理模块时只要涉及“等大小对象数组”就逃不掉这个参数。写比较器三种典型类型逐一封装qsort主体写完了它是一个“架子”。真正有业务信息的地方是你提供的比较器。4.1 整数数组的比较器整数排序是最基础的情况int cmp_int(const void* a, const void* b) { int ia *(const int*)a; int ib *(const int*)b; return (ia ib) - (ia ib); }注意我故意没有写成return ia - ib;。减法写法简单但存在整数溢出风险。比如ia INT_MAXib -1两者相减直接溢出成负数此时返回值的正负语义就反了。用(ia ib) - (ia ib)这种写法返回值只会是-1、0、1三个值绝对安全而且语义很清晰。这个习惯建议从入职第一天就养成。4.2 浮点数组的比较器double数组和int数组比较器的不同点在于浮点数不能直接用判断相等但这里我们是排序只需要判断大于小于的关系。只要不为NaN常规写法没问题int cmp_double(const void* a, const void* b) { double da *(const double*)a; double db *(const double*)b; return (da db) - (da db); }如果担心NaN可以在比较器里显式处理遇到NaN就把它排在最后。不过普通业务场景这样的比较器已经够用了。4.3 结构体数组按字段排序更贴近工程的场景是排结构体数组。比如一组学生记录既想按学号升序排又想按成绩降序排typedef struct { int id; double score; } Student; int cmp_stu_by_id(const void* a, const void* b) { const Student* sa (const Student*)a; const Student* sb (const Student*)b; return (sa-id sb-id) - (sa-id sb-id); } int cmp_stu_by_score_desc(const void* a, const void* b) { const Student* sa (const Student*)a; const Student* sb (const Student*)b; double da sa-score; double db sb-score; return (db da) - (db da); }比较器里直接操作结构体指针的成员排序函数完全不知道结构体长什么样。你要“先按学号、再按成绩”就写一个组合比较器先比较主字段如果主字段相等再比较次字段。这也是qsort设计最优雅的地方排序流程和业务规则彻底解耦。验证测试与典型场景实测写完代码只是第一步真正有价值的是一次完整的验证过程。5.1 测试int数组int main(void) { int arr[] {5, 2, 8, 1, 9, 3, 7, 4, 6}; size_t n sizeof(arr) / sizeof(arr[0]); my_qsort(arr, n, sizeof(int), cmp_int); for (size_t i 0; i n; i) { printf(%d , arr[i]); } printf(\n); return 0; }输出是1 2 3 4 5 6 7 8 9。这里算元素个数的写法sizeof(arr) / sizeof(arr[0])大家在嵌入式里应该已经写到条件反射了。如果你把这个技巧用在函数参数里就会失效因为数组作为函数参数会退化成指针sizeof(arr)在函数内得到的永远是864位平台指针大小。这也是一个常见坑。5.2 测试结构体数组Student students[] { {1003, 88.5}, {1001, 92.0}, {1002, 79.5}, }; my_qsort(students, 3, sizeof(Student), cmp_stu_by_id); for (size_t i 0; i 3; i) { printf(%d %.1f\n, students[i].id, students[i].score); }输出会按学号排好。如果改成cmp_stu_by_score_desc就会变成成绩从高到低。5.3 字符串数组的特殊性字符串数组往往让人迷糊。如果你这样写const char* words[] {banana, apple, cherry};这个数组的元素类型是const char*也就是“指向字符串的指针”。数组首元素是一个指针那排序器要交换的元素就是两个指针变量。比较器拿到的两个const void*参数指向的是数组里的两个元素而每个元素本身又是指针。所以在比较器内部你得先把const void*转成const char**再解引用拿到字符串地址。int cmp_str(const void* a, const void* b) { const char* sa *(const char**)a; const char* sb *(const char**)b; return strcmp(sa, sb); }这段代码是很多人面试时容易写错的地方。想不清楚的时候画个内存图数组在栈上存字符串指针每个指针指向字符串常量区的某块地址。比较器收到的a是words[0]的类型擦除版本你必须先还原成指针的指针再解引用才能取到banana首地址。这个过程其实就是“二级指针”的典型场景。qsort帮你把元素交换了但你比较器里需要知道元素本质上是指针。回调函数的设计智慧与工程扩展聊完具体代码再往高处走一步。回调函数这个设计在C语言生态里的地位怎么强调都不过分。6.1 回调机制在嵌入式里的体现嵌入式里最常见的回调场景就是中断/事件处理。以HAL库为例你注册一个回调函数等串口收到一帧数据后驱动库内部会在中断上下文中调用你注册的函数。它和qsort里的比较器本质上是同一个套路框架把“什么时候调用”管起来业务方把“具体做什么”填进去。qsort里的比较器是同步回调中断里的回调是异步回调。但两者的核心特点都一样你的函数指针被保存在某个结构体里等到某个时刻框架借助函数指针地址反过来调用它。6.2 函数指针数组的扩展用法如果你还需要“排序方向可控”“比较策略可变”的功能还可以引入函数指针数组。比如int (*comparators[])(const void*, const void*) { cmp_int, cmp_double, cmp_stu_by_id, cmp_stu_by_score_desc, };到时候只需要根据用户输入或者配置项从数组里取出对应下标的函数指针传给my_qsort。这比写一大串switch-case干净得多。函数指针数组在状态机设计、命令解析表、协议处理分发这些场景里都是常规武器。6.3 多关键字排序的组合器如果你想先按score升序、score相同再按id降序可以写一个组合比较器int cmp_score_asc_id_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 (sa-score sb-score) - (sa-score sb-score); } return (sb-id sa-id) - (sb-id sa-id); }比较器只影响比较结果不会影响排序算法本身的流程。这就是东西分层之后的灵活性。常见问题与排查技巧实录实际做完这个项目我录了几个最容易踩的坑。把这些坑列出来比多敲十遍代码管用。7.1 比较函数返回值写错有人图省事直接在比较器里写return *(int*)a - *(int*)b;。数据范围小的时候没问题一旦遇到INT_MAX和INT_MIN之类的极端值运算结果直接溢出比较出的顺序就是错的。排查这类问题用打印法很有效在冒泡循环里把每次比较的返回值打出来一旦发现返回值不符合-1/0/1规律问题基本就定位了。7.2 元素宽度填错width填错是非常隐蔽的bug。你明明写的是int数组结果width填了sizeof(double)指针偏移量全错排序越排越乱。这里想提醒一件事sizeof(arr[0])在数组存在的时候是最好的写法不要自己口算元素大小也不要复制粘贴别的数组的尺寸。7.3 忘记把void*转成char*再做指针运算C标准不允许对void*做加法运算。有些编译器开了GNU扩展能编译过但在标准模式下这就是个编译错误。就算编译过了那也是编译器送你的人情不是标准C的行为。遇到编译错误不要慌检查是不是少了个强转。7.4 比较器里误改数据标准库qsort的比较器参数是const void*这是库给你的承诺我保证在比较过程中不会改你的数据。你自己写my_qsort时也要养成这个习惯比较器参数都写成const。一旦你在比较器里对传入地址做写操作排序过程中数据被改了结果就完全不可预测。排查这种问题可以看排序前后元素的值有没有发生非交换产生的变化。7.5 测试模块化思想做完这个项目后我强烈建议你把“排序算法本体”和“比较器集合”分开编译、单独测试。做一个简单的命令行程序通过参数选择用哪个比较器排序哪组数据。这样以后你新增一种数据类型只需要增加一个比较器函数不需要动排序主体。这也是回调函数最大的收益面向扩展开放面向修改关闭。回到项目标题本身。“指针使用回调函数模拟实现qsort”这个题目表面上是要求你写一个排序工具实际上是在训练你的抽象能力。你需要在脑海中建立这样一个模型排序算法是一台机器它只负责按规定的流程搬运物品至于物品之间谁先谁后是由一张写着规则的卡片决定的这张卡片就是回调函数。指针则是让这一切能运转起来的底层机制void*抹平了类型差异char*配合width实现了精确的字节寻址函数指针让“规则”能作为参数传递。把这个模型吃透以后你看任何带回调接口的库不管是定时器、中断、协议栈还是GUI框架都不会再觉得神秘。如果只是把代码抄一遍收获有限建议你关掉这篇文章自己先动手写一版然后在测试过程中去体会“为什么参数要这么设计”“为什么这里必须用二级指针”踩过这些坑之后你才算是真正把这个项目消化成了自己的能力。