【C语言进阶篇】冒泡排序模拟实现——快排函数qsort
🎬 鸽芷咕：个人主页 🔥 个人专栏:《C语言初阶篇》 《C语言进阶篇》
⛺️生活的理想，就是为了理想的生活!
文章目录
- 📋 前言
- 💬 qsort 和 冒泡排序的区别
- 📑 qsort 的特点
- 📑 冒泡排序 的特点
- 💭 如何解决只能排序整形
- 📖（void *）指针讲解
- 📖（void* )类型的指针该如何使用
- ✅ 解决方法
- 💭 如何解决只能排序整形
- 📖 冒泡排序需要改进的地方
- ✅ 改进方法
- ✅ 参数讲解
- 💭 如何解决不同类型的交换问题
- ✅ swap交换函数的实现
- 💬 bubble_sort实现完全体
- 💭 bubble_sort完整代码
- 🌈 测试排序整形数组
- 🌈 测试排序结构体
- 📝全篇总结
📋 前言
🌈hello！ 各位宝子们大家好啊，前面一章讲解了qsor快排函数的使用那么我们是否可以自己实现一下他呢？ ⛳️冒泡排序我们都知道只能排序整形，但是回调函数学完了之后就可以完美解决这个问题，下面就来看看吧！ 📚本期文章收录在《C语言进阶篇》，大家有兴趣可以看看呐！ ⛺️ 欢迎铁汁们 ✔️ 点赞 👍 收藏 ⭐留言 📝！
🔥 注：VS2022 等C语言学习工具都在《学习工具专栏》, 还有各种实用调试技巧有兴趣可以去看看呐！
💬 qsort 和 冒泡排序的区别
📑 qsort 的特点
🔥 注：快排函数qsort的使用博主在《qsort的使用详解》详细讲解过哦，不会可以去看看。
qsort的特点是：
- 可以排序任意类型的数据
- 使用快速排序的思想 quick
📑 冒泡排序 的特点
冒泡排序 的特点:
- 只能排序整形数据
冒泡排序 思想:
- 俩俩相邻的元素进行比较，满足条件就交换
好了这俩种排序的思想和区别我们都明白了！冒泡排序我相信大家都不陌生，那么我们今天的任务就是使用冒泡排序的思想去模拟实现库函数qsort 函数的功能！
- 而这需要解决冒泡排序3个缺陷
- 一、只能排序整形
- 二、不同类型的数据比较方法不一样
- 三、不同类型数据如何交换方法也不一样
💭 如何解决只能排序整形
这个是冒泡排序最主要的问题，那么改如何解决呢？既然是模拟实现qsort 函数那么我们就可以借鉴一下 qsort 函数的方法！
qsort函数里面直接用通用类型指针接收的数据- 而
通用类型指针是不是刚好能解决冒泡排序只能接收整数的问题
📖（void *）指针讲解
void我们都知道是一个空类型的意思，void 就是无类型的指针 ：*
- 无具体类型的指针，可以说他为通用类型指针
- 但是这种类型的指针是不能够直接进行解引用操作的
- 由于类型是空类型所以也不能进行指针运算
- 因为既然他是个空类型那么我们
+ -是该跳过多少字节呢？
📚示例一：
⛳️这里就就可以看出一旦指针类型不同是不可以接收不同类型的地址的！
- 而用
void*类型的指针就不会出现这种情况
📚示例二：
📖（void* )类型的指针该如何使用
⛳️前面说了这种指针既不能直接解引用，又不能进行指针运算那么我们该怎么使用void*类型的指针呢？
- 🌱 其实void*类型的指针在使用的时候需要强制转换一下就好了！
- 🌱 这样这个空指针类型不就有类型了（我们强制转换的类型）
- 🌱 那么指针的运算不也解决了？因为有类型了就可以知道
- 🌱 加一步我们可以跳过多少字节
📑图片展示：
✅ 解决方法
现在我们知道了 qsort 快排函数的参数 和
通用类型指针void* 如何使用那么解决冒泡排序只能排序整形还不简单嘛?
- 既然是模拟实现
qsort那么就先仿着qsort的参数写 - 来实现我们的冒泡排序 bubble_sort
📚 代码演示：
//模拟实现 qsort
void bubble_sort(void* base, //第一个参数的地址
size_t num,//要比较元素的个数
size_t size, //比较元素的大小
int (*cmp)(const void* , const void*) )
//比较函数的地址这里我们就把要模拟实现的函数 bubble_sort 的参数给写好了，由于我们也要排序不同类型的参数所以，肯定是需要元素类型大小
- 从哪里排序的第一个参数地址
- 以及要排序多少个元素
- 和每个元素怎么进行比较
💭 如何解决只能排序整形
大家都知道冒泡排序在比较整数的时候字需要简单的进行比个大小就好了。但是我们这里需要对不同类型进行比较就不能进行以前那种简单的比较方法了！
- 那么该怎么解决呢?这个其实也很简单
qsort - 库函数里面需要我们自己写一个比较函数来进行判断如何比较
- 那么我们也可以使用这种方法，对于不同的数据由使用者来决定如何比较
- 我们只需要调用就好了。
📖 冒泡排序需要改进的地方
✅ 改进方法
📚 代码演示：
这里我们可以怎么改进呢？前面说了对于不同的数据由使用者来决定如何比较！我们只需要写一个回调函数就好了！
- 使用回调函数就可以在这里解决问题
- 一个函数可以调用多种不同的函数
🔥 注: 回调函数的详细讲解和使用实例在这里《回调函数的实战技巧》
void bubble_sort(void* base, size_t num, size_t size, int (*cmp)(const void* , const void*) )
{
int i = 0;
for (i = 0; i < num - 1; i++)
{
int j = 0;
for (j = 0; j < num - 1 - i; j++)
{
if ( cmp((char*)base+j*size, (char*)base +( j +1)* size)>0)
{
int tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
}
}
}
}✅ 参数讲解
cmp((char*)base+jsize, (char)base +( j +1)* size)>0 这个函数调用是如何写出来的呢? 虽然我们的比较函数是由使用者来实现的！但是我们只是可以调用函数，而函数的参数还是需要我们在
bubble_sort里面传出去的。
- 既然要比较就需要 第一个 第二个 俩个相邻的元素
- 而
void* 类型的指针又不能直接使用，我们还要排序不同类型的元素所以类型转换就不能写死 - 把它强转为 (char*) 是最合理的，一个字节！
而我们又知道每个元素的类型大小是多少，这不就和巧妙嘛！(char*)base+j*size char* 指针是每次访问一个字节，那么乘上我们的元素类型大小就刚好可以访问不同类型的元素！
- 假设我们参数是整形数组
- 那么 (char*)base+j*size 就是访问4个字节(char*)base+j*4
- 刚好是一个整形的大小。
💭 如何解决不同类型的交换问题
而冒泡排序以前的交换算法也肯定不可取了，这就需要我们自己构建一种可以交换任意类型的数据了！
✅ swap交换函数的实现
既然是交换那么肯定需要俩个参数，所以
(char*)base+j*size和(char*)base +( j +1)* size)这俩个参数肯定是需要的
- 而我们传过来的参数是强转成
char* 的 - 那么我们是不是可以这样交换
一个字节一个字节的进行交换，诶是不是很神奇。这样是不是也能把俩个元素个相互交换并且内容都不发生改变。
- 因为交换的本质还是一样，只不是以前是一步完成的！
- 我们现在交换了4次，只是次数变多了但结果是一样的！
- 都是把不同字节的内容给交换了！
- 只需要知道要交换元素类型大小是多少，所以我们还需要一个类型大小
size传过来！
📚 代码演示：
//交换函数
void swap(char* p1, char* p2,int size)
{
int i = 0;
for (i = 0; i < size; i++)
{
char tmp = *p1;
*p1 = *p2;
*p2 = tmp;
p1++;
p2++;
}
}💬 bubble_sort实现完全体
好了这下我们冒泡排序的所有缺点都解决了，折现就可以验证一下
bubble_sort冒泡排序模拟实现的qsort在功能上是不是一样的！
💭 bubble_sort完整代码
📚 代码演示：
//交换函数
void swap(char* p1, char* p2,int size)
{
int i = 0;
for (i = 0; i < size; i++)
{
char tmp = *p1;
*p1 = *p2;
*p2 = tmp;
p1++;
p2++;
}
}
//测试 bubble_sort 整数排序
//void qsort(void* base, size_t num, size_t size,
//int (*compar)(const void*, const void*))
void bubble_sort(void* base, size_t num, size_t size, int (*cmp)(const void* , const void*) )
{
int i = 0;
for (i = 0; i < num - 1; i++)
{
int j = 0;
for (j = 0; j < num - 1 - i; j++)
{
if ( cmp((char*)base+j*size, (char*)base +( j +1)* size)>0)
{
swap((char*)base + j * size, (char*)base + (j + 1) * size,size);
}
}
}
}🌈 测试排序整形数组
📚 代码演示：
#include <stdio.h>
#include <string.h>
//交换函数
void swap(char* p1, char* p2,int size)
{
int i = 0;
for (i = 0; i < size; i++)
{
char tmp = *p1;
*p1 = *p2;
*p2 = tmp;
p1++;
p2++;
}
}
//测试 bubble_sort 整数排序
//void qsort(void* base, size_t num, size_t size,
//int (*compar)(const void*, const void*))
void bubble_sort(void* base, size_t num, size_t size, int (*cmp)(const void* , const void*) )
{
int i = 0;
for (i = 0; i < num - 1; i++)
{
int j = 0;
for (j = 0; j < num - 1 - i; 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 int_cmp(const void* p1, const void* p2)
{
return (*(int*)p1) - (*(int*)p2);
}
test1()
{
int arr[10] = { 1,9,5,3,4,2,10,8,7,6 };
int sz = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, sz, sizeof(arr[0]), int_cmp);
//打印函数
}
int main()
{
test1();
return 0;
}🌈 测试排序结构体
📚 代码演示：
#include <stdio.h>
#include <string.h>
struct stu
{
char name[20];
int age;
};
//交换函数
void swap(char* p1, char* p2,int size)
{
int i = 0;
for (i = 0; i < size; i++)
{
char tmp = *p1;
*p1 = *p2;
*p2 = tmp;
p1++;
p2++;
}
}
//测试 bubble_sort 整数排序
//void qsort(void* base, size_t num, size_t size,
//int (*compar)(const void*, const void*))
void bubble_sort(void* base, size_t num, size_t size, int (*cmp)(const void* , const void*) )
{
int i = 0;
for (i = 0; i < num - 1; i++)
{
int j = 0;
for (j = 0; j < num - 1 - i; 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 struct_cmp(const void* p1, const void* p2)
{
return strcmp( ((struct stu*)p1)->name,((struct stu*)p2)->name);
}
//测试排序结构体
void test2()
{
struct stu arr[3] = { {"zhangsan",20},{"lisi",40},{"wangwu",33} };
int sz = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, sz, sizeof(arr[0]), struct_cmp);
}
int main()
{
test2();
return 0;
}📝全篇总结
✅ 归纳：
好了以上就是关于模拟实现qsort 函数的全部讲解了，学会这些你就可以完美的使用回调函数！
qsort函数和冒泡排序的区别
只能排序整形的改进方法
判断部分的改进
交换函数的实现
测试数据
☁️ 以上就全部内容了，本章是对回调函数的应用和提高大家学会了嘛！
看到这里了还不给博主扣个：
⛳️ 点赞☀️收藏 ⭐️ 关注！
💛 💙 💜 ❤️ 💚💓 💗 💕 💞 💘 💖
拜托拜托这个真的很重要！
你们的点赞就是博主更新最大的动力！
有问题可以评论或者私信呢秒回哦。
