目录一、qosrt 的使用声明返回值规则qsort 的使用排序整型数据排序结构体数据二、qsort 模拟实现冒泡排序存在的问题解决办法1. 改造参数2. 改造比较方法3. 调整交换部分的代码三、qsort 模拟实现完整代码测试排为升序排为降序一、qosrt 的使用✨ 声明头文件stdlib.h and search.h返回值void参数void* base指向待排序数组首元素的指针size_t num数组中的元素总个数size_t width数组中每个元素的大小以字节为单位int (__cdecl *compare )(const void *elem1, const void *elem2 )函数指针指向比较 base 的自定义的比较函数升序elem1 - elem2降序elem2 - elem1返回值规则返回值描述 0elem1 小于 elem2 0两者相等 0elem1 大于 elem2注void* 类型的指针是无具体类型的指针void* 类型的指针可以接收任意类型的地址但是这种类型的指针不能直接解引用也不能直接进行指针运算使用时要强制类型转换 qsort 的使用排序整型数据qsort 内部得到了 cmp_int 的函数地址并且通过地址调用了 cmp_int 函数所以 cmp_int 是回调函数排序结构体数据qsort 能够对任意数据类型进行排序其内部实现基于快速排序算法二、qsort 模拟实现采用冒泡排序算法思想实现一个类似于标准库 qsort 功能的通用排序函数冒泡排序❓ 存在的问题 解决办法1. 改造参数 让函数能够接受任意类型的数据2. 改造比较方法 让函数在排序时能够比较不同类型的数据3. 调整交换部分的代码 让函数能够交换任意类型的数据1. 改造参数为了使函数能够处理任意数据类型可以借鉴 qsort 库函数的设计思路通过 void* 指针来传递不确定类型的数据并同时传入 元素总个数numvoid* 类型的指针可以接收任意类型的地址当传入 base 和 num 两个参数时可以确定 待排序数组的起始地址 和 待排序数组的元素数量但无法得知每个元素的具体大小不知道每个元素的大小就无法定位下一个元素的起始位置所以要确定每个元素的大小因此增加一个参数元素的大小width2. 改造比较方法将比较方法写成固定的是不合适的这样只能使用单一的比较方式所以将比较方法作为参数传递进来库函数 qsort 的第四个参数比较函数的返回值用于确定两个元素之间的大小关系compare 指针指向的函数的参数两个待比较元素的地址同样由于无法确定两个比较元素的类型因此形参类型是 void*使用 const 修饰表明该函数仅用于比较操作不会修改元素内容比较的思路通过传过来的比较方法 compare 函数确定两个元素之间的大小关系但调用compare 函数前必须先拿到相邻两个元素的地址因此在函数内部需要定位每个元素的在数组中的起始位置因为不知道元素的具体类型所以需要计算地址1. 将 base 强制类型转换为 char* void* 不能直接进行指针运算以字节为单位进行地址定位2. 用 数组下标 * 元素大小width来精确跳过一个元素的大小从而找到第 j 个元素的起始位置因为数组元素在内存中是连续存放的每个元素占 width 字节所以第 j 个元素的起始地址 (char*)base j * width第 j 1 个元素的起始地址 (char*)base (j 1) * width换而言之跳过 n 个元素就偏移 n 个元素宽度跳过 j 个元素就偏移 j * width 个字节因此强制类型转换为 char* 后按字节偏移就能准确得到待比较元素的地址最后交给 compare 函数判断它们的大小关系3. 调整交换部分的代码函数能够交换任意类型的数据这里封装一个交换函数参数部分包含1. elem1 和 elem2 要交换元素的地址因为在定位每个元素的起始地址时已将 void* 类型的基地址base转换为了 char* 型指针进行偏移运算因此交换函数的形参也直接用 char* 进行接收2. width 元素大小在调用函数时必须知道一个元素在内存中占据多少个字节因为要交换元素的指针是 char* 类型char* 按字节偏移交换时逐字节进行交换总共交换 width 对字节以此保证两个元素的内容完全互换例如逐字节交换 1 和 2 ⚡代码实现三、qsort 模拟实现完整代码void Swap(char* elem1, char* elem2, size_t width) { for (size_t i 0; i width; i) { char tmp elem1[i]; elem1[i] elem2[i]; elem2[i] tmp; } } void my_qsort(void* base, size_t num, size_t width, int(*compare)(const void* elem1, const void* elem2)) { int i 0; for (i 0; i num - 1; i) { int j 0; for (j 0; j num - 1 - i; j) { if (compare((char*)base (j * width), (char*)base ((j 1) * width))0) { Swap((char*)base (j * width), (char*)base ((j 1) * width), width); } } } }测试排为升序排为降序“学习一门新编程语言的唯一途径就是用它写程序。”——《C 程序设计语言》Brian W. Kernighan, Dennis M. Ritchie