设计企业网站内容,制作网站商城,如何自建网站,电子商务网站规划、电子商务网站建设引入
我们在学习排序的时候#xff0c;第一个接触到的应该都是冒泡排序#xff0c;我们先来复习一下冒泡排序的代码#xff0c;来作为一个铺垫和引入。
代码如下#xff1a;
#includestdio.hvoid bubble_sort(int *arr, int sz)
{int i 0;for (i 0; i sz…引入
我们在学习排序的时候第一个接触到的应该都是冒泡排序我们先来复习一下冒泡排序的代码来作为一个铺垫和引入。
代码如下
#includestdio.hvoid bubble_sort(int *arr, int sz)
{int i 0;for (i 0; i sz - 1; i){int j 0;for (j 0; j sz - 1 - i; j){if (arr[j] arr[j 1]){int tmp arr[j];arr[j] arr[j 1];arr[j 1] tmp;}}}
}int main()
{int arr[] { 1,2,3,4,5,6,7,8,9,0 };int sz sizeof(arr) / sizeof(arr[0]);bubble_sort(arr, sz);int i 0;for (i 0; i sz; i){printf(%d , arr[i]);}return 0;
}很简单的一种排序方法但我们可以发现一个问题那就是冒泡排序不够通用它只能用于整型数组的排序如果我要排序float类型或者排序结构体要怎么办呢。
下面我们就来介绍一个比较万能的排序函数qsort函数
简介
先来简单了解一下qsort函数的各个部分
语法格式
它的固定格式如下
int cmp_int(const void* e1, const void* e2)
{}注意他的格式是固定的比如返回值类型必须是int类型形参的类型也是固定的只有返回值的部分是自己编写的也就是说当返回值类型不是int的时候我们需要进行强制类型转换或者手动将其返回值改成int类型 这在下文会详细说明
参数解释
在调用函数时传参格式如下
void qsort(void* base,size_t num,size_t width,int (*cmp)(const void* e1, const* e2)
);可以看一下这张图里面讲解了qsort函数的各个参数分别表示的是什么 base:起始位置,待排序数组的首元素地址 num数组的大小单位是元素待排序数组的元素个数 width元素大小单位是字节待排序数组的单个元素的大小 cmp函数指针比较函数compare function比较两个元素的函数的地址 解释对于不同类型元素的比较的方法是不同的此处就是将两个元素的比较方法写成函数传到qsort函数中然后使用指针cmp进行调用 e1和e2可以简单地认为是要比较的两个元素的地址下面会做补充说明 对void *的解释
先抛出一个问题下面这个代码有什么问题
int main()
{int a 0;int *pa a;char* pc a; return 0;
}问题就是第四行和第五行此处虽然可以存储但会报警告从“int *”
到“char *”的类型不兼容。
那么我们这时就可以使用void *无指针类型来解决这个问题
void* p a;
//void *类型的指针可以接收任意类型的地址此处就可以很好地解释qsort函数的第一个参数void* base
补充
对于void *类型的指针无法进行解引用 因为不知道进行解引用之后要访问几个字节 同理也无法进行无符号型的指针与整数的运算
那么在qsort函数中如何比较e1与e2呢 可以将二者强制转换成所需的类型代码中会提到这一点
返回值
下图是英文版的介绍 对qsort函数返回值的解释 当e1e2,返回值小于0 当e1e2返回值等于0 当e1e2 返回值大于0 提示所以可以利用这个规律将不是int类型的返回值手动变成int型下文float类型那里会详细说明
使用
此处我们举三个例子分别是int、float和结构体类型变量的比较
int类型
明确需要
我们需要三个函数main函数调用test函数test函数调用qsort函数、打印最终结果和cmp_int函数提供元素的比较方法
test函数
1.创建数组 2.计算大小 3.调用qsort函数 4.打印最终结果
cmp_int函数
照着前面的固定格式然后返回值那里就直接用
这里我一写*他就识别成斜体大家直接看下面的代码吧…)
最终代码
#includestdlib.hint cmp_int(const void* e1, const void* e2)
{return *(int*)e1 - *(int*)e2;}void test1()
{int arr[10] { 1,2,3,4,5,6,7,8,9,0 };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]);}printf(\n);
}int main()
{test1();return 0;
}还是比较好理解的就不做过多解释了
float类型
对于cmp_float函数的说明
问题
我们知道cmp_float函数的返回值必须是int类型的但,
*(float*)e1 - *(float*)e2的返回类型是float类型在运行时会报一个警告return”: 从“float”转换到“int”可能丢失数据 此处提供两种解决方法
1.使用if else语句手动判断大小并根据情况分别返回一个负数、0、一个正数 代码如下
if (*(float*)e1 *(float*)e2)
{return 1;
}
else if (*(float*)e1 *(float*)e2)
{return 0;
}
else
{return -1;
}2.使用强制类型转换转换成int类型
最终代码 #includestdlib.hint cmp_float(const void* e1, const void* e2)
{return *(float*)e1 - *(float*)e2;
}void test2()
{float f[] { 9.0, 8.0, 7.0, 6.0 ,5.0 ,4.0 ,3.0, 2.0, 1.0 };int sz sizeof(f) / sizeof(f[0]);qsort(f, sz, sizeof(f[0]), cmp_float);int i 0;for (i 0; i sz; i){printf(%.3f , f[i]);}
}int main()
{test2();return 0;
}
结构体类型
如果我们想要排序结构体类型的变量那就很有意思了我们一步一步来分析
明确需要
main函数、test3函数、cmp_stu函数 下面我们重点解释一下test3函数和cmp_stu函数
test3函数
1.创建结构体类型的数组并初始化 2.求数组元素个数 3.调用qsort函数里面包含了cmp_stu函数的地址即调用cmp_stu函数
cmp_stu函数
照猫画虎
我们按照前面的两个例子写出来的应该是
int cmp_struct(const void* e1, const void* e2)
{return *(struct*)e1 - *(struct*)e2;}但这么写是错误的 因为结构体是复杂对象无法直接用 或 进行比较那么我们就需要确定是用哪个成员去作为比较的标准 再通过-来访问相应的成员
下面给出两个例子此处分别以年龄age作为排序标准和以名字name来排序
cmp_stu_by_age函数
将e1和e2从void* 类型转换成结构体类型指针然后再通过-访问相应的成员 然后直接让二者相减即可此处在强制类型转换时别忘了写上struct就行
int cmp_stu_by_age(const void* e1, const void* e2)
{return ((struct Stu*)e1)-age - ((struct Stu*)e2)-age;}这个函数的实现还是与cmp_int函数有一些相似的
cmp_stu_by_name函数
提示此处比较的是字符串同样不能用 来进行比较 而是要用strcmp函数进行比较包含头文件string.h
int cmp_stu_by_name(const void* e1, const void* e2)
{return strcmp(((struct Stu*)e1)-name, ((struct Stu*)e2)-name);}
最终代码
#includestdlib.hstruct Stu
{char name[40];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)
{return strcmp(((struct Stu*)e1)-name, ((struct Stu*)e2)-name);提示此处比较的是字符串同样不能用 来进行比较而是要用strcmp函数进行比较
}void test3()
{struct Stu s[3] { {zhang, 20},{li, 30},{wang, 40} };int sz sizeof(s) / sizeof(s[0]);qsort(s, sz, sizeof(s[0]), cmp_stu_by_age);
}int main()
{test3();return 0;
}三个例子到这里就介绍结束了其实这样看下来也不是很难理解。 下面我们来学习qsort函数的模拟实现也就是优化bubble_sort函数使它能排序任意类型的元素
模拟实现
引入
此处提出一个问题如果说我不想使用qsort函数我就想使用冒泡函数那我要如何改进它才能达到和qsort函数相同的效果呢
函数调用方面的改进
接收地址
如果说想让冒泡排序函数具有排序任意类型元素的功能那么首先它就应该能接收任意类型元素的地址类似于qsort中的base参数
元素个数
函数需要知道要排序多少个元素所以就需要传入数组的大小类似num参数
元素大小宽度
知道了待排序数组的起始位置和元素个数后我们需要对数组中的元素进行移动操作 那么我们就需要知道元素的大小是什么
简易版框架如下
void bubble_sort(void* base, int sz, int width)
{int i 0;//次数for (i 0; i sz; i){//每次需要比较的元素对数int j 0;for (j 0; j sz - 1 - i; j)//比较两个元素{}}
}疑问1
基本框架搭建好了那我们要如何比较两个元素呢我们又不知道他们的类型
所以我们在传参的时候还需要将两个元素的比较方法函数一并传进bubble_sort函数中也就是第四个参数 首先要传入的肯定是函数的地址 其次我们需要返回一个值来告诉我们比较的结果是什么此处类似qsort函数的返回值 最后对于要比较的两个元素因为要求函数具有通用性所以参数类型就是void *类型 代码如下
void bubble_sort(void* base, int sz, int width, int(*cmp)(void* e1,void* e2) )
{int i 0;//次数for (i 0; i sz; i){//每次需要比较的元素对数int j 0;for (j 0; j sz - 1 - i; j)//比较两个元素{if(cmp()0)//交换if(cmp()0)//交换{}}}}
}疑问2if语句
if(cmp()0)//交换{}我们知道这个语句是比较两个元素那我们怎么找到这俩个元素呢
我们知道base就是首元素的地址
想法1
那么有人想通过加减整数来找到后面的元素这个问题在我前面的文章提到过因为元素是void*类型的不知道元素大小无法与整数进行运算
想法2
那么又有人想将base传换成int*类型再运算不就行了吗 还是不对因为我们不知道传进来的参数究竟是什么类型所以我们不能假定他的类型
想法3
小明这时候提出来我们已经知道了每个元素的大小width那可不可以先把base转换成char*类型再加上每个元素的字节大小width呢
这么做就可以了 因为char*大小是一个字节每次移动width个字节就进入到下一个元素中了
if语句代码如下
if(cmp((char*)base j*width, (char*)base (j1)*width)0)//交换
{}疑问3怎么交换
这里先创建一个swap函数用于两个元素的交换
void Swap(char*buf1, char*buf2)
{}void bubble_sort(void* base, int sz, int width)
{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 (j1)*width)0)//交换{Swap((char*)base j * width, (char*)base (j 1) * width);}}}
}但是我们仔细看Swap函数接收的参数类型是char*一个字节大小如果我这个元素是8个字节类型要怎么交换呢 所以如果按照一个字节一个字节这么交换的方式我们就需要知道要交换的元素的字节大小width以及要交换几次
代码如下
void Swap(char*buf1, char*buf2, int width)
{int i 0;for (i 0; i width; i){char tmp *buf1;*buf1 *buf2;*buf2 tmp;buf1;buf2;}
}
简单实现int类型
完整代码如下
void Swap(char*buf1, char*buf2, int width)
{int i 0;for (i 0; i width; i){char tmp *buf1;*buf1 *buf2;*buf2 tmp;buf1;buf2;}
}void bubble_sort(void* base, int sz, int width, int (*cmp)(void*e1, void*e2))
{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 (j1)*width)0)//交换{Swap((char*)base j * width, (char*)base (j 1) * width, width);}}}
}int cmp_int(const void* e1, const void* e2)
{return *(int*)e1 - *(int*)e2;
}void test4()
{int arr[10] { 1,2,3,4,5,6,7,8,9,0 };int sz sizeof(arr) / sizeof(arr[0]);bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);
}int main()
{test4();return 0;
}想要进行其他类型的比较只需要在调用bubble_sort函数时将第四个参数修改成对应的比较方法即可当然这需要自己构建
小提示 -的优先级高于强制类型转换所以要用()先将强制类型转换括起来先转换再访问
题外话
因为想要使bubble_sort函数具有通用性所以我们需要将不同类型元素的比较方法的函数的地址传进来也就是第四个参数而这种将函数地址传进另一个函数由这个函数去实现调用的方法就称为回调函数大概就是这个意思我这几天在整理指针的知识有时间就写一篇博客。
结语
没想到感觉没怎么写就写了六千多字捂脸 只能再一次感叹C的丰富
文章到这里就结束了希望这篇文章对你有所帮助我们下篇文章见~
