C 语言排序与查找的工程实践

更新时间：2026-08-26。本文是 languages/c/ 主题高手层的骨架文档（占位），完整展开将在后续批次补齐。

本文要回答的问题

• qsort 的第四个参数怎么写才不踩坑？
• bsearch 为什么要求数组先排好序？
• 结构体数组怎么按某个字段排序？

一、qsort 与比较函数

int cmp_int(const void *a, const void *b) {
    int x = *(const int *)a, y = *(const int *)b;
    return (x > y) - (x < y);   /* 安全返回 -1/0/1，避免减法溢出 */
}

qsort(arr, n, sizeof(int), cmp_int);

关键约定：返回负数/0/正数 表示 a<b/a==b/a>b。两个常见坑：

坑	后果	解法
返回 *a - *b	大数减法溢出，排序错乱	用比较再相减，或 (a>b)-(a<b)
忘记强转 const void*	编译警告/错误	先解引用再比较

二、结构体排序与稳定

• 按字段排：比较函数里只比较目标字段。
• 多关键字（先 a 后 b）：cmp 里 a 相等再比 b。
• qsort 不稳定：相等元素相对顺序不保证；需要稳定时自己写归并排序或加序号字段。

三、bsearch：先排后查

int *hit = bsearch(&key, arr, n, sizeof(int), cmp_int);

bsearch 是二分查找，O(log n)，但前提是数组已按同一比较函数升序排好，否则结果未定义。排序 O(n log n) + 多次查询 O(log n) 是"先排序再查找"的经典组合。

四、场景选型

场景	方案
小数组（n<32）	直接插入排序（常数小）
一般排序	qsort（快排，工程默认）
需要稳定	自写归并
一次性查多次	先 qsort 再 bsearch

五、与入门层的衔接

• 排序综合练习，见 排序练习。
• 函数指针比较回调，见 函数指针进阶。
• 结构体数组排序，见 结构体数组。

一句话总结

qsort/bsearch 是 C 的标准排序查找组合：比较函数用"比较再相减"防溢出、bsearch 必须配已排序数组，选型时把规模、稳定性、查询次数一起算进去。

---

本文为骨架文档：核心结构已就位，示例代码与实测数据将在后续批次补齐。