C语言没有像C++那样内置sort这样的模板函数，但标准库提供了qsort，配合自己实现的经典排序算法，基本能覆盖日常开发中的所有排序需求。本文先梳理几种常见的排序算法，再详细讲解qsort函数的正确用法，包括比较函数的写法和一些容易出错的地方。
C语言中常见的排序算法有哪些
按照时间复杂度，排序算法大致分为两类：简单排序和高级排序。简单排序包括冒泡排序、选择排序和插入排序，平均时间复杂度都是O(n²)，适合数据量小或者基本有序的场景；高级排序包括快速排序、归并排序、堆排序和希尔排序，平均时间复杂度可以达到O(n log n)，适合大数据量的场合。
冒泡排序是最容易理解的一种，它重复地走访数组，比较相邻两个元素，如果顺序错误就交换。整个过程像水底的气泡一样往上浮。选择排序则是每一轮从未排序部分中挑出最小（或最大）的元素，放到已排序部分的末尾。插入排序把数组分成已排序和未排序两部分，每次从未排序部分取一个元素，在已排序部分中找到合适的位置插入，对于基本有序的数组它的效率非常高，接近O(n)。
三种简单排序的C语言实现
下面给出冒泡排序和插入排序的代码实现，方便对照理解。冒泡排序还可以加一个交换标志，如果某一轮没有发生交换，说明数组已经有序，可以直接退出，这是一个常用的优化手段。
// 冒泡排序（带提前退出优化）
void bubble_sort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int swapped = 0;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
swapped = 1;
}
}
if (!swapped) break; // 本轮没有交换，说明已经有序
}
}
// 插入排序
void insertion_sort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // 后移腾出位置
j--;
}
arr[j + 1] = key;
}
}</code>
这两种排序都属于原地排序，只需要O(1)的额外空间。实际项目中如果数据规模在几百以内，插入排序的性能甚至不输快速排序，因为它的常数因子小，且没有递归调用的开销。这也是很多高级排序算法在分段较小时切换为插入排序的原因。
qsort函数怎么使用
qsort是C标准库void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))。四个参数分别是：数组首地址、元素个数、每个元素的字节数、比较函数的指针。
比较函数是qsort的核心，它接收两个指向待比较元素的指针，返回值规则为：返回负数表示第一个元素应排在前面，返回0表示相等，返回正数表示第一个元素应排在后面。需要注意的是，比较函数接收的是const void *类型指针，必须先强制转换成实际的元素类型指针，再解引用取值。
#include <stdio.h>
#include <stdlib.h>
// 升序比较函数
int cmp_int(const void *a, const void *b) {
int x = *(const int *)a;
int y = *(const int *)b;
return (x > y) - (x < y); // 避免溢出的写法
}
int main() {
int arr[] = {5, 2, 9, 1, 7, 3};
int n = sizeof(arr) / sizeof(arr[0]);
qsort(arr, n, sizeof(int), cmp_int);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}有人喜欢写成return x - y;，这种写法在int存在溢出风险，比如x是很大的正数而y是很大的负数时，相减会溢出，导致排序结果错乱。推荐使用上面代码中(x > y) - (x < y)的写法，永远安全。另外qsort没有返回值，排序结果直接反映在原数组上。
用qsort对结构体和字符串排序
qsort真正的强大之处在于可以排序任意类型的数据，只要比较函数写对即可。比如有一个学生结构体数组，需要按成绩从高到低排序，成绩相同时按学号升序，可以这样写：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
int id;
char name[32];
int 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->score != sb->score) {
return sb->score - sa->score;
}
return sa->id - sb->id;
}
int main() {
Student stus[] = {
{101, "zhang", 85},
{102, "li", 92},
{103, "wang", 85}
};
qsort(stus, 3, sizeof(Student), cmp_student);
for (int i = 0; i < 3; i++) {
printf("%d %s %d\n", stus[i].id, stus[i].name, stus[i].score);
}
return 0;
}对字符串数组排序时要注意一个细节：数组元素是char *指针时，比较函数里拿到的实际上是char **，需要两次解引用才能拿到字符串本身，然后用strcmp比较：
int cmp_str(const void *a, const void *b) {
// 元素本身是char*，所以要先转成char**再解引用
const char *sa = *(const char **)a;
const char *sb = *(const char **)b;
return strcmp(sa, sb);
}这个地方是初学者最容易出错的位置，如果直接把const void *转成const char *再去strcmp，程序很可能直接崩溃，因为指针的层级错了。
使用qsort的注意事项与算法选择建议
第一，标准只规定qsort的行为是排序，具体用什么算法由实现决定，大多数实现采用快速排序的变体，因此qsort不保证稳定，相等元素的相对顺序可能改变。如果业务需要稳定排序，比如排序后还要保留同分学生的原始顺序，就需要改用归并排序或者自己在比较函数中加入额外字段。第二，比较函数必须满足严格弱序，即对相等元素必须返回0，如果写成永远返回正数或负数，可能导致越界访问甚至死循环。第三，传入的size参数必须和元素实际大小一致，排序结构体时写错sizeof会导致整个数组被错误切分。
在算法选择上，数据量小（比如一千以内）时手写插入排序完全够用；数据量大且类型固定时，qsort通用性好但因为有函数指针调用，每次比较都要经过间接跳转，性能比手写的快速排序略慢，对性能极其敏感的场景可以自己实现；如果是嵌入式环境，还要考虑qsort递归实现可能带来的栈空间消耗。理解了这些原理和细节，就能在C语言项目中灵活应对各种排序需求了。