🔎1.qsort函数简介
👁️qsort（）函数是C语言库函数中的一种排序算法，其用到的排序思想是快速排序（quicksort）。它的独特之处在于可以排序任意类型的数组元素（整型、浮点型、字符串和结构体类型）
可以参考一下 cplusplus 中的资料👇
💡1.1.函数原型
void qsort(void* base, size_t num, size_t size, int (*compar)(const void*, const void*)
💡1.2.参数含义
🔴void * base ：指向了待排序数组的第一个元素（待排序数组的首地址）
🔴size_t num ：待排序的元素个数
🔴size_t size ： 每个元素的大小（单位是字节）
🔴int ( * compar ) ( const void * , const void * ) ：是一个函数指针，指向一个函数，这个函数可以比较两个元素的大小
可以再参考一下 cplusplus 中的资料👇
🔎2.比较函数介绍
🔴使用qsort来排序整型数组，这里就由qsort函数的使用者来提供一个比较函数（自定义函数），这个比较函数能够比较2个整数的大小
🔴两个参数表示所要比较元素的地址，之所以参数的接收类型为 void*（无具体类型指针） 是因为它可以接收任意类型的地址，比较元素的类型是不清楚的，只能以 void* 这个万能桶进行接收；const表示指针所指向元素的值无法更改
🔴因为void* 的指针不能解引用操作，所以要对两个元素指针进行强制类型转化为整型指针，再进行解引用获取比较元素的值，最后将两个元素的差值返回。当然也可以根据比较元素的类型将其强制类型转化
🔴compar比较函数的返回值，<0（不进行置换），>0（进行置换），==0（不进行置换）
p1 - p2 升序
p2 - p1 降序
🔎3.比较函数使用案例
💡3.1.整型数组
#include<stdio.h> #include<stdlib.h> //qsort函数的使用者提供这个比较函数 int cmp_int(const void* p1, const void* p2)//void* - 无具体类型指针,所以它可以接收任意类型的地址 { return *(int*)p1 - *(int*)p2; } void print_arr(int arr[], int sz) { int i = 0; for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } printf("\n"); } test1() { int arr[] = { 9,8,7,6,5,4,3,2,1,0 }; int sz = sizeof(arr) / sizeof(arr[0]); //使用qsort来排序整型数组，这里就要提供一个比较函数，这个比较函数能够比较2个整数的大小 //qsort 默认是排成升序的 qsort(arr, sz, sizeof(arr[0]), cmp_int); print_arr(arr, sz); } int main() { test1(); return 0; }
💡3.2.浮点型数组
#include<stdio.h> #include<stdlib.h> //qsort 排序浮点型数据 int cmp_double(const void* p1, const void* p2) { return *(double*)p1 > *(double*)p2 ? 1 : -1; } void print_arr(double arr[], int sz) { int i = 0; for (i = 0; i < sz; i++) { printf("%.2lf ", arr[i]); } printf("\n"); } void test2() { //排列浮点型数据 double arr[] = { 2.0 ,3.5 ,4.8 ,1.2 ,0.9 ,6.6 ,4.4 ,1.6 ,0.3 }; int sz = sizeof(arr) / sizeof(arr[0]); qsort(arr, sz, sizeof(arr[0]), cmp_double); print_arr(arr, sz); } int main() { test2(); return 0; }
🚨此函数返回类型为 int 型，浮点型相减的数字会丢失小数点后的数字从而造成误差。若差值为大于0且小于1，则返回值会被设置为0
💡3.3.结构体类型 - 字符串
#include<stdio.h> #include<stdlib.h> #include<string.h> //qsort 排序结构体数据 struct Stu { char name[20]; int age; }; //按照年龄来比较 int cmp_stu_by_age(const void* p1, const void* p2) { return ((struct Stu*)p1)->age - ((struct Stu*)p2)->age; } //按照名字来比较 int cmp_stu_by_name(const void* p1, const void* p2) { return strcmp(((struct Stu*)p1)->name , ((struct Stu*)p2)->name); } void test3() { struct Stu s[] = { {"zhangsan",30},{"lisi",25},{"wangwu",50}}; int sz = sizeof(s) / sizeof(s[0]); //测试按照年龄来排序 qsort(s,sz,sizeof(s[0]),cmp_stu_by_age); //测试按照名字来排序 qsort(s, sz, sizeof(s[0]), cmp_stu_by_name); } int main() { test3(); return 0; }
🚨按照名字来比较时是比较字符串类型大小，比较字符串类型大小不可用 < ,> , == 进行比较，需要使用 strcmp() 函数进行比较，而比较的结果与 qsort函数所需的返回值相同
使用 qsort函数 不要忘记引头文件 <stdlib.h>‼️
🔎4.利用冒泡排序模拟实现qsort函数的功能
请看源码和注释👇
#include<stdio.h> //qsort函数的使用者提供这个函数 int cmp_int(const void* p1, const void* p2) { return *(int*)p1 - *(int*)p2; } void print_arr(int arr[], int sz) { int i = 0; for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } printf("\n"); } 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++; } } //假设排序为升序 //希望这个bubble_sort函数可以排序任意类型的数据 void bubble_sort(void* base, size_t num, size_t width, int(*cmp)(const void* p1, const void* p2)) { //要确定趟数 size_t i = 0; for (i = 0; i < num - 1; i++) { //一趟冒泡排序的过程 size_t j = 0; for (j = 0; j < num - 1 - i; j++) { //两个相邻的元素比较 //arr[j] arr[j+1] if (cmp((char*)base+j*width,(char*)base+(j + 1)*width) > 0) { //交换 Swap((char*)base + j * width, (char*)base + (j + 1) * width,width); } } } } void test4() { int arr[] = { 3,1,5,2,4,0,9,8,6,7 }; int sz = sizeof(arr) / sizeof(arr[0]); bubble_sort(arr, sz, sizeof(arr[0]), cmp_int); print_arr(arr, sz); } int main() { test4(); return 0; }
![现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int)，已知类QuickSort的quickSort(int[])方法实现了快速排序算法](https://ucc.alicdn.com/b3c447iaqrtq2_20240813_8507e56fc1e0475c88702b767789ed11.png?x-oss-process=image/resize,h_160,m_lfit)