库函数《qsort》的模拟实现
- 前言
- 一、qsort函数
- 二、qsort函数实现思路
- 1. 底层原理
- 2. 函数传参
- 1). 第一个参数
- 2). 第二个参数
- 3). 第三个参数
- 4). 第四个参数
- 三、局部函数实现
- 四、全部代码汇集
- 五、总结
前言
我们在上一篇博客讲解了库函数qsort的使用，今天我为大家带来qsort的模拟实现。上一篇博客这个库函数的阅读链接：一篇文章看懂《qsort》快排的用法
其实有人会问，我明明已经掌握了库函数qsort的使用方法，为何还要去写模拟实现，其实啊，学好一个东西，不仅仅只是会用就可以，如果我们能更深层次的去探索这个函数是怎么实现的，我相信，这其中的乐趣，不一般。。。
仅以此篇文章作为我学习的见证，希望能够各位带来一定的帮助，谢谢。文章若有不妥之处，欢迎指点。这是一个共同进步的平台！！！
一、qsort函数
我们先看看qsort函数的使用：
#include <stdio.h>
#include <stdlib.h>
int cmp_int(const void* e1, const void* e2)
{
//e1-e2，得到的是升序
return *(int*)e1 - *(int*)e2;
}
int main()
{
int arr[10] = { 2,3,1,4,5,6,7,9,8,10 };
int sz = sizeof(arr) / sizeof(arr[0]);
qsort(arr, sz, sizeof(arr[0]), cmp_int);
int i = 0;
for (i = 0; i < sz; i++)
printf("%d ", arr[i]);
return 0;
}
qsort函数的四个参数我们就不过多讲了。大家翻一翻上一篇博客。
二、qsort函数实现思路
1. 底层原理
其实啊，qsort函数，底层原理是 快速排序,只不过我们在使用的时候，被封装成了函数而已。我们写的是从冒泡排序的角度写。
2. 函数传参
qsort(arr, sz, sizeof(arr[0]), cmp_int);
1). 第一个参数
传入的是一个数组，可能大多数人的第一反应就是对应函数的形参用数组指针来接收，我当初自己在写的时候，也是这样想的，当我们越往后面写，发现这个形参用数组指针来接收，并不好用，至于为什么，往下看。
我们在上一篇博客提到过 void* 这个概念，它能接收来自所有类型的值，我们这第一个参数的形参就写成 void* base。
2). 第二个参数
传入的是元素个数，我们再提到一个概念：size_t 返回类型，它是一个无符号整形（unsigned int），我在《C primer plus》书找到了相关的解释，图放在下面：
因为我们传第二个参数时，传的其实就是sizeof的返回值，所有函数形参部分就写 size_t sz。
3). 第三个参数
这第三个参数啊，跟第二个参数是一样的，计算得到的也是sizeof的返回值，也直接写size_t width。（代表一个元素的大小）
4). 第四个参数
这第四个参数是一个函数啊，我们在传参的时候，传的其实是这个函数的地址啊，在my_sort(就是等会我们需要实现的qsort函数)，在my_sort函数里面，我们通过传过来的函数地址（cmp_int）去调用这个（cmp_int）函数,我们就叫回调函数。这里有点绕，仔细品。
既然传过来的是一个函数的地址，对应的，我们就用函数指针去接收，具体的代码看下面：
void my_sort(void* base,
size_t sz,
size_t width,
int (*cmp)(void*, void*));
有的小伙伴就会问函数指针是是什么？
就是用来接收函数的地址，用的指针，具体的原理，大家可以去CSDN查，这里，我们就不多讲了。
局部代码：
void my_sort(void* base, size_t sz, size_t width, int (*cmp)(void*, void*))
{
//函数里面实则还是冒泡排序
int i = 0;
for (i = 0; i < sz; i++)
{
int j = 0;
for (j = 0; j < sz - 1 - i; j++)
{
//进行判断和交换
}
}
}
这就是qsort函数大致的框架，还有一点点小细节问题，处理了就完成了，加油哦。
三、局部函数实现
现在放在我们面前的问题，怎么进行数值的判断和交换。
int arr[10]={2,1,4,5,6,3};
我们以这个数组为例，我们想想，如果我们要排一个升序的数组，只需要我们传递给（cmp_int）函数的两个参数相减为正数，上一篇博客提到了口诀“左减右为升序，反之则降”，即就是e1 - e2 大于0 ,也就是e1>e2了。 注：函数参数（const void* e1，const void* e2）
知道了其中原理，就好实现了呗，if语句判断，如果（cmp_int）函数的放回值大于0，我们就交换一下两个数。
void my_sort(void* base, size_t sz, size_t width, int (*cmp)(void*, void*))
{
//函数里面实则还是冒泡排序
int i = 0;
for (i = 0; i < sz; i++)
{
int j = 0;
for (j = 0; j < sz - 1 - i; j++)
{
//进行判断和交换
if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
{
//此处函数传参的时，并非只需要传递两个需要交换的数据，还有数据的大小，即就是字节数
//例如是整体数据交换，而Swap函数，其实函数里面需要循环4次才行，因为是4个字节的数据嘛
Exch((char*)base + j * width, (char*)base + (j + 1) * width, width);
}
}
}
}
随着j的增加，我们比较的数据也一个个的往后移，特别注意(char*) base + j * width,我们在使用base时，必须先要进行强制类型转换，这样再进行加减操作才可以。因为 base的类型是 void * 类型，没有具体的大小。强制类型转换后，再加上j*width个字节，这样就能找到数组中一个个的元素。
接下来就是函数Exch的实现，这个函数就是交换两个数的位置用的，（exchange）。上面的if语句如果成立，我们就调用函数Exch，去交换两个数的位置，传参的话，跟if语句里面的参数一样的，毋庸置疑。只是我们在传参的时候，还需要传第三个参数width，因为我们调用函数Exch后，函数里面一次交换，只能交换1个字节的内容。有小伙伴就会问，我一次直接交换4个字节的内容，这不是简单的多了嘛。。。。
对于整形数组，一次直接交换4个字节的内容，当然简单了，但是我们需要交换其他数据类型的时候呢，难道还要重新写一遍my_sort吗？？是吧，所以，1个字节慢慢交换，循环width次就行，这样写出来的函数，才是通用的。
Exch函数的实现
void Exch(char* cmp1, char* cmp2, size_t width)
{
int i = 0;
for (i = 0; i < width; i++)
{
char tmp = *cmp1;
*cmp1 = *cmp2;
*cmp2 = tmp;
cmp1++, cmp2++; //逗号表达式，从左到右，依次执行
}
}
这里面就简单多了，就是创建一个临时变量 ，交换数据后，对应的地址加1即可，特别注意一下函数形参部分哦，为什么要写 char*。值得思考哦。
四、全部代码汇集
int cmp_int(const void* e1, const void* e2)
{
return *(int*)e2 - *(int*)e1;
}
void Exch(char* cmp1, char* cmp2, size_t width)
{
int i = 0;
for (i = 0; i < width; i++)
{
char tmp = *cmp1;
*cmp1 = *cmp2;
*cmp2 = tmp;
cmp1++, cmp2++; //逗号表达式，从左到右，依次执行
}
}
void my_sort(void* base, size_t sz, size_t width, int (*cmp)(void*, void*))
{
//函数里面实则还是冒泡排序
int i = 0;
for (i = 0; i < sz; i++)
{
int j = 0;
for (j = 0; j < sz - 1 - i; j++)
{
//进行判断和交换
if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
{
//此处函数传参的时，并非只需要传递两个需要交换的数据，还有数据的大小，即就是字节数
//例如是整体数据交换，而Swap函数，其实函数里面需要循环4次才行，因为是4个字节的数据嘛
Exch((char*)base + j * width, (char*)base + (j + 1) * width, width);
}
}
}
}
int main()
{
int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
int sz = sizeof(arr) / sizeof(arr[0]);
my_sort(arr, sz, sizeof(arr[0]), cmp_int);
int i = 0;
for (i = 0; i < 10; i++)
printf("%d ", arr[i]);
return 0;
}
五、总结
简单的给大家说了一下整体代码的思路，还有细节问题，没能给大家表达清楚，我感到非常遗憾。
特别注意一下冒泡排序里面的逻辑，又特别是里面的if语句，这是整个代码的关键，其他的就没多大的问题，捋清楚了，这些，应该就能懂了，还有就是指针哦，虽然有点难，但是始终相信功夫不负有心人！
如果还有什么不理解的，我们在评论区聊，共同进步。加油！！
下次见！！！
