【C语言】qsort详解——能给万物排序的神奇函数

🦄个人主页:小米里的大麦-CSDN博客

🎏所属专栏:https://blog.csdn.net/huangcancan666/category_12718530.html

⚙️操作环境:Visual Studio 2022

一、引言

二、qsort函数介绍

1.函数原型

2.参数说明

2.1比较函数

3.使用示例

3.1对一维数组进行排序

3.2对结构体进行排序

4.让我们尝试用更简单的方式来说明如何使用 qsort 函数。

步骤 1: 定义比较函数

步骤 2: 调用 qsort 函数

5.进阶

5.1 解释：

1. 参数:

2. 返回值:

2. 实现细节:

5.2 为什么自动排序？

1. 减法操作

2.qsort 排序机制

3. 实现细节

三、模拟实现qsort函数

使用bubble_sort函数

四、总结

五、共勉

一、引言

在C语言中，qsort函数是一个非常强大且灵活的排序工具，它能够处理各种不同类型的数据结构，包括基本类型数组、字符串、二维数组甚至是结构体。本篇文章将详细介绍qsort函数的工作原理以及如何使用它来进行排序。

二、`qsort`函数介绍

qsort函数是C标准库中的一个通用排序函数，它的原型定义在stdlib.h头文件中。qsort函数之所以被称为“快速排序”函数，是因为它通常采用了一种高效的排序算法——快速排序算法来实现排序过程。

来看看qsort - C++ Reference上的介绍：

1.函数原型

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

2.参数说明

base：指向待排序数组的指针。（谁需要排序）
num：数组中元素的数量。（需要排序的数量/有多少数需要排序）
size：数组中每个元素的字节数。（每个元素有多大）
compar：指向一个比较函数的指针，该函数用于确定排序顺序。（比较函数的指针）

2.1比较函数

比较函数compar接受两个void *类型的参数，并返回一个int类型的值。如果第一个参数应该排在第二个参数之前，则返回负数；如果两者相等，则返回0；如果第一个参数应该排在第二个参数之后，则返回正数。

3.使用示例

让我们通过几个例子来看看如何使用qsort函数。

3.1对一维数组进行排序

#include <stdio.h>
#include <stdlib.h>int compar(const void *a, const void *b) {return *(int *)a - *(int *)b;
}int main() {int arr[] = {3, 1, 5, 9, 7, 6, 4, 8, 0, 2};size_t num = sizeof(arr) / sizeof(arr[0]);size_t sz = sizeof(arr[0]);qsort(arr, num, sz, compar);for (int i = 0; i < num; i++) {printf("%d ", arr[i]);}return 0;
}

3.2对结构体进行排序

按年龄排序
#include <stdio.h>
#include <stdlib.h>struct Stu {char name[20];int age;
};int compar_Stu_age(const void *p1, const void *p2) {return ((struct Stu *)p1)->age - ((struct Stu *)p2)->age;
}int main() {struct Stu s[] = {{"zhangsan", 20}, {"lisi", 30}, {"wangmazi", 25}};size_t num = sizeof(s) / sizeof(s[0]);size_t sz = sizeof(s[0]);qsort(s, num, sz, compar_Stu_age);for (int i = 0; i < 3; i++) {printf("%s, %d\n", s[i].name, s[i].age);}return 0;
}

按姓名排序
int compar_Stu_name(const void *p1, const void *p2) {return strcmp(((struct Stu *)p1)->name, ((struct Stu *)p2)->name);
}int main() {struct Stu s[] = {{"zhangsan", 20}, {"lisi", 30}, {"wangmazi", 25}};size_t num = sizeof(s) / sizeof(s[0]);size_t sz = sizeof(s[0]);qsort(s, num, sz, compar_Stu_name);for (int i = 0; i < 3; i++) {printf("%s, %d\n", s[i].name, s[i].age);}return 0;
}

4.让我们尝试用更简单的方式来说明如何使用 `qsort` 函数。

假设我们有一个整数数组，我们想要按升序排序这个数组。首先我们需要定义一个比较函数，然后调用 qsort 函数。

步骤 1: 定义比较函数

比较函数用来告诉 qsort 如何比较数组中的元素。对于整数数组，我们可以这样定义比较函数：

int compare(const void *a, const void *b) {if (*(int *)a < *(int *)b) {return -1;  // a 小于 b} else if (*(int *)a > *(int *)b) {return 1;   // a 大于 b} else {return 0;   // a 等于 b}
}

这里的关键点是，a 和 b 是指向 void 类型的指针，我们需要把它们转换成指向 int 的指针，以便能够访问它们所指向的整数值。

步骤 2: 调用 `qsort` 函数

接下来，我们可以在 main 函数中定义一个整数数组，并调用 qsort 函数对其进行排序。

#include <stdio.h>
#include <stdlib.h>// 比较函数
int compare(const void *a, const void *b) {if (*(int *)a < *(int *)b) {return -1;  // a 小于 b} else if (*(int *)a > *(int *)b) {return 1;   // a 大于 b} else {return 0;   // a 等于 b}
}int main() {int arr[] = {5, 2, 9, 1, 5, 6};int n = sizeof(arr) / sizeof(arr[0]);  // 计算数组元素个数// 调用 qsort 函数qsort(arr, n, sizeof(int), compare);// 输出排序后的数组printf("Sorted array: ");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}

5.进阶

// 定义比较函数
int compare(const void *a, const void *b) {return (*(int *)a - *(int *)b);
}

比较函数通常写成return (*(int *)a - *(int *)b);这种方法适用于整数数组的排序，但如果你需要对其他数据类型进行排序或者需要更复杂的比较逻辑，就需要修改这个函数以适应你的需求。

5.1 解释：

这个函数实现了以下功能：

1. 参数:

const void *a: 指向第一个要比较的元素的指针。
const void *b: 指向第二个要比较的元素的指针。

2. 返回值:

如果 *(int *)a 小于 *(int *)b，则返回一个负数。
如果 *(int *)a 等于 *(int *)b，则返回 0。
如果 *(int *)a 大于 *(int *)b，则返回一个正数。

3. 实现细节:

*(int *)a 和 *(int *)b 分别将 void 指针转换为 int 指针，并解引用这些指针以获取实际的整数值。
*(int *)a - *(int *)b 进行减法运算，得到的结果直接作为函数的返回值。

这种实现方式非常简洁，通过减法操作自动处理了所有三种情况：

如果结果是负数，则 a 应该排在 b 前面。
如果结果是 0，则 a 和 b 相等。
如果结果是正数，则 a 应该排在 b 后面。

5.2 为什么自动排序？

1. 减法操作

当执行 *(int *)a - *(int *)b 时，实际上是在计算两个整数值之间的差。这个差可以是正数、负数或零，这取决于 a 和 b 的相对大小。

如果 *(int *)a < *(int *)b，那么差值将会是一个负数。
如果 *(int *)a == *(int *)b，那么差值将会是零。
如果 *(int *)a > *(int *)b，那么差值将会是一个正数。

2.qsort 排序机制

qsort 函数通过比较函数来确定元素的相对顺序。比较函数需要返回一个整数值来指示两个元素的相对位置关系。具体来说：

如果比较函数返回一个负数，qsort 函数会认为 a 应该排在 b 的前面。
如果比较函数返回零，qsort 函数会认为 a 和 b 的位置无关紧要，因为它们相等或不需要交换。
如果比较函数返回一个正数，qsort 函数会认为 a 应该排在 b 的后面。

3. 实现细节

由于 qsort 函数内部的排序算法（通常是快速排序或其他高效算法）需要知道如何比较两个元素，所以它会调用提供的比较函数，并根据返回值决定如何排列元素。

三、模拟实现`qsort`函数

除了使用标准库中的qsort函数，我们还可以自己模拟实现一个类似的排序函数，比如使用冒泡排序算法。下面是一个简单的冒泡排序实现，它能够对不同的数据类型进行排序。

冒泡排序实现
#include <stdio.h>
#include <stdlib.h>void Swap(char *buf1, char *buf2, int sz) {int i;for (i = 0; i < sz; i++) {char tmp = *buf1;*buf1 = *buf2;*buf2 = tmp;buf1++;buf2++;}
}void bubble_sort(void *base, size_t num, size_t sz, int (*compar)(const void *, const void *)) {size_t i, j;for (i = 0; i < num - 1; i++) {for (j = 0; j < num - 1 - i; j++) {if (compar((char *)base + j * sz, (char *)base + (j + 1) * sz) > 0) {Swap((char *)base + j * sz, (char *)base + (j + 1) * sz, sz);}}}
}