郑州营销型网站制作策划,二级网站内容建设要求,公司注销网站备案申请表,谷歌网站入口大家好#xff01;我是保护小周ღ#xff0c;本期为大家带来的是深度解剖C语言标准库函数 qsort()#xff0c;qsort()函数他可以对任意类型的数据排序#xff0c;博主会详细解释函数使用方法#xff0c;以及使用快速排序的左右指针法模拟实现函数功能#xff0c;这样的排…
大家好我是保护小周ღ本期为大家带来的是深度解剖C语言标准库函数 qsort()qsort()函数他可以对任意类型的数据排序博主会详细解释函数使用方法以及使用快速排序的左右指针法模拟实现函数功能这样的排序确定不来学习一下吗 目录
一、qsort()函数简介
二、qsort() 函数的参数
三、qsort() 函数的使用
3.1 对整型数据排序
3.2 对结构体类型数据排序 四、快速排模拟实现qsort()函数 一、qsort()函数简介
qsort() 函数是C语言标准库提供的排序函数qQuick函数内部是以快速排序的思想实现的那qsort() 函数的意义是什么呢内部居然还使用别的排序的思想。因为常规排序是写死的假如原先是对整型数据的排序现在要对结构体类型的数据排序则需要修改函数参数函数内部数据也要相应的修改。而qsort()函数他可以对任意类型的数据排序比如说可以直接排整型数据也可以排结构体类型的数据甚至是字符串数据通用性极强。这样的排序确定不来学习一下吗 二、qsort() 函数的参数 很明显 qsort()函数具有4个参数接下来博主来解剖一下这些参数代表着什么意思。 1. void * base : 首先来了解一下什么是 void* 这个是无具体类型的指针void * 的指针是非常宽容的可以接收任意类型的数据。常常用来临时存放数据等到需要使用数据时我们必须要强制类型转换成某一具体类型的数据才能对数据进行操作。 对void *pa,接收了一个整型 a 的地址我们对指针pa 进行强制类型转换int*再解引用 pa即可对变量a 进行操作。 void *base 存的就是待排序数据的起始地址不能直接访问。 这个参数是 qsort() 函数能够对任意数据排序的基础。
2. size_t num : 记录待排序数据元素个数。
3. size_t size : 记录待排序数据任意一个元素的所占的字节数元素的大小。
4. int (*compar) (const void* , const void* ) :
这其实是一个函数类型的指针可以用来存储函数的地址然后也提前声明了函数的参数返回值
返回值是 int 类型参数部分是两个 void * 类型的接收。这个函数的作用是来比较两个参数的大小然后返回比较果结怎么比呢 如果是整型数据使两个参数相减返回结果。如果是字符串我们可以使用 strcmp(“字符串”“字符串”);strcmp 函数的返回值也是整型数据这个是根据对应的场景选择比较方式即可得到相应的结果。
这第四个参数需要我们自己设计实现函数的作用就是比较任意两个参数返回一个整型数据就可以利用这个数据来判断两个元素大小所以这是个比较排序。 三、qsort() 函数的使用
qsort()函数包含在 stdlib.h库里所以我在使用前需要申明一下。
3.1 对整型数据排序
#includestdio.h
#includestdlib.h//头文件声明//判断两个元素的大小
int Compar(void const *p1,void const *p2)//无具体类型的指针接收数据使用时强制类型转换。
{//两个整型数据相减即可即可得到三种信息,,return (*(int*)p1 - *(int*)p2) *(-1); //利用乘-1改变符号控制升序还是降序
}//打印
void Print(int *arr,int n)
{for (int i0;in;i){printf(%d ,arr[i]);}
}int main()
{int arr[] { 8,6,4,2,3,7,1,2,3,10,9 };int len sizeof(arr) / sizeof(arr[0]);//记录数组元素个数int size sizeof(arr[0]);//记录某一个元素的大小所占的字节数//库函数qsort(arr, len, size, Compar);//第四个参数直接传函数的地址函数名代表函数的地址由函数指针接收。//打印Print(arr, len);return 0;
} 3.2 对结构体类型数据排序
#includestdio.h
#includestdlib.h
#includestring.htypedef struct Student//定义一个Student类型的结构体
{char name[12]; //姓名int age; //年龄char StuID[8]; //学号
}Student;//typedef,重命名一下简化。//比较任意两个元素的大小。
int CmpSort(const void* p1, const void * p2)
{//return ( ((Student*)p1)-age - ((Student*)p2)-age );//根据年龄来比return (strcmp(((Student*)p1)-name,((Student*)p2)-name));//按照姓名的首字母来比较
}//打印
void Print(Student* ps,int n)
{for (int i0;in;i){printf(%s %d %d\n,ps[i].name,ps[i].age,ps[i].StuID);}
}int main()
{Student student[3] { {张三,18,21933321},{李四,20,21933323},{王老五,19,21933322}};int len sizeof(student) / sizeof(student[0]);//统计Student 类型student数组的元素的个数int size sizeof(student[0]);//统计某一个Student 元素所占的字节数。//库函数qsort(student,len,size,CmpSort);Print(student,len);//打印return 0;
} 四、快速排模拟实现qsort()函数
好了经过以上三节内容的铺垫相信大家应该对 qsort() 函数的用法功能明白了接下来我们就要来模拟实现函数内部。上文说到排序思想是用快速排序的思想。那博主今天就用快速排序——左右指针法来模拟实现。挖坑法有一点复杂下文解释。
老铁如果对快速排序的几种排序思想还有什么不明白的可以学习博主的专栏。文章最后会贴。
什么是左右指针法一张图带你搞定 利用递归来继续分割区间分割后继续单趟排最后实现整体排序排序结束。
算法逻辑弄明白了现在还有一个问题那就是函数内部不知道我们要对什么类型的数据进行排序我们虽然使用 void * 无指定类型的指针来接收数据内部怎么根据数据的类型来进行强制类型转换呢不转换无法处理数据。
大家回忆一下我们qsort()函数是不是有四个参数其中有一个参数就是 某一个元素所占的字节大小。size。
我们是不是可以将 void * 转换成 char * char* 的指针每一次只能访问一个字节的内容。
举个例子 现在访问数据元素的问题解决了那怎么交换数据元素的位置呢
还是建立在访问元素的基础上先找到需要交换的元素的位置再根据 size 的大小一个字节一个字节的交换数据。
//交换数据
void Swap(char* base1, char* base2, int size)
{for (int i 0; i size; i)//按字节转换{char tmp *base1;*base1 *base2;*base2 tmp;base1;base2; }
}这一趟下来两个元素的就实现了交换。
完整版代码
#include stdio.h
#include stdlib.hint Cmp_qsort(void const* p1, void const* p2)//用户输入
{int size1 (*(int*)p1 - *(int*)p2);return size1;
}//交换数据
void Swap(char* base1, char* base2, int size)
{for (int i 0; i size; i)//按字节转换{char tmp *base1;*base1 *base2;*base2 tmp;base1;base2; }
}//模拟实现
void _Quick_qsort(void const* base, int left, int right, int size, int(*Cmp_qsort)(void const* p1, void const* p2))
{if (left right){return;}int begin left;int end right;int key begin;//记录坑位的下标、while (begin end){while (begin end (Cmp_qsort((char*)base key*size, (char*)base end * size) 0))--end;while (begin end (Cmp_qsort((char*)base key*size, (char*)base begin * size) 0))begin;Swap((char*)base begin * size, (char*)baseend*size, size);}Swap((char*)base begin * size, (char*)base key * size, size);_Quick_qsort(base, left, begin - 1, size, Cmp_qsort);_Quick_qsort(base, begin 1, right, size, Cmp_qsort);}//过渡一下
void Quick_qsort(void const* base, int len, int size,int(*Cmp_qsort)(void const *p1,void const *p2))
{_Quick_qsort(base, 0, len - 1, size, Cmp_qsort);//左右区间写入参数
}//打印
void Print(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}
}//快排左右指针法
int main()
{int a[] {6,1,2,10,7,9,9,3,4,5,10,8};int len sizeof(a) / sizeof(a[0]);int size sizeof(a[0]);Quick_qsort(a, len, size,Cmp_qsort);//快速排序模拟实现Print(a, len);//打印return 0;} 这个模拟是争对于顺序结构的数据而链式结构要采用不同的办法。 不采用快排的挖坑发的原因是我们需要一个类型大小的空间存坑值这个时候我们只能根据size一个元素所占的字节数动态开辟一个char *的数组一个字节一个字节的存储。如果光定义指针指向那坑值指针会随着指向地址的元素的变化而变化。 至此C语言的深度解剖 qsort() 函数博主已经分享完了希望对大家有所帮助如有不妥之处欢迎批评指正。 本期收录于博主的专栏——数据排序适用于编程初学者感兴趣的朋友们可以订阅查看其它“经典数据排序”。排序算法_保护小周ღ的博客
感谢每一个观看本篇文章的朋友更多精彩敬请期待保护小周ღ *★,°*:.☆(▽)/$:*.°★*
文章存在借鉴如有侵权请联系修改删除
