C 语言中的 qsort 排序函数

发表于 更新于 分类于 本文字数： 765 阅读时长 ≈ 3 分钟
C语言中的qsort排序函数，和如何编参数中用于比较的函数指针。

C 语言中的 qsort 函数是一个功能强大的标准库函数，调用它需要包含头文件 <stdlib.h>。

正如它的函数名一样，它的作用是进行排序，而由于在函数内部采用快速排序算法(quick sort)，所以它被命名为”qsort”。

该函数的声明是：

1
void qsort(void *base, size_t num, size_t size, int (*compare)(const void *, const void *));
  • base：通用指针类型，表示要排序的数组，可以是任意类型数组。
  • num：数组中的元素数量，也就是待排序的 base 数组的长度。
  • size：base 数组中每个元素的大小，通常使用 sizeof 运算符得到。
  • compare：函数指针类型，表示该函数需要传入一个 返回值类型是 int，形参列表是 const void *, const void * 的表示比较规则的函数。

比较规则和 compare 函数指针

1
int compare(const void *a, const void *b);

qsort 函数只会进行 升序排序，compare 函数就是用来判断两个元素的大小关系的。

  • 返回值等于 0，则 a == b.
  • 返回值大于 0，则 a > b.
  • 返回值小于 0，则 a < b.

如果我们想升序排序，只需要 a 小于 b 的时候返回负数，a 大于 b 的时候返回正数，a 等于 b 的时候返回零。

降序排序的逻辑和升序相反。当 a 实际上小于 b 的时候返回正数，那么 qsort 就会认为 a 逻辑上大于 b，而 qsort 函数只会进行升序排序，所以 a 作为实际上小的数字，但是因为 a 逻辑上大，所以 a 会排在后面，这就相当于降序排序。

排序基本数据类型的数组

以 int 为例

1
2
3
4
5
6
int my_cmp(const void *a, const void *b){
    // 将 a 和 b 转换成 int* 类型，然后才可以进行比较操作
    const int *num1 = a;
    const int *num2 = (const int*)b;    // 对于 C 语言而言，强转语法可写可不写
    // 后续表示大小规则的逻辑
}

排序自定义结构体数组

假设有一个自定义类型 Student

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct{
    int stu_id;
    char name[25];
    int age;
}Student, Students[1024];

int my_cmp(const void *a, const void *b){
    // 将 a 和 b 转换成 Student* 类型，然后才可以进行比较操作
    const Student *s1 = a;
    const Student *s2 = (const Student*)b;  // 对于 C 语言而言，强转语法可写可不写
    // 后续表示大小规则的逻辑
}

排序 C 风格字符串数组

C 风格字符串本身就是字符指针，所以字符串的指针本身就是二级指针，这一点非常值得注意。

1
2
3
4
5
6
7
8
9
10
int my_cmp(const void *a, const void *b){
    // 将 a 和 b 转换成 char* 类型，然后才可以进行比较操作
    const char *s1 = *(const char **)a; 
    // 强转成二级指针再解引用一次，才能得到 char* 字符串的一级指针
    const char *s2 = *(const char **)b; 
    // 注意：此时的强转语法是不能省略的。
    // 因为通用指针类型是明确不能直接解引用的！！！

    // 后续表示大小规则的逻辑
}