👦个人主页：@Weraphael

✍🏻作者简介：目前是C语言学习者

✈️专栏：【C/C++】算法
🐋 希望大家多多支持，咱一起进步！😁
如果文章对你有帮助的话
欢迎评论💬 点赞👍🏻 收藏 📂 加关注😍

前言：

往期我们学习了二分查找、归并排序、快速排序和冒泡排序。今天我们学习qsort函数，qsort函数是C语言库中实现的快速排序算法。并且qsort要求提供一个自己定义的比较函数。比较函数使得qsort通用性更好，qsort函数可以实现对数组、字符串、结构体等结构进行升序或降序排序。闲言少叙，开快车🚝🚝

一、qsort函数简介

二、qsort函数的使用

1、对int类型数组排序

2、对char类型排序

3、对浮点型排序

4、对结构体类型排序

三、模拟实现qsort函数

1、代码详解

2、代码实现之整型排序

3、代码实现之结构体类型排序

四、总结

一、qsort函数简介

对于陌生的库函数，可通过cplusplus网站来了解它

【qsort参数介绍】

【比较函数的返回值】

所以，qsort函数大致的模板为

int compare(const void* p1, const void* p2) //
{return p1 - p2; //返回的是升序return p2 - p1; //返回的是降序   //注：p1和p2的类型根据实际情况写
}int main()
{int arr[] = { 1,3,4,6,7,2,10,8,5,9 };int sz = sizeof(arr) / sizeof(arr[0]);//计算数组元素个数 40 / 4 = 10qsort(arr, sz, sizeof(arr[0]), compare);//arr - 指向要排序的数组的第一个元素的指针。//sz -  由 arr 指向的数组中元素的个数//sizeof(arr[0]) - 数组中每个元素的大小，以字节为单位。//compar - 用来比较两个元素的函数。return 0;
}

Q：为什么compare的形参的两个参数是void*类型？

因为qsort函数可以实现对数组(int)、字符串(char)、结构体(stuct)等类型进行升序或降序排序，而void*是不介意类型的，就像一个“垃圾桶”，任意的类型的地址都能往void*塞，但就是不能对其直接使用（解引用操作，++，--等等）。若想使用，只要进行强制类型转化即可。

二、qsort函数的使用

1、对int类型数组排序

【升序情况】

//升序的情况
#include <stdlib.h>  //使用qsort需要包含头文件
#include <stdio.h>  
int compare_int(const void* p1, const void* p2) 
{return *(int*)p1 - *(int*)p2; //强制类型转化并解引用
}int main()
{int arr[] = { 1,3,4,6,7,2,10,8,5,9 };int sz = sizeof(arr) / sizeof(arr[0]);qsort(arr, sz, sizeof(arr[0]), compare_int);for (int i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}

【程序结果】

【降序情况】

//降序的情况
#include <stdlib.h>  //使用qsort需要包含头文件
#include <stdio.h>  
int compare_int(const void* p1, const void* p2) 
{return *(int*)p2 - *(int*)p1; //强制类型转化并解引用
}int main()
{int arr[] = { 1,3,4,6,7,2,10,8,5,9 };int sz = sizeof(arr) / sizeof(arr[0]);qsort(arr, sz, sizeof(arr[0]), compare_int);for (int i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}

2、对char类型排序

//升序的情况
#include <stdio.h>
#include <stdlib.h>int compare_char(const void* p1, const void* p2) 
{return *(char*)p1 - *(char*)p2; //强制类型转化并解引用
}int main()
{char arr[] = { 'f', 'b','e','a','d','c'};int sz = sizeof(arr) / sizeof(arr[0]);qsort(arr, sz, sizeof(arr[0]), compare_char);for (int i = 0; i < sz; i++){printf("%c ", arr[i]);}return 0;
}

【程序结果】

3、对浮点型排序

#include <stdio.h>
#include <stdlib.h>int compare_double(const void* p1, const void* p2) 
{return (*(double*)p1 > *(double*)p2 ? 1 : -1); //三目操作符
}int main()
{double arr[] = { 3.14,2.6,2.3,1.7};int sz = sizeof(arr) / sizeof(arr[0]);qsort(arr, sz, sizeof(arr[0]), compare_double);for (int i = 0; i < sz; i++){printf("%lf ", arr[i]);}return 0;
}

注意

用qsort对浮点型的一定要用三目运算符，由于浮点数的精度问题，如果是两个很接近的数相减，则可能返回一个接近0的小数，而compare_double的返回值是int型，因此会将这个小数返回0。

4、对结构体类型排序

【按姓名排序】

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Stu
{char name[20];int age;
};int compare_name(const void* p1, const void* p2)
{return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name);
}int main()
{struct Stu s[3] = { {"张三",10},{"李四",30},{"王五",21} };int sz = sizeof(s) / sizeof(s[0]);qsort(s, sz, sizeof(s[0]), compare_name);for (int i = 0; i < sz; i++){printf("%s %d\n", s[i].name, s[i].age);}return 0;
}

【程序结果】

注意

姓名是字符串，比较的是字典序大小，要用strcmp。

比较年龄和比较整型一样，这里就不为大家展示了

三、模拟实现qsort函数

模拟实现qsort函数是要基于冒泡排序实现的（冒泡排序讲解）

【冒泡排序的实现】

#include <stdio.h>
void Sort(int arr[], int sz)
{for (int i = 0; i < sz - 1; i++){for (int 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[] = { 2,6,8,7,6,0,1,5,9,3 };int sz = sizeof(arr) / sizeof(arr[0]);Sort(arr, sz);for (int i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}

现要求改造冒泡排序，使整个函数可以排序任意类型的数组

以整型数组为例

【主函数部分】

#include <stdio.h>
int cmp_int(const void* p1, const void* p2)
{return *(int*)p1 - *(int*)p2;
}int main()
{ int arr[] = { 2,6,8,7,6,0,1,5,9,3 };int sz = sizeof(arr) / sizeof(arr[0]);Sort(arr, sz, sizeof(arr[0]), cmp_int); for (int i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}

【Sort函数部分】

参考qsort函数的参数

void Swap(char* x1, char* x2, int width)
{//因为不知道是什么类型，要一个字节一个字节交换for (int i = 0; i < width; i++){char tmp = *x1;*x1 = *x2;*x2 = tmp;x1++;x2++;}
}//void* base - 要求排序不同类型的数组，void*恰好能接收任意类型
//int sz - 元素个数
//int width - 一个元素的大小
//int (*p)(const void*, const void*)  函数传参函数指针接收
//size_t - 无符号整型void Sort(void* base, size_t sz, size_t width, int (*p)(const void*, const void*))
{for (size_t i = 0; i < sz - 1; i++){for (size_t j = 0; j < sz - 1 - i; j++){//通过函数指针p调用的函数cmp_int,所以这是个回调函数if (p((char*)base + j * width,(char*)base + (j + 1) * width) > 0){//写一个Swap函数来交换Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);}}}
}

【代码详解】

【代码实现之整型排序】

int cmp_int(const void* p1, const void* p2)
{return *(int*)p1 - *(int*)p2;
}void Swap(char* x1, char* x2, int width)
{for (int i = 0; i < width; i++){char tmp = *x1;*x1 = *x2;*x2 = tmp;x1++;x2++;}
}void Sort(void* base, size_t sz, size_t width, int (*p)(const void*, const void*))
{for (size_t i = 0; i < sz - 1; i++){for (size_t j = 0; j < sz - 1 - i; j++){if (p((char*)base + j * width,(char*)base + (j + 1) * width) > 0){Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);}}}
}int main()
{ int arr[] = { 2,6,8,7,6,0,1,5,9,3 };int sz = sizeof(arr) / sizeof(arr[0]);Sort(arr, sz, sizeof(arr[0]), cmp_int); for (int i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}

【程序结果】

【代码实现之结构体类型排序】

以排列姓名为例

struct Stu
{char name[20];int age;
};
int compare_name(const void* p1, const void* p2)
{return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name);
}void Swap(char* x1, char* x2, int width)
{for (int i = 0; i < width; i++){char tmp = *x1;*x1 = *x2;*x2 = tmp;x1++;x2++;}
}void Sort(void* base, size_t sz, size_t width, int (*p)(const void*, const void*))
{for (size_t i = 0; i < sz - 1; i++){for (size_t j = 0; j < sz - 1 - i; j++){if (p((char*)base + j * width,(char*)base + (j + 1) * width) > 0){Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);}}}
}int main()
{ struct Stu s[3] = { {"张三",10},{"李四",30},{"王五",21} };int sz = sizeof(s) / sizeof(s[0]);Sort(s, sz, sizeof(s[0]), compare_name);for (int i = 0; i < sz; i++){printf("%s %d\n", s[i].name,s[i].age);}return 0;
}

【程序结果】