qsort函数的使用与模拟实现
目录
一、qsort 函数的原型
（一）参数解析
（二）关键：比较函数（compar）的定义
1、参数 p1、p2
2、返回值情况
3、核心操作：类型转换
二、使用示例：排序不同类型的数据
（一）使用qsort函数排序整型数据
（二） 排序字符串数组（字符指针数组）
（三）排序结构体数组（按指定成员排序）
（四）注意事项
1、排序算法
2、稳定性
3、类型转换的关键
4、性能
三、qsort 的模拟实现
（一）关于模拟实现的代码与解析
1、与 qsort 的对应关系
2. 核心设计思路（与 qsort 一致）
（二）关于泛型编程
1、什么是泛型编程
2、void* + 回调函数 是 C 语言泛型的 “专属方案”。
3、C语言与其他语言的泛型编程
qsort 是 C 标准库（stdlib.h）中提供的快速排序函数，可以对任意类型的数组进行排序（整数、字符、结构体等）。它的核心优势是通用性—— 通过函数指针接收自定义的比较规则，从而适配不同类型的数据排序。
一、qsort 函数的原型
void qsort(
void* base, // 待排序数组的首地址
size_t nmemb, // 数组元素的个数
size_t size, // 每个元素的大小（单位：字节）
int (*compare)(const void*, const void*) // 比较函数的指针
);
（一）参数解析
1、base：指向待排序数组的首元素，用 void* 类型（万能指针）接收任意类型的数组地址。
2、nmemb：数组中元素的总个数（size_t 是无符号整数类型）。
3、size：每个元素占用的字节数（如 int 是 4，double 是 8，结构体需用 sizeof 计算）。
4、compar：比较函数的指针，用于定义两个元素的比较规则，返回值决定排序结果。
（二）关键：比较函数（compar）的定义
比较函数是 qsort 的 “灵魂”，它需要我们根据排序的数据类型自行实现，原型固定为：
int compare(const void* p1, const void* p2);
1、参数 p1、p2
指向待比较的两个元素的指针（const void* 表示 “不能修改指向的内容”）。
2、返回值情况
（1）>0：p1 指向的元素 大于 p2 指向的元素，排序时 p1 应放 p2 后面；
（2）=0：两个元素 相等，顺序不变；
（3）<0：p1 指向的元素 小于 p2 指向的元素，排序时 p1 应放 p2 前面。
3、核心操作：类型转换
由于 p1、p2 是 void* 类型，不能直接解引用，必须先转换为实际数据类型的指针，再比较。
//比较 int 类型的示例
//版本一：常规版
int compare_int(const void* p1, const void* p2) {
// 转换为 int* 类型（因为原数组是 int 数组）
const int* a = (const int*)p1;
const int* b = (const int*)p2;
// 返回 *a - *b 表示升序；*b - *a 表示降序
return *a - *b; // 升序排列
//return *b - *a; //降序排序
}
//版本二：简化版
//直接在 return 中完成类型转换和计算
int compare_int(const void* p1, const void* p2) {
return *(const int*)p1 - *(const int*)p2; // 升序排列
}二、使用示例：排序不同类型的数据
★ 使用 qsort 时，每一种需要排序的数据类型，或同类型但排序规则不同（如升序/降序/绝对值、结构体中的同类型数据），都需要单独一个对应的 compare 比较函数，即单独重写一个 compare 函数，这个函数属于回调函数。
回调的核心定义是：将一个函数（回调函数）的指针作为参数传递给另一个函数（调用者函数），并在调用者函数内部通过这个指针调用该函数。
compare 函数是回调函数—— 它由我们定义，但其调用时机和方式由 qsort 决定；
qsort 是调用者函数—— 它接收 compare 函数的指针作为参数（int (*compar)(const void*, const void*)），并在排序过程中（内部）多次调用 compare 函数来比较元素大小。
（一）使用qsort函数排序整型数据
#include
#include
// 比较函数：int 升序
int compare_int(const void* p1, const void* p2) {
const int* a = (const int*)p1;
const int* b = (const int*)p2;
return *a - *b; // 升序（a > b 时返回正数，a 放后面）
}
int main() {
int arr[] = {3, 1, 4, 2, 5};
int n = sizeof(arr) / sizeof(arr[0]);
// 调用 qsort 排序
qsort(
arr, // 数组首地址
n, // 元素个数
sizeof(int), // 每个元素大小（4字节）
compare_int // 比较函数
);
// 打印排序结果
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]); // 输出：1 2 3 4 5
}
return 0;
} （二） 排序字符串数组（字符指针数组）
#include
#include
#include
// 比较函数：字符串按字典序升序（使用 strcmp）
int compare_str(const void* p1, const void* p2) {
// 注意：数组元素是 char*，所以 p1 是 char**类型
const char* const* a = (const char* const*)p1;
const char* const* b = (const char* const*)p2;
// 用 strcmp 比较字符串（返回值符合 compar 函数的要求）
return strcmp(*a, *b);
}
int main() {
char* strs[] = {"banana", "apple", "orange", "grape"};
int n = sizeof(strs) / sizeof(strs[0]);
qsort(strs, n, sizeof(char*), compare_str);
for (int i = 0; i < n; i++) {
printf("%s ", strs[i]); // 输出：apple banana grape orange
}
return 0;
} （三）排序结构体数组（按指定成员排序）
#include
#include
#include
// 定义一个学生结构体
typedef struct {
char name[20];
int age;
} Student;
// 比较函数：按年龄升序
int compare_stu_age(const void* p1, const void* p2) {
const Student* s1 = (const Student*)p1;
const Student* s2 = (const Student*)p2;
return s1->age - s2->age;
}
// 比较函数：按姓名字典序升序
int compare_stu_name(const void* p1, const void* p2) {
const Student* s1 = (const Student*)p1;
const Student* s2 = (const Student*)p2;
return strcmp(s1->name, s2->name);
}
int main() {
Student students[] = {
{"Bob", 20},
{"Alice", 18},
{"Charlie", 19}
};
int n = sizeof(students) / sizeof(students[0]);
// 按年龄排序
qsort(students, n, sizeof(Student), compare_stu_age);
printf("按年龄排序：
");
for (int i = 0; i < n; i++) {
printf("%s(%d) ", students[i].name, students[i].age);
// 输出：Alice(18) Charlie(19) Bob(20)
}
// 按姓名排序
qsort(students, n, sizeof(Student), compare_stu_name);
printf("
按姓名排序：
");
for (int i = 0; i < n; i++) {
printf("%s(%d) ", students[i].name, students[i].age);
// 输出：Alice(18) Bob(20) Charlie(19)
}
return 0;
} （四）注意事项
1、排序算法
qsort 名称来自 “快速排序”，但标准并未强制规定具体实现，部分库可能用其他高效排序算法，如归并排序，但效果都是原地排序，不额外分配大量内存。
2、稳定性
qsort 是不稳定排序，即相等元素的相对顺序可能改变，如果需要稳定排序，需自行实现或使用其他函数。
3、类型转换的关键
比较函数中必须正确转换 void* 为实际类型的指针（如 int*、Student*），否则会访问错误内存导致崩溃；
对于指针数组，如char* strs[ ]，元素是指针；因此 p1 实际是 “指针的指针”，如 char** p1；转换时需注意。其中的一颗“ * ”说明p1是一个指针变量，还有一颗“ * ”与char连接，说明指向的是一个char*类型的数据。
转换时必须保证指针所指向类型的正确！
4、性能
时间复杂度平均为 O(n log n)，适合大部分场景，但对排序稳定性有要求时需谨慎使用。
qsort 是 C 语言中极具通用性的排序工具，其核心设计思想是：用 void* 接收任意类型数组，实现 “通用容器”；用函数指针接收比较规则，通过自定义比较函数适配不同数据类型。
掌握 qsort 的关键是正确实现比较函数 —— 理解如何将 void* 转换为实际类型指针，并定义符合需求的比较逻辑（升序、降序、按结构体成员等）。这也是 “回调函数” 在标准库中最典型的应用之一。
三、qsort 的模拟实现
（一）关于模拟实现的代码与解析
#define _CRT_SECURE_NO_WARNINGS
#include
//用户自定义
int int_cmp(const void* p1, const void* p2)
{
return (*(int*)p1 - *(int*)p2);
}
//内部实现
void swap(void* p1, void* p2, int size)
{
int i = 0;
for (i = 0; i < size; i++)
{
//实现按字节逐个交换，从而兼容任意类型、任意大小的元素交换。
char tmp = *((char*)p1 + i);
*((char*)p1 + i) = *((char*)p2 + i);
*((char*)p2 + i) = tmp;
}
}
//内部实现
void bubble(void* base, int count, int size, int(*cmp)(void*, void*))
{
int i = 0;
int j = 0;
for (i = 0; i < count - 1; i++)
{
for (j = 0; j < count - i - 1; j++)
{
if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0)
{
swap((char*)base + j * size, (char*)base + (j + 1) * size,
size);
}
}
}
}
int main()
{
int arr[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };
int i = 0;
bubble(arr, sizeof(arr) / sizeof(arr[0]), sizeof(int), int_cmp);
for (i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
{
printf("%d ", arr[i]);
}
printf("
");
return 0;
} 这段代码是 qsort 函数的简化模拟实现，核心思想与标准库的 qsort 一致：通过 void* 通用指针 接收任意类型数组，通过 函数指针 接收比较规则，从而实现对任意类型数据的排序。
1、与 qsort 的对应关系
| 组件 | 模拟实现中的代码 | 作用与 qsort 的一致性 |
| 排序函数 | bubble 函数 | 对应 qsort，接收数组地址、元素个数、元素大小、比较函数指针，实现排序逻辑（这里用冒泡排序）。 |
| 通用指针 | void* base 参数 | 同 qsort 的 void* base，通过 char* 强制转换实现按字节访问，适配任意类型。 |
| 比较函数指针 | int(*cmp)(void*, void*) 参数 | 同 qsort 的 compar 参数，接收比较函数指针，由外部定义具体比较逻辑。 |
| 元素交换函数 | swap 函数 | 模拟 qsort 内部的元素交换逻辑，通过按字节拷贝（char* 指针）实现任意大小元素的交换。 |
| 比较函数示例 | int_cmp 函数 | 对应 qsort 的比较函数，定义 int 类型的比较规则（升序）。 |
2. 核心设计思路（与 qsort 一致）
（1）用 void* 实现 “通用容器”
bubble 函数的第一个参数 void* base 可以接收任意类型数组的首地址（int、char、结构体等），通过强制转换为 char* 指针，实现按字节访问（(char*)base + j * size），从而计算任意类型元素的地址偏移量。
（2）用函数指针接收 “比较规则”
通过 int(*cmp)(void*, void*) 参数接收比较函数，将具体的比较逻辑（如 int 升序、结构体按成员比较等）“外包” 给外部函数，使 bubble 函数本身与数据类型解耦。
（3）按单字节交换实现 “通用交换”
swap 函数通过 char* 指针按字节拷贝（size 为每个元素的字节数），可以交换任意类型的元素（无论是 int（4 字节）、double（8 字节）还是结构体（自定义大小））。
这段代码是 qsort 核心思想的简化模拟实现：通过 void* 通用指针、回调函数、按字节操作，实现了 “对任意类型数组排序” 的核心功能，是理解 qsort 工作原理的很好示例。
（二）关于泛型编程
1、什么是泛型编程
这段代码虽然没有使用现代编程语言（如 C++、Java）中的泛型语法，如模板、泛型类，但本质上体现了泛型编程的核心思想—— “编写与数据类型无关的通用代码，能处理多种类型的数据”，即一次编写，多处复用。
2、void* + 回调函数 是 C 语言泛型的 “专属方案”。
void* 指针：负责 “兼容任意类型”—— 它可以接收任意数据的地址（int、结构体、指针等），通过强制转换，如转 char* 按字节操作，实现对不同类型数据的访问；
回调函数：负责 “接收类型的相关逻辑”—— 将与具体类型绑定的操作，如比较、打印、自定义处理，通过函数指针传递给通用代码，让通用逻辑（如排序、遍历）与类型解耦。
这正是 qsort 模拟实现的设计思路：
① void* base 接收任意数组地址（泛型容器）；② int (*cmp)(void*, void*) 接收比较函数（接收类型相关逻辑）；③ swap 用 char* 按字节操作（通用交换）。
3、C语言与其他语言的泛型编程
仅在 C 语言中：由于缺乏原生泛型支持，void*（兼容任意类型）+ 回调函数（注入类型逻辑）是实现泛型编程的 “标配”，是一种 “手动实现的泛型”；
在其他语言中：泛型有更原生、更安全的实现方式（模板、<> 泛型等），void*（或类似的无类型指针）和回调函数更多用于特定场景（如底层交互、动态逻辑注入），而非泛型编程的主流手段。
简单说：void* + 回调函数 是 C 语言为了实现泛型思想而 “不得已” 采用的手动方案，而非所有泛型编程的通用模式。
以上即为 qsort函数的使用与模拟实现 的全部内容，创作不易，麻烦三连支持一下呗~
