当前位置：首页 > news >正文

qsort函数使用及其模拟实现

news 2025/8/19 15:01:17

一、qsort函数简介

参数说明

二、qsort使用示例

1、使用qsort排序整型数据

1. 比较函数的基本要求

2. 为什么使用const void*参数

3. 具体实现解析

关键步骤：

4. 内存视角分析

2、使用qsort排序结构体数据

1. 按年龄比较的函数

工作原理：

返回值含义：

特点：

2. 按姓名比较的函数

工作原理：

返回值含义：

特点：

三、qsort函数的模拟实现

1、比较函数 int_cmp

2、交换函数 _swap

3、冒泡排序函数 bubble_sort

4、主函数 main

关于void*指针的说明

一、qsort函数简介

qsort是C标准库中的一个快速排序函数，位于stdlib.h头文件中。它的原型如下：

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

参数说明

base: 指向要排序数组的第一个元素的指针
nitems: 数组中元素的个数
size: 数组中每个元素的大小（以字节为单位）
compar: 用于比较两个元素的函数指针

二、qsort使用示例

1、使用qsort排序整型数据

#include <stdio.h>
#include <stdlib.h>  // 需要包含stdlib.h以使用qsort// qsort函数的使用者需要实现一个比较函数
int int_cmp(const void *p1, const void *p2)
{return (*(int*)p1 - *(int*)p2);  // 升序排列// 若要降序排列，可以改为 return (*(int*)p2 - *(int*)p1);
}int main()
{int arr[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};int i = 0;int size = sizeof(arr) / sizeof(arr[0]);qsort(arr, size, sizeof(int), int_cmp);for (i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}

1. 比较函数的基本要求

qsort的比较函数需要遵循以下规则：

接受两个const void*参数（指向要比较元素的指针）
返回一个int值表示比较结果：
- 负数：第一个参数小于第二个参数
- 零：两个参数相等
- 正数：第一个参数大于第二个参数

2. 为什么使用`const void*`参数

通用性：void*可以指向任何数据类型，使qsort能处理各种类型的数组
安全性：const修饰确保函数不会修改原始数据
标准化：这是C标准库规定的接口形式

3. 具体实现解析

int int_cmp(const void *p1, const void *p2)
{return (*(int*)p1 - *(int*)p2);  // 升序排列
}

关键步骤：

类型转换：
- (int*)p1：将void指针转换为int指针
- *(int*)p1：解引用获取实际的整数值
比较运算：a - b的结果：
- 若a > b → 结果为正 → 表示a应该在b后面（升序）
- 若a == b → 结果为0 → 表示两者相等
- 若a < b → 结果为负 → 表示a应该在b前面（升序）
升降序控制：
- 升序：return a - b（参数1 - 参数2）
- 降序：return b - a（参数2 - 参数1）

4. 内存视角分析

假设我们有数组[3,1]，比较过程：

qsort传入的是&arr[0]和&arr[1]（void指针）
比较函数内：
- 转换为int指针后解引用得到3和1
- 计算3 - 1 = 2（正数）
- 表示3 > 1，需要交换位置

2、使用qsort排序结构体数据

#include <stdio.h>
#include <stdlib.h>
#include <string.h>  // 需要包含string.h以使用strcmpstruct Stu {        // 学生结构体char name[20];  // 名字int age;        // 年龄
};// 按照年龄来比较
int cmp_stu_by_age(const void *e1, const void *e2)
{return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}// 按照名字来比较
int cmp_stu_by_name(const void *e1, const void *e2)
{// strcmp是库函数，专门用来比较两个字符串的大小return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
}// 按照年龄来排序
void test_age_sort()
{struct Stu s[] = {{"zhangsan", 20}, {"lisi", 30}, {"wangwu", 15}};int sz = sizeof(s) / sizeof(s[0]);qsort(s, sz, sizeof(s[0]), cmp_stu_by_age);// 打印排序结果for (int i = 0; i < sz; i++) {printf("%s %d\n", s[i].name, s[i].age);}
}// 按照名字来排序
void test_name_sort()
{struct Stu s[] = {{"zhangsan", 20}, {"lisi", 30}, {"wangwu", 15}};int sz = sizeof(s) / sizeof(s[0]);qsort(s, sz, sizeof(s[0]), cmp_stu_by_name);// 打印排序结果for (int i = 0; i < sz; i++) {printf("%s %d\n", s[i].name, s[i].age);}
}int main()
{printf("按年龄排序:\n");test_age_sort();printf("\n按姓名排序:\n");test_name_sort();return 0;
}

这段代码展示了如何使用C标准库中的qsort函数对结构体数组进行排序，重点在于两个比较函数cmp_stu_by_age和cmp_stu_by_name的实现。

1. 按年龄比较的函数

int cmp_stu_by_age(const void *e1, const void *e2)
{return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}

工作原理：

参数是两个void*指针，这是qsort函数要求的比较函数格式
将void*指针转换为struct Stu*类型
比较两个学生的年龄字段age
返回两者的差值

返回值含义：

如果第一个学生的年龄小于第二个学生，返回负值
如果两者年龄相等，返回0
如果第一个学生的年龄大于第二个学生，返回正值

特点：

简单直接，适合数值类型的比较
对于整数比较很有效

2. 按姓名比较的函数

int cmp_stu_by_name(const void *e1, const void *e2)
{return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
}

工作原理：

同样接收两个void*指针参数
将指针转换为struct Stu*类型
使用strcmp函数比较两个学生的name字符串（后面到字符串部分会讲解）
直接返回strcmp的结果

返回值含义：

如果第一个名字在字典序中排在第二个名字之前，返回负值
如果两个名字相同，返回0
如果第一个名字在字典序中排在第二个名字之后，返回正值

特点：

使用标准库函数strcmp进行字符串比较
遵循字典序（lexicographical order）比较规则
比较是基于ASCII值的逐个字符比较

三、qsort函数的模拟实现

下面使用回调函数和冒泡排序的方式模拟实现qsort：

#include <stdio.h>
#include <string.h>// 比较函数，用于整型比较
int int_cmp(const void *p1, const void *p2)
{return (*(int*)p1 - *(int*)p2);
}// 交换函数，逐字节交换两个元素
void _swap(void *p1, void *p2, int size)
{for (int i = 0; i < size; i++) {char tmp = *((char*)p1 + i);*((char*)p1 + i) = *((char*)p2 + i);*((char*)p2 + i) = tmp;}
}// 模拟qsort的冒泡排序实现
void bubble_sort(void *base, int count, int size, int(*cmp)(const void*, const void*))
{for (int i = 0; i < count - 1; i++) {for (int j = 0; j < count - i - 1; j++) {// 计算两个要比较元素的地址void *elem1 = (char*)base + j * size;void *elem2 = (char*)base + (j + 1) * size;if (cmp(elem1, elem2) > 0) {  // 如果前一个元素大于后一个元素_swap(elem1, elem2, size); // 交换两个元素}}}
}int main()
{int arr[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};int size = sizeof(arr) / sizeof(arr[0]);bubble_sort(arr, size, sizeof(int), int_cmp);for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}

这段代码实现了一个通用的冒泡排序函数，模仿了C标准库中的qsort函数的行为。下面我将详细解释各个部分：

1、比较函数 `int_cmp`

int int_cmp(const void *p1, const void *p2)
{return (*(int*)p1 - *(int*)p2);
}

这是一个用于比较整数的函数
参数是两个void指针，可以指向任何类型的数据
通过强制类型转换(int*)将指针转换为整型指针，然后解引用获取整数值
返回值为：
- 负数：如果p1指向的值小于p2指向的值
- 零：如果两者相等
- 正数：如果p1指向的值大于p2指向的值

2、交换函数 `_swap`

void _swap(void *p1, void *p2, int size)
{for (int i = 0; i < size; i++) {char tmp = *((char*)p1 + i);*((char*)p1 + i) = *((char*)p2 + i);*((char*)p2 + i) = tmp;}
}

这个函数用于交换两个内存块的内容
参数：
- p1, p2: 要交换的两个内存块的指针
- size: 每个内存块的大小（字节数）
实现方式：
- 将指针转换为char*（因为char是1字节）
- 逐字节交换两个内存块的内容
这种实现方式可以处理任何数据类型

3、冒泡排序函数 `bubble_sort`

void bubble_sort(void *base, int count, int size, int(*cmp)(const void*, const void*))
{for (int i = 0; i < count - 1; i++) {for (int j = 0; j < count - i - 1; j++) {void *elem1 = (char*)base + j * size;void *elem2 = (char*)base + (j + 1) * size;if (cmp(elem1, elem2) > 0) {_swap(elem1, elem2, size);}}}
}

这是一个通用的冒泡排序实现
参数：
- base: 数组的起始地址
- count: 数组中元素的数量
- size: 每个元素的大小（字节数）
- cmp: 比较函数的指针
实现要点：
1. 外层循环控制排序轮数
2. 内层循环比较相邻元素
3. 通过(char*)base + j * size计算元素地址（因为char指针算术运算以字节为单位）
4. 使用用户提供的比较函数来决定是否需要交换
5. 需要交换时调用_swap函数

4、主函数 `main`

int main()
{int arr[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};int size = sizeof(arr) / sizeof(arr[0]);bubble_sort(arr, size, sizeof(int), int_cmp);for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}