第49章 qsort 函数

课程目录第49章 qsort 函数

49、qsort 函数：如何用 qsort 对结构体排序？

排序这事儿，在嵌入式开发里太常见了。传感器数据要排序、任务优先级要排序、日志时间戳也要排序。C 标准库给了我们一个万能排序工具——qsort。但很多人第一次用它排结构体时，都会栽跟头。今天我就把这事彻底讲透。

qsort 到底怎么用？

先看它的函数原型：

#include <stdlib.h>

void qsort(void *base, size_t nmemb, size_t size,
           int (*compar)(const void *, const void *));

四个参数，说白了就是：

base：数组首地址
nmemb：元素个数
size：每个元素的大小（字节数）
compar：比较函数的指针

嗯，这里要注意——比较函数是灵魂。你写对了，排序就对了；写错了，结果全乱套。

结构体排序实战

假设我们要排一个学生成绩表，按分数从高到低排。结构体长这样：

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

比较函数怎么写？我直接给代码：

int cmp_desc(const void *a, const void *b) {
    // 先把 void* 转回 Student*
    const Student *sa = (const Student *)a;
    const Student *sb = (const Student *)b;

    // 降序：b 的分数减 a 的分数
    if (sb->score > sa->score) return  1;
    if (sb->score < sa->score) return -1;
    return 0;
}

调用起来很简单：

Student arr[] = {
    {"Alice", 88},
    {"Bob",   95},
    {"Cindy", 72},
    {"David", 95}
};
int n = sizeof(arr) / sizeof(arr[0]);

qsort(arr, n, sizeof(Student), cmp_desc);

排完之后，Bob 和 David 都是 95 分排最前面，然后是 Alice 88 分，Cindy 72 分垫底。

核心要点：比较函数返回正数表示 a 排在 b 后面，返回负数表示 a 排在 b 前面，返回 0 表示相等。这个逻辑别搞反了。

为什么有人会写错？

我见过最典型的错误，是直接拿指针去减：

// ❌ 错误写法
int cmp_wrong(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

这种写法对整数排序偶尔能蒙对，但一旦遇到结构体，或者分数是负数，立马翻车。为什么？因为 int 减法可能溢出。你想想看，如果 a 是 INT_MIN，b 是 INT_MAX，一减直接溢出成负数，排序结果就全错了。

我在项目中遇到过类似问题——一个嵌入式设备上报的温度数据排序，有人用了减法写法，结果在极端温度下排序完全乱掉。排查了两天才找到原因。从那以后，我写比较函数一律用 if-else 或 >、< 比较，绝不用减法。

多字段排序怎么办？

实际项目中，经常需要先按一个字段排，相等时再按另一个字段排。比如学生先按分数降序，分数相同再按姓名字典序升序。

int cmp_multi(const void *a, const void *b) {
    const Student *sa = (const Student *)a;
    const Student *sb = (const Student *)b;

    // 先比分数（降序）
    if (sb->score > sa->score) return  1;
    if (sb->score < sa->score) return -1;

    // 分数相等，比姓名（升序）
    return strcmp(sa->name, sb->name);
}

逻辑很清楚：分数分出高低就直接返回，分数相等再走 strcmp。我个人习惯把这种「先主后次」的写法叫做「瀑布式比较」——一层层往下落，直到分出胜负。

避坑指南

我曾经踩过的坑，你最好别踩：

比较函数参数类型别写错：一定是 const void *，不是 const Student *。虽然你可以在函数内部强转，但函数签名必须严格匹配。
结构体大小别算错：sizeof(Student) 而不是 sizeof(Student*)。我见过有人传指针大小进去，结果 qsort 把内存当数组乱切，直接崩了。
字符串比较用 strcmp：别自己写循环比字符，strcmp 已经帮你处理了大小写、本地化等问题。
相等时返回 0：如果两个元素完全相等，必须返回 0。虽然 qsort 不保证稳定排序，但返回 0 至少不会破坏已有顺序。

知识体系一览

下面这张图把 qsort 排结构体的核心流程串起来了：

性能小贴士

嵌入式环境资源有限，qsort 用的是快速排序算法，平均时间复杂度 O(n log n)。但最坏情况会退化到 O(n²)。如果你对实时性要求极高，或者数组几乎有序，可以考虑改用插入排序或堆排序。不过话说回来，对于几百个结构体以内的场景，qsort 完全够用，别过度优化。

我的个人习惯：在嵌入式项目中，如果结构体比较大（比如包含长字符串或数组），我会先排一个索引数组，而不是直接排结构体本身。这样能减少内存拷贝，速度更快。代码大概长这样：

int idx[n];
for (int i = 0; i < n; i++) idx[i] = i;

qsort(idx, n, sizeof(int), cmp_by_idx);

// cmp_by_idx 里通过 idx 访问原数组
int cmp_by_idx(const void *a, const void *b) {
    int ia = *(const int*)a;
    int ib = *(const int*)b;
    // 比较 arr[ia] 和 arr[ib] 的分数
    ...
}

这样原数组纹丝不动，排序结果通过索引顺序体现。在内存紧张或结构体很大的场景下，这招特别好使。

好了，qsort 排结构体这事，说白了就是三步：写好结构体、写好比较函数、传对参数。其中比较函数是唯一需要动脑子的地方。你只要记住「返回正数表示 a 在后，负数表示 a 在前」，基本就不会翻车。

公众号:蓝海资料掘金营，微信deep3321

📚 课程目录