排序与搜索：qsort、bsearch 与自定义比较函数

排序和搜索，是 C 语言命令行工具里最常用的两个操作。你想想看，不管是处理日志文件、解析配置数据，还是做内存数据库的索引，都离不开它们。今天我就把这两个家伙彻底讲透。

一、qsort：C 标准库的排序利器

qsort 是 C 标准库提供的快速排序实现。名字里的 "q" 就是 "quick"，快速。它定义在 <stdlib.h> 里，原型长这样：

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

参数看着多，其实就四个：

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

嗯，这里有个关键点——比较函数。qsort 不知道你要排整数还是排字符串，它只负责交换内存块。怎么比，得你告诉它。

整数排序示例

#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;
    // 升序：ia - ib
    // 降序：ib - ia
    return ia - ib;
}

int main() {
    int arr[] = {34, 7, 23, 32, 5, 62};
    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;
}

输出：5 7 23 32 34 62

字符串排序示例

int cmp_str(const void *a, const void *b) {
    // a 和 b 是 char** 类型，因为数组元素是 char*
    const char *sa = *(const char **)a;
    const char *sb = *(const char **)b;
    return strcmp(sa, sb);
}

// 调用
char *words[] = {"banana", "apple", "cherry", "date"};
qsort(words, 4, sizeof(char *), cmp_str);

这里容易犯的错是：把 const char ** 写成了 const char *。记住，数组元素是指针，所以比较函数收到的参数是指向指针的指针。

二、bsearch：二分查找的正确姿势

排序之后，自然就是查找。bsearch 是二分查找的标准实现，前提是数组必须已经排好序。

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

参数和 qsort 几乎一样，多了一个 key——你要找的目标值。返回的是找到的元素的指针，找不到返回 NULL。

int target = 23;
int *found = bsearch(&target, arr, n, sizeof(int), cmp_int);
if (found)
    printf("找到了：%d\n", *found);
else
    printf("没找到\n");

我个人习惯把 key 也封装成指针传递，这样比较函数可以统一处理。比如查找结构体时，key 可以是一个只填充了关键字段的临时结构体。

三、自定义比较函数：灵活性的灵魂

qsort 和 bsearch 的强大之处，就在于你可以通过比较函数实现任意排序逻辑。我整理了几种常见模式：

场景	比较函数写法	说明
整数升序	return ia - ib;	注意溢出风险
整数降序	return ib - ia;	交换 a、b 位置
字符串升序	return strcmp(sa, sb);	区分大小写
字符串降序	return strcmp(sb, sa);	交换参数
结构体按字段	return a->age - b->age;	先转成结构体指针
多级排序	先比字段1，相等再比字段2	用 if-else 链

多级排序示例

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

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

    // 先按年龄升序
    if (sa->age != sb->age)
        return sa->age - sb->age;
    // 年龄相同，按分数降序
    if (sa->score != sb->score)
        return (sa->score > sb->score) ? -1 : 1;
    // 分数也相同，按名字字典序
    return strcmp(sa->name, sb->name);
}

我在项目中遇到过需要按多个字段排序的场景，比如先按优先级、再按时间戳、最后按 ID。这种多级比较函数写起来很直观，就是一层层 if 判断。

四、排序算法选型：什么时候用什么

qsort 用的是快速排序，平均 O(n log n)，最坏 O(n²)。但标准库的实现通常做了优化（比如三数取中、小数组转插入排序），所以实际表现很稳定。

不过，不是所有场景都适合用 qsort。我根据自己的经验画了张选型图：

说说我的经验：

• 通用场景：直接用 qsort。标准库的实现经过了大量测试，比你自己手写的快排稳定得多。
• 小数据量（n < 50）：插入排序反而更快。因为 qsort 有递归开销，插入排序的常数极小。
• 几乎有序的数据：插入排序 O(n)，qsort 反而可能退化到 O(n²)。
• 需要稳定排序：qsort 是不稳定的。如果你需要相等元素的相对顺序不变，用归并排序。
• 外部排序：数据量超过内存时，用归并排序的分治思想做外部排序。

五、综合实战：命令行工具的排序+搜索

最后，我写一个完整的例子。假设我们要做一个处理学生成绩的小工具：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

int cmp_by_score(const void *a, const void *b) {
    const Student *sa = (const Student *)a;
    const Student *sb = (const Student *)b;
    if (sa->score < sb->score) return 1;  // 降序
    if (sa->score > sb->score) return -1;
    return 0;
}

int cmp_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;
}

int main() {
    Student students[] = {
        {3, "张三", 88.5},
        {1, "李四", 92.0},
        {2, "王五", 76.5},
        {4, "赵六", 88.5}
    };
    size_t n = sizeof(students) / sizeof(students[0]);

    // 按分数降序排序
    qsort(students, n, sizeof(Student), cmp_by_score);
    printf("按分数降序：\n");
    for (size_t i = 0; i < n; i++)
        printf("  %d %s %.1f\n", students[i].id, students[i].name, students[i].score);

    // 按 ID 排序，准备二分查找
    qsort(students, n, sizeof(Student), cmp_by_id);
    printf("\n按 ID 排序后：\n");
    for (size_t i = 0; i < n; i++)
        printf("  %d %s %.1f\n", students[i].id, students[i].name, students[i].score);

    // 二分查找 ID=2 的学生
    Student key = {2, "", 0};
    Student *found = bsearch(&key, students, n, sizeof(Student), cmp_by_id);
    if (found)
        printf("\n找到 ID=2：%s，分数 %.1f\n", found->name, found->score);
    else
        printf("\n没找到\n");

    return 0;
}

这个例子展示了两个关键点：

1. 同一个结构体可以用不同的比较函数实现不同的排序逻辑
2. bsearch 要求数组必须按比较函数的规则排好序

好了，排序和搜索就讲到这里。qsort 和 bsearch 是 C 标准库里的黄金搭档，掌握了它们，大部分数据处理场景你都能应付。记住：比较函数是灵魂，排序前想清楚规则，查找前确认有序。做到这三点，基本不会翻车。

---

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