指针：使用回调函数模拟实现qsort
在C语言的学习路线里，几乎每个人都会遇到“指针”这个坎。很多朋友学到函数指针这一块就开始懵了，尤其是看到int (*cmp)(const void *, const void *)这种声明时，恨不得当场把书合上。但我想说，如果你能亲手把qsort这类库函数“复刻”一遍，那些曾经绕晕你的东西会一次性串通。这个项目看起来只是写一个排序工具，实际上它把指针、类型擦除、函数指针、回调机制这些C语言里的硬骨头全揉在一起了。做完之后你再回头去看嵌入式里常见的定时器回调、串口中断处理，甚至看一下Linux内核里大量使用的函数指针表，思路会通透很多。
我做这个项目之前，一直觉得qsort就是个“能排任意类型数组”的黑盒子。直到自己动手实现了一个简化版，才真正理解它为什么设计成那副“奇怪”的样子：传入一个void* base当数组首地址，传一个size_t width表示每个元素占多少字节，再传一个函数指针让调用方决定“什么叫大、什么叫小、什么叫相等”。这三个参数，缺一个都不行。去掉width，void*根本没法做指针运算；去掉回调函数，排序算法根本不知道两个元素谁大谁小；去掉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。如果我要访问下标为j+1的元素，就是(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_MAX，ib = -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)在函数内得到的永远是8（64位平台指针大小）。这也是一个常见坑。
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框架，都不会再觉得神秘。如果只是把代码抄一遍，收获有限；建议你关掉这篇文章，自己先动手写一版，然后在测试过程中去体会“为什么参数要这么设计”“为什么这里必须用二级指针”，踩过这些坑之后，你才算是真正把这个项目消化成了自己的能力。
