快速排序qsort是C语言标准库里出场率最高的排序函数，也是被误解最多的一个。很多人用过它，但很少有人真正读懂它；今天我想把这几个事一次讲透：qsort的用法、它背后的快速排序思想，以及怎样不看库源码，自己动手模拟实现一个功能相同、接口兼容的通用排序函数。这篇内容适合正在学指针和函数回调的初学者，也适合工作多年、能用qsort但心里始终没把握的开发者。看完之后，你至少能做到三件事：几秒钟写对任意数据类型的比较器、独立实现一个行为接近库函数的通用排序函数、排序结果异常时知道问题出在哪个环节。

1. qsort是谁：为什么这个名字会骗人

1.1 “快速排序”四个字带来的误会

qsort的全称其实是quick sort，在编程历史上，这个函数真的就是按照快速排序算法设计的。1970年代大牛们把快速排序带进C语言标准库，取名qsort，一直沿用到现在。后来C标准逐步更新，标准里对qsort的实现算法却一直没有硬性规定：它不要求你必须用快速排序，也不保证排序是稳定的。所以现代很多编译器的标准库实现，表面叫qsort，内部早就换成了introsort这种混排方案：数据量小的时候切到插入排序，递归深度太深的时候切到堆排序，防止快速排序退化成O(n^2)。

这意味着什么？意味着你研究qsort的重点，一开始就不应该放在“它内部到底怎么快”上，而应该放在“它为什么能对任意类型数组排序”上。快速排序只是它的历史出身，泛型思想才是它的灵魂。

1.2 qsort真正解决的是什么问题

假设没有qsort，你想在C语言里排序一个int数组，写一个int_sort函数；明天要排double数组，再写一个double_sort；后天排结构体，又要复制粘贴改类型。这种重复劳动让人崩溃。

qsort用三个设计点解决了这个问题。第一，参数用void*，把“地址”抽象出来，不关心你指向什么类型；第二，用size_t类型的元素个数加元素宽度，告诉函数“数组有多长、每个元素占几个字节”；第三，把“怎么比较大小”这个策略彻底交给调用者，通过函数指针传进来。三个点合在一起，让同一个排序函数既能排int，又能排double，还能排结构体。

这个设计在今天就叫“控制反转”，而在C语言里，它靠的就是void指针、函数指针和回调这三个基本功。qsort是一个看上去简单、实际上把泛型编程精髓全包含在内的函数。

2. qsort用法：从函数签名到比较器

2.1 函数签名逐字段拆解

先看完整的函数原型：

#include <stdlib.h> void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void *));

四个参数各司其职。base是待排序数组的首元素地址；nitems是数组中元素的总个数；size是每一个元素占用的字节数，通常用sizeof(类型)计算；最后一个参数是函数指针，它指向一个自定义的比较函数。

有几个同学问过：既然第一个参数已经是void*，为什么还要单独传元素个数和元素宽度？因为void有个毛病，它丢失了类型信息。C语言的指针运算是和类型绑定的，int加1跳4个字节，double加1跳8个字节，而void不知道自己是啥，你根本不知道加1应该跳多远。所以qsort必须由调用者显式告诉它“每个元素有多宽”，函数内部把base转成char*，然后按base + i * size去定位第i个元素。

比较器的要求也很明确，它接收两个const void*，分别指向数组中的两个元素。返回值必须满足：第一个参数小于第二个参数时返回负值，相等返回0，大于返回正值。这个约定是整个排序契约的核心，写错了排序必然乱。

2.2 int、double、字符串的常见比较器

先来最经典的int数组排序：

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 arr[] = {3, 1, 4, 1, 5, 9, 2, 6}; qsort(arr, sizeof(arr) / sizeof(arr[0]), sizeof(int), cmp_int);

很多人习惯写return(int)a -(int)b;。这个写法在小整数数组上没问题，但存在一个隐患：如果两个数差距过大，减法结果可能溢出int范围。比如一个数是INT_MAX，另一个是INT_MIN，相减结果直接变成不确定的溢出值，比较器就撒谎了。更稳妥的写法是我上面这种，用两次布尔表达式组合成-1、0、1三个状态，任何整数都不会有溢出问题。

double数组是另一个高频翻车点：

// 错误示范 int cmp_double_wrong(const void *a, const void *b) { return *(double *)a - *(double *)b; }

这个错误很隐蔽。比较器返回值是int，而两个double相减的结果是double，赋值时发生了截断。比如0.5和0.2的差是0.3，截断成int就是0，比较器告诉排序函数这俩相等，最后顺序乱得莫名其妙。

正确的double比较器应该用分支：

int cmp_double(const void *a, const void *b) { double da = *(const double *)a; double db = *(const double *)b; if (da > db) return 1; if (da < db) return -1; return 0; }

从这段代码也能看出“写比较器”这件事没有捷径，每换一种类型，你都得到函参数里重新解读一次数据。

2.3 字符串指针数组的二级指针陷阱

排序字符串数组是新手最容易卡住的地方。这里的“字符串数组”指的是char数组，也就是charstr_array[N];

char *strs[] = {"banana", "apple", "pear", "orange"};

数组里存的是指向字符串的指针，每个元素是char*。qsort比较时，回调参数a和b指向的是数组中的元素，元素本身是char*，所以a和b的类型实际上是char**。比较器要先把void转成char**，再解引用拿到char，最后交给strcmp：

int cmp_str(const void *a, const void *b) { char * const *sa = (char * const *)a; char * const *sb = (char * const *)b; return strcmp(*sa, *sb); }

如果手滑写成return strcmp((char*)a, (char*)b);，意思就全变了：你把字符串本身的内存地址当成char*传给了strcmp，strcmp会从那个地址开始读字节，读到后面越界。这个错误轻则是排序顺序完全随机，重则是直接段错误。

还有一种是二维字符数组char words[N][64]，每个字符串存在连续的行里。这时a和b指向的其实是char[64]这个数组类型，比较器直接转成char*就行：

int cmp_words(const void *a, const void *b) { return strcmp((const char *)a, (const char *)b); }

两种字符串容器的数据结构不同，比较器写法就不同，这就是为什么qsort要求你自己写比较器——因为只有你才知道数组里到底装的是什么。

2.4 降序、多关键字和“稳定化”

降序是最容易实现的变体，把a和b对调就行：

int cmp_int_desc(const void *a, const void *b) { return cmp_int(b, a); }

多关键字排序本质上就是“先比主字段，主字段相等再比次字段”。比如先按成绩降序，成绩相同按学号升序：

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 (sa->id > sb->id) - (sa->id < sb->id); // 学号升序 }

顺带说一嘴“稳定性”。C标准不保证qsort稳定，也就是说两个成绩完全相同的元素，排序后原来的前后关系不一定保持。如果你在业务里必须稳定，一个通用技巧是给结构体增加一个index字段，记录元素原始下标，然后在比较器里把“完全相等”的情况改成按index比较。这样排完之后，相等元素的相对顺序就等于原始顺序，稳定性相当于手动找回来了。

3. 实战案例：一个成绩排序脚本的完整进化

3.1 第一版：按成绩排序

我用一个常见的模拟场景来说明，假设要管理一小批学生成绩数据：

typedef struct { char name[16]; int id; int score; } Student;

初始化几条数据：

Student stu[] = { {"stu01", 1004, 87}, {"stu02", 1001, 92}, {"stu03", 1003, 87}, {"stu04", 1002, 78} }; size_t n = sizeof(stu) / sizeof(stu[0]); qsort(stu, n, sizeof(Student), cmp_student);

按成绩升序排列，效果是stu04(78)、stu01(87)、stu03(87)、stu02(92)。这里有个细节：stu01和stu03成绩相同，它们谁在前谁在后完全取决于qsort内部的分区过程，不保证任何顺序。如果要让这种并列情况也稳定，就在比较器里补一个id的比较。

3.2 第二版：加姓名和学号混合排序

实际业务里经常会遇到“排序规则动态变化”的需求。有人想按成绩，有人想按姓名，还有人想按学号。qsort的好处是排序函数本身不用动，只需要换比较器。

按姓名排序的比较器：

int cmp_name(const void *a, const void *b) { const Student *sa = (const Student *)a; const Student *sb = (const Student *)b; return strcmp(sa->name, sb->name); }

每次新增一种排序需求，就是新增一个比较器函数，原来已经排序好的数组随时可以用新规则重新排序。这也是“策略模式”在C语言里最朴素的形态。

3.3 写比较器时最容易破坏数据的一步

有一次我看到同事写的比较器长这样：

int cmp_damaged(const void *a, const void *b) { Student *sa = (Student *)a; Student *sb = (Student *)b; if (sa->score < sb->score) return -1; if (sa->score > sb->score) return 1; // 成绩相同，交换一下，帮助排序？ Student t = *sa; *sa = *sb; *sb = t; return 0; }

这段代码的逻辑是“成绩相等就交换一下”。结果当然是一塌糊涂。比较器本质上是给排序算法提供“参考消息”，它不应该修改数组内容。你在比较器里动手脚，排序算法的各种假设全部失效，轻则数据错乱，重则无限循环。记住：比较器只读不改，这是红线。

4. 先看懂快速排序，再谈模拟实现

4.1 分治、选基准、原地交换

在动手模拟qsort之前，最好先有一个标准的快速排序实现作为参照。传统的快速排序用分治思想：从数组中选一个基准元素pivot，把小于它的元素放到左边，大于它的放到右边，然后对左右两个子区间递归执行同样的过程。

下面是个很经典的int版实现：

void quick_sort_c(int arr[], int low, int high) { if (low >= high) return; int i = low; int j = high; int pivot = arr[low]; while (i < j) { while (i < j && arr[j] >= pivot) j--; if (i < j) arr[i++] = arr[j]; while (i < j && arr[i] <= pivot) i++; if (i < j) arr[j--] = arr[i]; } arr[i] = pivot; quick_sort_c(arr, low, i - 1); quick_sort_c(arr, i + 1, high); }

这段代码的逻辑是“挖坑填数”：先以arr[low]为基准挖一个坑，从右往左找小于基准的数填坑，再从左往右找大于基准的数填新坑，两指针相遇时把基准放回去。写完这个版本，再去看各种排序可视化动画，立刻就能对应上。

4.2 复杂度与最坏情况的来源

快速排序平均复杂度是O(n log n)，最坏是O(n^2)。为什么最坏会变慢？因为一旦每次选的基准都恰好是当前区间的最小值或最大值，分区就极不平衡——一边是0个元素，另一边是n-1个元素，递归深度从log n退化到n，总比较次数变成“等差数列”式的O(n^2)。

经典的坑是：数组已经基本有序，而你又固定取第一个元素当基准时，最坏情况就会发生。这也是标准库实现会引入“三数取中”或者随机选基准的原因。你以为自己在排一个乱序数组，实际上排一个近似有序的数组时，朴素快排反而最难受。

4.3 void*带来的麻烦和解决办法

从int版本的快速排序走向通用qsort，最大的鸿沟不是算法本身，而是类型被抹掉了。int版本可以直接写arr[i] = pivot，因为编译器知道arr是int*，步长固定是4字节；但void*版本的数组里，编译器不知道步长，更不知道元素怎么赋值。

解决办法只有一个：把void转成char，手动用元素宽度去计算地址。char*天生按字节步进，sizeof(char)就是1，于是第i个元素的地址就可以写成base + i * size。后续所有移动、交换、比较，都在这个字节地址上操作。这是模拟实现里最核心的一步，理解了它，整个模拟实现就完成了一半。

5. 模拟实现qsort：从冒泡接口到泛型快排

5.1 第一步：用最朴素的冒泡写出通用接口

模拟实现qsort的第一步，我建议先用冒泡排序，因为冒泡代码量最小、逻辑最直观，能把精力全部集中在“如何用void*和函数指针接口”这个问题上。

void swap_bytes(void *a, void *b, size_t width) { char *ca = (char *)a; char *cb = (char *)b; for (size_t i = 0; i < width; i++) { char tmp = ca[i]; ca[i] = cb[i]; cb[i] = tmp; } } void my_qsort_bubble(void *base, size_t n, size_t width, int (*cmp)(const void *, const void *)) { if (n < 2) return; char *arr = (char *)base; for (size_t i = 0; i < n - 1; i++) { for (size_t j = 0; j < n - 1 - i; j++) { char *left = arr + j * width; char *right = arr + (j + 1) * width; if (cmp(left, right) > 0) swap_bytes(left, right, width); } } }

这段代码有几个细节必须说明。第一，开头那个if (n < 2) return;不是可有可无。如果n是0，n-1在size_t类型下会变成size_t的最大值，外层循环会无限跑下去，直接踩中无符号数下溢的坑。第二，交换函数必须接收width，因为qsort不知道元素类型，它只能把元素当成width个连续的字节看待。第三，回调参数传的是left和right，也就是元素的地址，不是元素的值；值怎么解释，完全交给比较器。

5.2 第二步：字节交换改成块交换

逐字节交换的缺点很明显：如果元素是32字节的大结构体，每交换一次就要做32次单字节内存读写。优化思路是用一块临时缓冲，批量拷贝：

void swap_block(void *a, void *b, size_t width) { char tmp[64]; char *ca = (char *)a; char *cb = (char *)b; size_t chunk; while (width >= sizeof(tmp)) { memcpy(tmp, ca, sizeof(tmp)); memcpy(ca, cb, sizeof(tmp)); memcpy(cb, tmp, sizeof(tmp)); ca += sizeof(tmp); cb += sizeof(tmp); width -= sizeof(tmp); } memcpy(tmp, ca, width); memcpy(ca, cb, width); memcpy(cb, tmp, width); }

这个函数先用固定64字节的栈缓冲区做大块交换，剩余不足64字节的尾巴再用memcpy收掉。栈上数组的分配不在堆上，不用考虑malloc失败，速度也远快于逐字节循环。这个优化技术在真实项目里很实用，前提是元素宽度不要超过合理范围，如果元素特别大，另一种思路就是下面要讲的索引排序。

5.3 第三步：把内核换成真正的快速排序

冒泡版接口跑通之后，已经可以宣称“模拟实现qsort”了，因为它和库函数共用同一个函数指针契约。但如果想让算法也接近真正的qsort，就需要把内部换成泛型快速排序。

static void qsort_range(char *arr, size_t left, size_t right, size_t width, int (*cmp)(const void *, const void *)) { if (left >= right) return; char *pivot = arr + left * width; size_t store_index = left; size_t i; for (i = left + 1; i <= right; i++) { char *cur = arr + i * width; if (cmp(cur, pivot) < 0) { store_index++; if (store_index != i) swap_bytes(arr + store_index * width, cur, width); } } if (store_index != left) swap_bytes(arr + store_index * width, pivot, width); if (store_index > left) qsort_range(arr, left, store_index - 1, width, cmp); if (store_index + 1 < right) qsort_range(arr, store_index + 1, right, width, cmp); } void my_qsort_quick(void *base, size_t n, size_t width, int (*cmp)(const void *, const void *)) { if (n < 2) return; qsort_range((char *)base, 0, n - 1, width, cmp); }

这是经典的Lomuto分区方案，逻辑上比挖坑填数的版本更好理解。我故意在递归边界上用if (store_index > left)这一类显式判断，而不是写成qsort_range(arr, left, store_index - 1, ...)这种不带保护的调用，就是为了防止当store_index为0的时候size_t下溢。这种边界保护的意识，是写泛型算法时最容易被忽视又最容易出事故的地方。

5.4 与标准库相比，少了哪些工程细节

我这份泛型快排和标准库的qsort差别还很大。标准库实现通常会做三件事：用三数取中选择pivot，降低有序数组触发最坏情况的概率；小区间改用插入排序，避免递归函数调用开销过大；检测递归深度过深或数据规模异常时切换堆排序，确保最坏情况也是O(n log n)。

这些优化每一个都可以写单独文章展开。但我不建议初学者一上来就追求这些，而是先把接口契约、字节寻址、交换逻辑这层地基打扎实。地基稳了，看任何库源码都像看故事书；地基不稳，直接看introsort只会更懵。

6. 高频踩坑记录与排查套路

6.1 三种“比较器翻车”现场

常见问题我汇总成一张表，对照着查会方便很多。

比较器翻车还有一个共性表现：同样的数据，有时候排出来对，有时候排出来不对。原因往往是比较器内部依赖外部状态，比如使用了全局变量，而全局变量在排序过程中被其他线程改了。排查这一步就需要先从“比较器必须是纯函数”来检查。

6.2 浮点数、NaN与比较器的“职业道德”

double比较器里如果不处理NaN，可能引发严重问题。NaN和任何值的比较得出的结果都是false，也就是说da > db和da < db都成立不了，比较器只能返回0，告诉排序函数“它们相等”。

问题来了：如果排序函数拿NaN和另一个NaN比较，返回0，两个NaN不交换，勉强能过去；但NaN和正常数值比较也返回0，整个数组就会被当成一堆相等元素，顺序完全随机。更糟的是，NaN的存在会破坏比较器的严格弱序性质，导致排序算法进入未定义行为区域。

正经写代码要处理NaN：

int cmp_double(const void *a, const void *b) { double da = *(const double *)a; double db = *(const double *)b; if (isnan(da)) return 1; if (isnan(db)) return -1; if (da > db) return 1; if (da < db) return -1; return 0; }

这样所有NaN都会被排到数组末尾，其他数值部分保持正常排序。所谓比较器的“职业道德”，就是指它必须对所有输入都给出明确、一致的反馈，不能出现“我不确定、我随便说”的情况。

6.3 空数组与极端参数的地雷

自己实现排序函数最容易漏掉参数校验。n为0时，任何n-1运算在无符号类型下都会爆炸；n为1时，排序函数可以直接返回，但有些没经验的实现还会进入循环访问越界；base为空指针且n大于0时，访问直接段错误。

标准库qsort对空数组的处理是天然安全的，因为它内部对n < 2做了分支。但咱们自己写模拟实现时，这些边界问题必须显式处理，否则别人拿你的函数一跑，第一轮就崩。

除了空数组，还要注意大结构体的性能地雷。如果你给qsort传一个每条记录长达1KB的结构体数组，排序期间每次交换都要搬移1KB内存，n很大时会非常慢。一个工程上常用的优化方案是排序索引数组，而不是排序原始数组，这我会在后面详细写。

6.4 给比较器加“监听”来调试

排序结果不对，很多人的第一反应是去看排序函数，实际上大多数bug都在比较器里。有一个很有效的调试技巧：把比较器临时包一层监听函数，把每次比较的两个元素打出来。

int debug_cmp(const void *a, const void *b) { int r = real_cmp(a, b); int ia = *(const int *)a; int ib = *(const int *)b; printf("cmp(%d, %d) = %d\n", ia, ib, r); return r; }

然后把调用处的函数指针从real_cmp临时换成debug_cmp。这样你能直接看到排序算法在比较哪些元素，返回了什么结果。如果发现“比较结果一会儿正一会儿负，但又对应不上数据本身”，那基本可以断定比较器有状态问题。排查完后记得把监听去掉，不要把调试输出留在生产代码里。

7. qsort之外：还有多少东西值得延伸

7.1 索引排序：大结构体排序的终极解法

当结构体体积很大时，直接对结构体数组排序会不停拷贝大块内存。一种经典实践是建一个int索引数组，排序时只交换索引，比较时通过索引去访问原始数组。比较器本身无法携带原始数组指针，所以通常用全局变量保存：

Student *g_pool; int cmp_by_idx(const void *a, const void *b) { int ia = *(const int *)a; int ib = *(const int *)b; return cmp_student(&g_pool[ia], &g_pool[ib]); } // 用法 Student *pool = ...; size_t n = ...; int *idx = malloc(n * sizeof(int)); for (size_t i = 0; i < n; i++) idx[i] = i; g_pool = pool; qsort(idx, n, sizeof(int), cmp_by_idx);

排完之后，idx数组里存的就是排序后的原始下标。通过idx[i]取出的数据是升序的，而原始数组完全没动。这在处理大对象、并且需要保留多个字段顺序时非常有用。

这类应用也暴露了qsort一个设计缺陷：比较器没办法接收一个额外的用户上下文参数。解决办法要么是全局变量，要么是自己写一个带context参数的排序函数，不过这就超出了标准库接口的范畴。

7.2 缺少上下文参数的设计缺口

qsort的比较器只能通过参数拿到两个元素的指针，拿不到额外的调用者数据。这在多线程环境下格外难受：如果两个线程同时在跑排序，都用同一个全局变量保存“池子指针”，相互之间就会互相干扰。

自己实现一个排序函数时，可以在接口层多加一个参数：

void sort_ctx(void *base, size_t n, size_t width, int (*cmp)(const void *, const void *, void *), void *ctx);

比较器多接收一个void* ctx，这个指针原样透传给你。调用者可以传入结构体地址、数组地址或者任何上下文数据，彻底摆脱全局变量。这也说明了“标准库的经典接口”不是不可超越的，理解它以后，你可以在此基础上设计更符合自己业务需求的东西。

7.3 一个接口思维吃遍各种语言

学完qsort以后会发现，现代语言里的排序接口基本都是同一个套路。JavaScript的Array.prototype.sort接收一个compareFunction，C#的List.Sort可以传Comparison ，Python的sorted用key函数决定排序依据，Rust的sort_by接收闭包。万变不离其宗：排序算法负责“怎么排”，比较逻辑交给调用者负责“怎么比较”。

这种“把发生变化的部分封装出去”的设计，在程序设计里无处不在。qsort作为最早把这种设计批量传给普通开发者的接口之一，值得你多花一些时间吃透。每当你看到一个接口里出现函数指针、lambda、比较器、回调这类东西，都可以回想到qsort：它的聪明和它的坑，全都来自“把比较逻辑交给用户”这一个决定。

如果你问我什么时候算真正掌握了qsort，我的标准很简单：第一，三秒钟内能写出任意类型数组的正确比较器；第二，能说清字符串数组为什么必须二次解引用；第三，遇到排序结果怪异，第一反应是怀疑比较器而不是排序函数。我自己就因为用减法比较double翻过车，也亲眼见过同事把char**写成char*导致线上数据全乱。建议你把我上面这个冒泡版和快排版模拟各敲一遍，敲完再去翻系统库里的qsort源码，感受完全不一样。这可能是C语言里最值得亲手造一次轮子的地方。