c语言qsort函数如何自定义比较规则？

qsort 是 C 标准库 <stdlib.h> 中提供的一个快速排序函数，它非常强大，因为它可以对任何类型的数据进行排序，而不仅仅是整数，这种通用性是通过函数指针实现的。

为什么使用 qsort？

qsort 相比我们自己实现的排序算法有几个显著的优点：

1. 高效：qsort 通常使用快速排序算法实现，平均时间复杂度为 O(n log n),对于大规模数据的排序非常高效。
2. 通用：它可以排序任何数据类型，包括 int、float、double、char,甚至是自定义的结构体。
3. 方便：它是标准库的一部分，无需自己编写复杂的排序逻辑,只需提供一个比较规则即可。

函数原型

qsort 的原型定义在 <stdlib.h> 头文件中：

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

这个函数看起来有点复杂,我们来逐个解析它的参数：

核心部分：比较函数 compar

qsort 的工作完全依赖于你提供的 compar 函数，这个函数由你来实现,它的作用是比较数组中的两个元素。

比较函数的规则：

compar 函数接收两个参数，这两个参数都是指向数组元素的 const void* 指针，因为 qsort 不知道你存的是什么类型，所以它只把它们当作字节数据块。在函数内部，你必须将它们强制转换回你实际的数据类型。

函数必须返回一个 int 值,这个值决定了两个元素的相对顺序：

完整示例

下面我们通过几个例子来演示如何使用 qsort。

示例 1：对整数数组进行排序

这是最常见的用法。

#include <stdio.h>
#include <stdlib.h> // 包含 qsort 的头文件
// 比较函数：用于比较两个整数
int compare_ints(const void *a, const void *b) {
    // 将 void* 指针强制转换为 int* 指针，然后解引用获取值
    int arg1 = *(const int*)a;
    int arg2 = *(const int*)b;
    if (arg1 < arg2) return -1;  // a < b，返回负数
    if (arg1 > arg2) return 1;   // a > b，返回正数
    return 0;                    // a == b，返回 0
}
int main() {
    int values[] = { 50, 100, 25, 10, 40 };
    int n = sizeof(values) / sizeof(values[0]);
    // 调用 qsort
    // base: values (数组起始地址)
    // nmemb: n (元素个数)
    // size: sizeof(int) (单个元素大小)
    // compar: compare_ints (比较函数)
    qsort(values, n, sizeof(int), compare_ints);
    printf("排序后的整数数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", values[i]);
    }
    printf("\n");
    return 0;
}

输出：

排序后的整数数组: 10 25 40 50 100

示例 2：对浮点数数组进行排序

原理和整数完全一样,只是类型不同。

#include <stdio.h>
#include <stdlib.h>
// 比较函数：用于比较两个浮点数
int compare_floats(const void *a, const void *b) {
    float arg1 = *(const float*)a;
    float arg2 = *(const float*)b;
    // 使用一个很小的数来处理浮点数精度问题
    if ((arg1 - arg2) < -1e-6) return -1;
    if ((arg1 - arg2) > 1e-6) return 1;
    return 0;
}
int main() {
    float values[] = { 3.14f, 1.5f, 9.8f, 2.2f, 5.5f };
    int n = sizeof(values) / sizeof(values[0]);
    qsort(values, n, sizeof(float), compare_floats);
    printf("排序后的浮点数组: ");
    for (int i = 0; i < n; i++) {
        printf("%.2f ", values[i]);
    }
    printf("\n");
    return 0;
}

输出：

排序后的浮点数组: 1.50 2.20 3.14 5.50 9.80

示例 3：对结构体数组进行排序

qsort 的真正威力在于对复杂结构的排序，假设我们有一个学生结构体,我们想按学生的年龄或成绩进行排序。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 定义学生结构体
struct Student {
    char name[50];
    int age;
    float score;
};
// 比较函数：按年龄升序排序
int compare_by_age(const void *a, const void *b) {
    struct Student *studentA = (struct Student *)a;
    struct Student *studentB = (struct Student *)b;
    return (studentA->age - studentB->age);
}
// 比较函数：按成绩降序排序
int compare_by_score(const void *a, const void *b) {
    struct Student *studentA = (struct Student *)a;
    struct Student *studentB = (struct Student *)b;
    // 如果希望降序，颠倒比较逻辑即可
    if (studentA->score < studentB->score) return 1;
    if (studentA->score > studentB->score) return -1;
    return 0;
}
int main() {
    struct Student students[] = {
        {"Alice", 20, 88.5},
        {"Bob", 22, 92.0},
        {"Charlie", 19, 85.5},
        {"David", 21, 90.0}
    };
    int n = sizeof(students) / sizeof(students[0]);
    // 1. 按年龄排序
    qsort(students, n, sizeof(struct Student), compare_by_age);
    printf("按年龄排序:\n");
    for (int i = 0; i < n; i++) {
        printf("%s, %d, %.1f\n", students[i].name, students[i].age, students[i].score);
    }
    printf("\n");
    // 2. 按成绩排序
    qsort(students, n, sizeof(struct Student), compare_by_score);
    printf("按成绩排序:\n");
    for (int i = 0; i < n; i++) {
        printf("%s, %d, %.1f\n", students[i].name, students[i].age, students[i].score);
    }
    return 0;
}

输出：

按年龄排序:
Charlie, 19, 85.5
Alice, 20, 88.5
David, 21, 90.0
Bob, 22, 92.0
按成绩排序:
Bob, 22, 92.0
David, 21, 90.0
Alice, 20, 88.5
Charlie, 19, 85.5

总结与最佳实践

1. 包含头文件：始终在文件开头包含 #include <stdlib.h>。
2. 编写比较函数：这是最关键的一步，函数签名必须严格匹配 int (*)(const void *, const void *)。
3. 正确进行类型转换：在比较函数内部，将 const void* 参数强制转换为你实际的数据类型指针（如 int*, struct Student*）,然后解引用。
4. 实现比较逻辑：根据升序或降序要求，返回负数、零或正数。
5. 调用 qsort：确保传递的 base, nmemb, size 和 compar 四个参数都是正确的。

qsort 是 C 语言中一个非常经典和实用的工具,掌握它的使用对于进行数据处理和算法实现至关重要。