qsort函数的应用以及模拟实现

前言

🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨
🐻推荐专栏: 🍔🍟🌯 c语言进阶
🔑个人信条: 🌵知行合一
🍉本篇简介:>:介绍库函数qsort函数的模拟实现和应用
金句分享:

✨追光的人，终会光芒万丈.✨

一、qsort函数介绍

库函数查询网站(建议使用旧版本查询)

头文件:<stdlib.h>

功能介绍:

使用函数确定顺序，对指向的数组的元素进行排序，每个元素的长度以字节为单位。
此函数使用的排序算法通过调用指定的函数(要自己定义元素比较方式函数传给qsort)并将指向元素的指针作为参数来比较元素.
该函数不返回任何值，而是通过按定义重新排序数组元素来修改指向的数组的内容。

参数介绍:

参数1(void* base)	要排序的数组首地址
参数2(size_t num)	数组中的元素个数。
参数3(size_t size)	数组中每个元素的大小（以字节为单位）。
参数4 ( int (compar)(const void,const void*))	指向数组中元素比较方式的函数指针

二、qsort函数的应用

1.整形数组排序

#include <stdio.h>
#include <stdlib.h>
//注意,由于qsort排序时,并不知道要排序的元素是何种类型,
//所以自定义比较函数的参数都暂时是void*要强制类型转化为对应类型才可以使用.
int int_sort(const void* e1, const void* e2)//自定义整形元素比较方式函数
{return  *(int*)e1 - *(int*)e2;
}
int main()
{int arr1[10] = { 4,6,1,7,8,2,9,10,3,5 };int sz1 = sizeof(arr1) / sizeof(arr1[0]);//计算元素个数qsort(arr1, sz1, sizeof(arr1[0]), int_sort);//整形排序int i = 0;for (i = 0; i < sz1; i++)//整形打印{printf("%d ", arr1[i]);}return 0;
}

运行结果:

1 2 3 4 5 6 7 8 9 10

2.浮点型数组排序

//浮点型数组排序
#include <stdio.h>
#include <stdlib.h>
int double_sort(const void* e1, const void* e2)//浮点型比较
{
//注意要强制转化为相对于的类型,然后解引用比较.int ret = 0;if ((*(double*)e1) - (*(double*)e2) > 0){ret = 1;//前面的数比后面大时返回整数}else ret = -1;//后面数大返回负数;return ret;//两个数相等返回0;
}
int main()
{double arr2[6] = {3.41, 9.45,	4.78,	3.67,	2.9,	7.36 };int sz2 = sizeof(arr2) / sizeof(arr2[0]);//计算数组元素个数qsort(arr2, sz2, sizeof(arr2[0]), double_sort);int i = 0;for (i = 0; i < sz2; i++)//浮点型数组打印{printf("%5.2lf ", arr2[i]);}return 0;
}

运行结果:

2.90 3.41 3.67 4.78 7.36 9.45

3.字符型排序

//字符型数组排序
#include <stdio.h>
#include <stdlib.h>
int char_sort(const void* e1, const void* e2)//字符型比较
{return (*(char*)e1) - (*(char*)e2);
}
int main()
{char arr3[10] = { 'd','g','b','a','e','i','h','c','j','f' };int sz3 = sizeof(arr3) / sizeof(arr3[0]);//计算元素个数qsort(arr3, sz3, sizeof(arr3[0]), char_sort);int i = 0;for (i = 0; i < sz3; i++)//字符型打印{printf("%c ", arr3[i]);}
}

运行结果:

a b c d e f g h i j

4.结构体数组排序

strcmp函数用于比较字符串的,它的比较方式是比较字符的ASCII码值,并不是长度,后续在库函数模拟篇会讲到.

//结构体排序
#include <stdio.h>
#include <stdlib.h>
struct student//创建结构体类型
{char name[15];char sex[3];int age;float stature;
};
typedef struct student sc;//对结构体类型重命名
int sort_age(const void* e1, const void* e2)//按年龄排序
{return (((sc*)e1)->age - ((sc*)e2)->age);
}
int sort_name(const void* e1, const void* e2)//按姓名排序
{return strcmp(((sc*)e1)->name, ((sc*)e2)->name);
}
int main()
{sc arr4[5] = { {"chu jie niu","男",20,1.73f},{"xiao wang","男",19,1.68f},{"qing niao","女",21,1.59f},{"wao shu li","男",16,1.83f},{"peng hu wan","男",15,1.81f} };int sz4 = sizeof(arr4) / sizeof(arr4[0]);//qsort(arr4, sz4, sizeof(arr4[0]), sort_age);qsort(arr4, sz4, sizeof(arr4[0]), sort_name);int i = 0;printf("姓名	    性别   年龄   身高\n");for (i = 0; i < sz4; i++){printf("%-12s %-5s %-5d %-5.2fm\n", arr4[i].name, arr4[i].sex, arr4[i].age, arr4[i].stature);}return 0;
}

运行结果:

姓名        性别   年龄   身高
chu jie niu  男    20    1.73 m
peng hu wan  男    15    1.81 m
qing niao    女    21    1.59 m
wao shu li   男    16    1.83 m
xiao wang    男    19    1.68 m

三、qsort模拟实现(采用冒泡排序模拟)

复习一下冒泡排序吧!

void bubble_sort(int* arr, int sz)//冒泡排序
{int i = 0, j = 0;for (i = 0; i < sz - 1; i++){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[10] = { 4,7,1,8,2,3,9,10,5,6 };int sz = sizeof(arr) / sizeof(arr[0]);//计算元素个数bubble_sort(arr, sz);for (int i = 0; i < sz; i++)//数组打印{printf("%d ",arr[i]);}return 0;
}

qsort模拟实现(采用冒泡排序模拟实现)

第一步:冒泡函数的参数

首先,要修改的是冒泡排序函数的参数.

void bubble_sort(void * arr, size_t num, size_t width, int (cmp)(const void, const void*))

这四个参数的含义上面介绍qsort参数时有介绍.
需要注意的是,qsort函数事先并不知道要传过来的数组是何种类型,所以先用void*接收.

补充知识:

void*可以接收任何类型的变量,但是并不能直接使用,要强制类型转化为对应类型使用.

第二步:比较元素的的方法

if (arr[j] > arr[j + 1])
语句中的arr[j]和arr[j+1]有两点需要注意.
由于事先不知道类型
1.要先将arr强制类型转化为char*,因为一个字节是类型的最小单位,这时width就发挥作用了.

arr[j]转化为 (char*)arr + j * width

arr[j+1]转化为 (char*)arr + (j + 1) * width

2.元素的比较方式不再是单一的相减就可以,这里就用到了自定义函数,元素的比较方式函数.

if (cmp((char*)arr + j * width, (char*)arr + (j + 1) * width) > 0)

第三步:交换函数

对于这样只能实现整形的交换方式,肯定是不行的.

int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;

修改为:用char*类型修改交换

swap(char* e1, char* e2, size_t sz)//交换函数
{//由于qsort函数事先不知道要比较的元素是何种类型,所以用最小单位一个字节来交换.//sz代表元素的所占字节大小int i = 0;char p = 0;for (i = 0; i < sz; i++){p = *(e1 + i);*(e1 + i) = *(e2 + i);*(e2 + i) = p;}
}

最后展示全部代码:

#include <stdio.h>
#include <stdlib.h>
struct student//创建结构体类型
{char name[15];char sex[3];int age;float stature;
};
typedef struct student sc;//对结构体类型重命名
int sort_age(const void* e1, const void* e2)//按年龄排序
{return (((sc*)e1)->age - ((sc*)e2)->age);
}
int sort_name(const void* e1, const void* e2)//按姓名排序
{return strcmp(((sc*)e1)->name, ((sc*)e2)->name);
}
int int_sort(const void* e1, const void* e2)//整形比较
{return  *(int*)e1 - *(int*)e2;
}
swap(char* e1, char* e2, size_t sz)//交换函数
{//由于qsort函数事先不知道要比较的元素是何种类型,所以用最小单位一个字节来交换.//sz代表元素的所占字节大小int i = 0;char p = 0;for (i = 0; i < sz; i++){p = *(e1 + i);*(e1 + i) = *(e2 + i);*(e2 + i) = p;}
}
//最后一个参数是函数指针,指向两个元素的比较方法这个函数
void bubble_sort(void * arr, size_t num, size_t width, int (*cmp)(const void*, const void*))
{int i = 0, j = 0;for (i = 0; i < num-1; i++){for (j = 0; j < num - 1 - i; j++){if (cmp((char*)arr + j * width, (char*)arr + (j + 1) * width) > 0){swap((char*)arr + j * width , (char*)arr + (j + 1) * width,width);}}}
}int main()
{int arr[10] = { 4,7,1,8,2,3,9,10,5,6 };int sz = sizeof(arr) / sizeof(arr[0]);//计算元素个数bubble_sort(arr,sz,sizeof(arr[0]),int_sort);for (int i = 0; i < sz; i++)//数组打印{printf("%d ",arr[i]);}printf("\n");sc arr4[5] = { {"chu jie niu","男",20,1.73f},{"xiao wang","男",19,1.68f},{"qing niao","女",21,1.59f},{"wao shu li","男",16,1.83f},{"peng hu wan","男",15,1.81f} };int sz4 = sizeof(arr4) / sizeof(arr4[0]);qsort(arr4, sz4, sizeof(arr4[0]), sort_age);//qsort(arr4, sz4, sizeof(arr4[0]), sort_name);int i = 0;printf("姓名	    性别   年龄   身高\n");for (i = 0; i < sz4; i++){printf("%-12s %-5s %-5d %-5.2fm\n", arr4[i].name, arr4[i].sex, arr4[i].age, arr4[i].stature);}return 0;
}

运行结果:

1 2 3 4 5 6 7 8 9 10
姓名        性别   年龄   身高
peng hu wan  男    15    1.81 m
wao shu li   男    16    1.83 m
xiao wang    男    19    1.68 m
chu jie niu  男    20    1.73 m
qing niao    女    21    1.59 m

qsort函数用冒泡排序的模拟实现,就讲到这里了,如果文章有错误或者不理解的地方,欢迎私信牛牛,互相交流,互相学习.

最后，如果文章对大家有帮助的话，求一波三连吧！
💗💗💗886