qsort函数排序+冒泡模拟实现

📝本章重点：

1.能够正确的理解qsort函数各个

参数的含义

，并能够正确的使用qsort函数进行各类型排序。
2.重点掌握qsort函数中的参数

cmpar

——自定义比较函数的地址。借此进一步理解回调函数。
3.学习以冒泡排序思想

模拟实现

qsort函数。

文章目录

一、qsort排序函数

1、函数功能特点

//头文件:#include<stdlib.h>voidqsort(void* base,size_t num,size_t size,int(*compar)(constvoid*,constvoid*));

注：因为qsort可以对任意类型数据排序，所以待排数据的起始类型可以是任意类型，C语言中可以用

void*

接收任意类型的地址。

2、函数参数

3、比较函数

qsort之所以可以对任意类型的数据排序正是因为传入的比较函数是相对自定义的：

对于比较函数 int compar(const void *p1,const void *p2)

（1）比较整数：

intcompareMyType(constvoid* p1,constvoid* p2){return*(MyType*)p1 -*(MyType*)p2;}

1、如果compar返回值小于0（< 0），即

*(MyType*)p1 < *(MyType*)p2

那么p1所指向元素会被排在p2所指向元素的前面,也就是升序 。
2、如果compar返回值等于0（= 0），即

*(MyType*)p1 = *(MyType*)p2

那么p1所指向元素与p2所指向元素的顺序不确定。
3、如果compar返回值大于0（> 0），即

*(MyType*)p1 > *(MyType*)p2

那么p1所指向元素会被排在p2所指向元素的后面,也是升序。

所以为了方便理解我们可以简单这样认为：对于qsort函数如果compar函数的返回值<0(不进行置换)，>0(进行置换)，0(不进行置换)。
即：

return *(MyType*)p1 - *(MyType*)p2;

——qsort升序排序

return *(MyType*)p2 - *(MyType*)p1;

——qsort降序排序
对于具体qsort函数内部具体是怎么进行置换或排序的我们不必关心。（内部实现为快排思想）

（2）比较字符串：

intcompareMyType(constvoid* p1,constvoid* p2){returnstrcmp((MyType *) p1,(MyType *) p2);}

同理：

return strcmp((MyType*)p1,(MyType*)p2);

——qsort升序排序

return strcmp((MyType*)p2,(MyType*)p1);

——qsort降序排序

（3）比较结构体

与上述思想类似，比较结构体时需要具体情况具体分析。

2、测试qsort排序

（1）测试qsort函数排序整形

#include<stdio.h>#include<stdlib.h>//输出函数voidprint(int arr[],int sz){int i =0;for(i =0; i < sz; i++){printf("%d ", arr[i]);}}//比较函数intcompar(constvoid* e1,constvoid* e2){return*((int*)e1)-*((int*)e2);//升序//return *((int*)e2) - *((int*)e1);//降序}intmain(){int arr[]={3,5,2,6,8,1,9,0,4,7};int sz =sizeof(arr)/sizeof(arr[0]);//arr-数据起始地址//sz-数据元素个数//sizeof(arr[0])-数据元素的大小//compar-比较函数指针qsort(arr, sz,sizeof(arr[0]), compar);print(arr, sz);return0;}

（2）测试qsort函数排序结构体

📝按年龄排序

#include<stdio.h>#include<stdlib.h>//结构体structstu{char name[20];int age;};//(1)按年龄排序intcompar_struct_age(constvoid* e1,constvoid* e2){return((structstu*)e1)->age -((structstu*)e2)->age;}intmain(){structstu s[]={{"zhangsan",20},{"lisi",55},{"wangwu",40}};int sz =sizeof(s)/sizeof(s[0]);qsort(s, sz,sizeof(s[0]), compar_struct_age);return0;}

📝按名字排序

#include<stdio.h>#include<stdlib.h>//结构体structstu{char name[20];int age;};//(2)按名字排序intcompar_struct_name(constvoid* e1,constvoid* e2){//使用strcmp比较字符串returnstrcmp(((structstu*)e1)->name,((structstu*)e2)->name);}intmain(){structstu s[]={{"zhangsan",20},{"lisi",55},{"wangwu",40}};int sz =sizeof(s)/sizeof(s[0]);qsort(s, sz,sizeof(s[0]), compar_struct_name);return0;}

二、冒泡模拟qusort函数实现

1、实现思路

理解了库函数qsort()的使用后，下面我们来用冒泡排序的思想实现一下qsort函数，首先我们先回忆一下冒泡排序：

voidbubble_sort(int arr[],int sz){int i =0;for(i =0; i < sz -1; i++)//冒泡排序趟数{int j =0;for(j =0; j < sz - i -1; j++)//每趟冒泡排序{//判断和交换if(arr[j]> arr[j +1])//升序//if (arr[j] < arr[j + 1])降序{int tmp = arr[j];
                arr[j]= arr[j +1];
                arr[j +1]= tmp;}}}}

通过冒泡排序的参数部分我们就可以看出

void bubble_sort(int arr[], int sz)

冒泡排序仅支持单一类型的数据排序。想要用冒泡排序模拟实现qsort函数排任意类型数据，我们可以仿照qsort函数参数对冒泡排序进行改进：

voidbubble_sort(void* base,int sz,int width,int(*cmp)(constvoid*e1,constvoid*e2))

下面我们只需要将冒泡排序中的判断和交换部分以qsort思想实现即可。

2、模拟实现

（1）判断部分

判断部分我们需要使用传入的比较函数指针，利用回调函数的机制进行判断，同时仿照qsort函数内部交换思想即：比较函数cmp返回值大于零（

>0

）进行交换：

if(cmp((char*)base + j * width,(char*)base +(j +1)* width)>0){//交换}

注释：已知base的类型为void*，这里将

void*

类型转换为

char*

类型是一步非常巧妙的过程，因为转换之后我们只需分别加上jwidth 和（j+1）width即可找到相邻数据的起始地址，之后在利用回调函数的机制，调用外部定义的cmp比较函数，此时cmp实参为（char*)base+ j * width, (char*)base + (j + 1) * width分别为两相邻数据的起始位置地址，我们已知cmp函数的形参类型为void*，将得到的起始数据位置的指针转换为相应类型的指针再进行比较，即可得到返回值。

（2）交换部分

交换部分我们可以独立出一个交换函数-

swap()

voidswap(char* buf1,char* buf2,int width){int i =0;for(i =0; i < width;i++){char tmp =*buf1;*buf1 =*buf2;*buf2 = tmp;
        buf1++;
        buf2++;}}

判断交换部分
--------------------------------------------------------------------------if(cmp((char*)base + j * width,(char*)base +(j +1)* width)>0){//交换swap((char*)base + j * width,(char*)base +(j +1)* width,width);}--------------------------------------------------------------------------

注释：对于swap函数传入实参，为两相邻数据的起始地址 与
待排数据元素的大小。我们回到qsort函数的定义：qsort函数是对数组元素进行排序。数组的特点即是，连续存放的相同类型数据。对于相同类型的连续数据也就意味着每个数据的大小是相同的，即每个元素占用的字节大小相同。所以根据这样一个特点，我们就可以通过交换相邻数据的每个字节，以达到交换相邻数据的目的。这样我们就有了遍历元素字节排序的思想：

for (i = 0; i < width;i++)

（3）完整代码与测试

//以冒泡模拟实现qsort#include<stdio.h>#include<stdlib.h>//交换函数voidswap(char* buf1,char* buf2,int width){int i =0;for(i =0; i < width;i++){char tmp =*buf1;*buf1 =*buf2;*buf2 = tmp;
        buf1++;
        buf2++;}}//冒泡实现voidbubble_qsort_sort(void* base,int sz,int width,int(*cmp)(constvoid*e1,constvoid*e2)){int i =0;for(i =0; i < sz -1; i++)//趟数{int j =0;for(j =0; j < sz - i -1; j++)//每趟{//判断if(cmp((char*)base + j * width,(char*)base +(j +1)* width)>0){//交换swap((char*)base + j * width,(char*)base +(j +1)* width,width);}}}}

这样我们就完全实现了用冒泡思想模拟实现qsort函数，并且使用规则相同，下面我们可以测试一下：
测试整数

//打印函数voidprint(int arr[],int sz){int i =0;for(i =0; i < sz; i++){printf("%d ", arr[i]);}}//比较函数intcompar(constvoid* e1,constvoid* e2){return*((int*)e1)-*((int*)e2);}intmain(){int arr[]={3,5,2,6,8,1,9,0,4,7};int sz =sizeof(arr)/sizeof(arr[0]);bubble_qsort_sort(arr, sz,sizeof(arr[0]), compar);print(arr, sz);return0;}

同样测试结构体也与库函数qsort结果相同，这里就不在过多测试。

总结

以上就是对qsort函数的理解、应用以及模拟实现。相信通过本章对qsort函数的解剖，你已经对qsort函数有了更深的理解。