• 【进阶C语言】排序函数（qsort）与模拟实现（回调函数的实例）

    本章大致内容目录： 

    1.认识回调函数

    2.排序函数qsort

    3.模拟实现qsort

    回调函数为C语言重要知识点，以函数指针为主要知识；下面介绍回调函数的定义、回调函数的库函数举例即库函数模拟实现。

    一、回调函数

    1.回调函数定义

           回调函数就是一个通过函数指针调用的函数。如果你把函数的指针（地址）作为参数传递给另一个函数，当这个指针被用来调用其所指向的函数时，我们就说这是回调函数。

          回调函数不是由该函数的实现方直接调用，而是在特定的事件或条件发生时由另外的一方调用的，用于对该事件或条件进行响应。
         总结：被函数指针调用的函数

    2.回调函数机制实例

    在进阶指针1的函数指针数组中，完成了计数器的实现，现在我们再用回调函数的方法改进，先看      原代码：

    1. #include
    2. void menu()
    3. {
    4. 	printf("****************************\n");
    5. 	printf("***  1. add      2. sub  ***\n");
    6. 	printf("***  3. mul      4. div  ***\n");
    7. 	printf("***  0. exit             ***\n");
    8. 	printf("****************************\n");
    9. }
    10. //加法
    11. int Add(int x, int y)
    12. {
    13. 	return x + y;
    14. }
    15. //减法
    16. int Sub(int x, int y)
    17. {
    18. 	return x - y;
    19. }
    20. //乘法
    21. int Mul(int x, int y)
    22. {
    23. 	return x * y;
    24. }
    25. //除法
    26. int Div(int x, int y)
    27. {
    28. 	return x / y;
    29. }
    30. int main()
    31. {
    32. 	int input = 0;
    33. 	int x = 0;
    34. 	int y = 0;
    35. 	int ret = 0;
    36. 	do
    37. 	{
    38. 		menu();
    39. 		printf("请选择:>");
    40. 		scanf("%d", &input);
    41. 		switch (input)
    42. 		{
    43. 		case 1:
    44. 			printf("请输入2个操作数:");
    45. 			scanf("%d %d", &x, &y);
    46. 			ret = Add(x, y);
    47. 			printf("ret = %d\n", ret);
    48. 			break;
    49. 		case 2:
    50. 			printf("请输入2个操作数:");
    51. 			scanf("%d %d", &x, &y);
    52. 			ret = Sub(x, y);
    53. 			printf("ret = %d\n", ret);
    54. 			break;
    55. 		case 3:
    56. 			printf("请输入2个操作数:");
    57. 			scanf("%d %d", &x, &y);
    58. 			ret = Mul(x, y);
    59. 			printf("ret = %d\n", ret);
    60. 			break;
    61. 		case 4:
    62. 			printf("请输入2个操作数:");
    63. 			scanf("%d %d", &x, &y);
    64. 			ret = Div(x, y);
    65. 			printf("ret = %d\n", ret);
    66. 			break;
    67. 		case 0:
    68. 			printf("退出计算器\n");
    69. 			break;
    70. 		default:
    71. 			printf("选择错误, 重新选择\n");
    72. 			break;
    73. 		}
    74. 	} while (input);
    75.  
    76. 	return 0;
    77. }

       改进方向：

      可以发现，在case部分，很多代码都是重复的，显得冗余；上文使用函数指针数组将这些重复的包含了起来，实现了简洁的操作。

       接下来，我们使用函数指针的机制再次修改，使其更加简便。

        改进思路：

    第一步：

    第二步：初步改进后的代码

    1. case 1:
    2. 	calc(Add);
    3. 	break;
    4. case 2:
    5. 	calc(Sub);
    6. 	break;
    7. case 3:
    8. 	calc(Mul);
    9. 	break;
    10. case 4:
    11. 	calc(Div);
    12. 	break;
    13. case 0:
    14. 	printf("退出计算器\n");
    15. 	break;
    16. default:
    17. 	printf("选择错误, 重新选择\n");
    18. 	break;

    将每个功能函数的地址传给一个通用的函数。

    第三步：通用函数的实现（利用回调机制）

    1. void calc(int (*pf)(int,int))//用函数指针接收函数地址
    2. {
    3. 	int x = 0;
    4. 	int y = 0;
    5. 	int ret = 0;
    6. 	printf("请输入两个数>:");
    7. 	scanf("%d%d",&x,&y);
    8. 	ret = pf(x,y);//通过函数指针调用
    9. 	printf("%d\n",ret);
    10. }

    执行点：函数指针可以接收函数的地址，并且可以通过函数指针变量可以直接调用函数，被调用的函数称为回调函数。

    第四步：程序运行图解

    完整代码展示：

    1. #include
    2. void menu()
    3. {
    4. 	printf("****************************\n");
    5. 	printf("***  1. add      2. sub  ***\n");
    6. 	printf("***  3. mul      4. div  ***\n");
    7. 	printf("***  0. exit             ***\n");
    8. 	printf("****************************\n");
    9. }
    10. //加法
    11. int Add(int x, int y)
    12. {
    13. 	return x + y;
    14. }
    15. //减法
    16. int Sub(int x, int y)
    17. {
    18. 	return x - y;
    19. }
    20. //乘法
    21. int Mul(int x, int y)
    22. {
    23. 	return x * y;
    24. }
    25. //除法
    26. int Div(int x, int y)
    27. {
    28. 	return x / y;
    29. }
    30. void calc(int (*pf)(int,int))//用函数指针接收函数地址
    31. {
    32. 	int x = 0;
    33. 	int y = 0;
    34. 	int ret = 0;
    35. 	printf("请输入两个数>:");
    36. 	scanf("%d%d",&x,&y);
    37. 	ret = pf(x,y);//通过函数指针调用
    38. 	printf("%d\n",ret);
    39. }
    40. int main()
    41. {
    42. 	int input = 0;
    43. 	
    44. 	do
    45. 	{
    46. 		menu();
    47. 		printf("请选择:>");
    48. 		scanf("%d", &input);
    49. 		switch (input)
    50. 		{
    51. 		case 1:
    52. 			calc(Add);
    53. 			break;
    54. 		case 2:
    55. 			calc(Sub);
    56. 			break;
    57. 		case 3:
    58. 			calc(Mul);
    59. 			break;
    60. 		case 4:
    61. 			calc(Div);
    62. 			break;
    63. 		case 0:
    64. 			printf("退出计算器\n");
    65. 			break;
    66. 		default:
    67. 			printf("选择错误, 重新选择\n");
    68. 			break;
    69. 		}
    70. 	} while (input);
    71.  
    72. 	return 0;
    73. }

     上述就是回调函数的介绍和一个简单的实例，下面库函数的实现也是利用了回调函数的机制。

    二、排序函数qsort

    为了对比出qsort，我们先来重温一遍冒泡排序。

    1.冒泡排序

      将一个数组逆序：

    1. #include
    2. my_bubble(int arr[],int sz)
    3. {
    4. 	int i = 0;
    5. 	for (i=0;i-1;i++)
    6. 	{
    7. 		int j = 0;
    8. 		for (j=0;j-1-i;j++)
    9. 		{
    10. 			if (arr[j]>arr[j+1])
    11. 			{
    12. 				int tmp = arr[j];
    13. 				arr[j] = arr[j + 1];
    14. 				arr[j + 1] = tmp;
    15. 			}
    16. 		}
    17. 	}
    18. }
    19. print_bubble(int arr[],int sz)
    20. {
    21. 	int i = 0;
    22. 	for (i=0;i
    23. 	{
    24. 		printf("%d ",arr[i]);
    25. 	}
    26. 	printf("\n");
    27. }
    28. int main()
    29. {
    30. 	int arr[] = {10,9,8,7,6,5,4,3,2,1};
    31. 	int sz = sizeof(arr) / sizeof(arr[0]);
    32. 	print_bubble(arr,sz);
    33. 	my_bubble(arr,sz);//将数组升序
    34. 	print_bubble(arr,sz);
    35. 	return 0;
    36. }

    上述就是冒泡排序的代码

    由此可知，冒泡排序的局限性，所以我们下面介绍万能排序函数--qsort

    2.qsort的介绍

       函数基础原型：

    需要包含头文件#include 

       qsort功能介绍：

    该函数是一个库函数，可以排序任意数据类型的数据（数组）；底层逻辑采用的是快速排序

       参数介绍：

    前三个参数：

    void* base：待排序数据的第一个元素的地址

    size_t num：待排序数据元素的个数

    size_t size：待排序数组中一个元素的大小，单位是字节

    第四个参数：

    （1）int (*compar)(const void*，const void*)：这是一个函数指针参数，变量为：compar

    （2）compar是一个比较函数，作用是比较两个数据的大小

    compar函数的要求：

    （1）compar函数是需要用户（需要排序的程序员）自己完成的函数

    （2）要求：对两个数进行比较

    第一个参数指向的值>第二个，返回>0的数字

    第一个参数指向的值=第二个，返回=0的数字

    第一个参数指向的值<第二个，返回<0的数字

    （3）函数的返回值类型必须是：int

    （4）两个参数类型必须是：void*；

    目的：可以接收任意类型数据的地址

    3.qsort函数的使用

    将上述的数字逆序

       主函数传参部分：

    1. int my_compar(const void* e1, const void* e2)
    2. {
    3. 	//需要自己完成的比较函数
    4. }
    5. int main()
    6. {
    7. 	int arr[] = { 10,9,8,7,6,5,4,3,2,1 };
    8. 	int sz = sizeof(arr) / sizeof(arr[0]);
    9. 	print_bubble(arr, sz);
    10. 	//可以直接调用库函数进行排序
    11. 	qsort(arr,sz,sizeof(arr[0]),my_compar);
    12. 	print_bubble(arr, sz);
    13. 	return 0;
    14. }

       完成函数部分：

    1. int my_compar(const void* e1, const void* e2)
    2. {
    3. 	//需要自己完成的比较函数
    4. 	return *((int*)e1) - *((int*)e2);
    5. }

    （1）void*可以兼容任意类型的地址；但是不能进行解引用和+\-操作

    （2）根据自己的需要排序的数据类型完成该部分函数，该函数便是回调函数

     整体实现：

    1. #include
    2. #include
    3. print_bubble(int arr[], int sz)
    4. {
    5. 	int i = 0;
    6. 	for (i = 0; i < sz; i++)
    7. 	{
    8. 		printf("%d ", arr[i]);
    9. 	}
    10. 	printf("\n");
    11. }
    12. //排序整形数据
    13. int my_compar(const void* e1, const void* e2)
    14. {
    15. 	return *((int*)e1) - *((int*)e2);
    16. }
    17. int main()
    18. {
    19. 	int arr[] = { 10,9,8,7,6,5,4,3,2,1 };
    20. 	int sz = sizeof(arr) / sizeof(arr[0]);
    21. 	print_bubble(arr, sz);
    22. 	qsort(arr,sz,sizeof(arr[0]),my_compar);
    23. 	print_bubble(arr, sz);
    24. 	return 0;
    25. }

    结果展示：

    排序结构体数据类型

       结构体中的整形数据（年龄）：

    1. #include
    2. #include
    3. struct Stu
    4. {
    5. 	char name[20];
    6. 	int age;
    7. 	int s;
    8. };
    9. print_bubble(struct Stu* arr, int sz)
    10. {
    11. 	int i = 0;
    12. 	for (i = 0; i < sz; i++)
    13. 	{
    14. 		printf("%s,%d ", (arr[i]).name,(arr[i]).age);
    15. 	}
    16. 	printf("\n");
    17. }
    18. //排序结构中的年龄（整形）
    19. int compar_Stu_age(const void* e1,const void* e2)
    20. {
    21. 	return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
    22. }
    23. int main()
    24. {
    25. 	struct Stu arr[] = { {"张三",19},{"李四",22},{"王五",20}};
    26. 	int sz = sizeof(arr) / sizeof(arr[0]);
    27. 	printf("年龄从小到大排序：\n");
    28. 	print_bubble(arr, sz);
    29. 	qsort(arr, sz, sizeof(arr[0]), compar_Stu_age);
    30. 	print_bubble(arr, sz);
    31. 	return 0;
    32. }

    结果展示：

       结构体中字符的排序（名字）：

    1. #include
    2. #include
    3. #include
    4. struct Stu
    5. {
    6. 	char name[20];
    7. 	int age;
    8. 	int s;
    9. };
    10. print_bubble(struct Stu* arr, int sz)
    11. {
    12. 	int i = 0;
    13. 	for (i = 0; i < sz; i++)
    14. 	{
    15. 		printf("%s,%d ", (arr[i]).name, (arr[i]).age);
    16. 	}
    17. 	printf("\n");
    18. }
    19. int compar_Stu_name(const void* e1, const void* e2)
    20. {
    21.     //字符串比较需要用该函数
    22. 	return strcmp(((struct Stu*)e1)->name ,((struct Stu*)e2)->name);
    23. }
    24. int main()
    25. {
    26. 	struct Stu arr[] = { {"张三",19},{"李四",22},{"王五",20} };
    27. 	int sz = sizeof(arr) / sizeof(arr[0]);
    28. 	printf("名字按字典排序：\n");
    29. 	print_bubble(arr, sz);
    30. 	qsort(arr, sz, sizeof(arr[0]), compar_Stu_name);
    31. 	print_bubble(arr, sz);
    32. 	return 0;
    33. }

    结果展示：

    以上就是qsort函数使用的一些例子

    库函数qsort使用步骤：

    三、模拟实现qsort

    模拟思路：底层使用【冒泡排序】的算法模拟实现qsort，使得可以排序任意类型的数据。所以我们在冒泡排序的基础上进行改造。

    1.改造方向

    对比方向：

    2.分部改造 

    （1）改造参数

    1. //改造前的
    2. void bubble_sort(int arr[], int sz)
    3. //改造后的参数写法
    4. void bubble_qsort(void* base,size_t num,size_t size,int (*cmp)(const void* e1,const void* e2))

     第四个参数：是一个函数指针，用来接收函数的地址。该函数是一个比较函数，由使用者撰写，用来比较两个数据的大小，并传参。

     改造后：

    比较函数（cmp_int）:

    1. //用来比较整形数据
    2. int cmp_int(const void* e1,const void* e2)
    3. {
    4. 	return *((int*)e1) - *((int*)e2);
    5. }

    （1）e1是一个指针，存放了一个要比较的元素的地址
             e2是一个指针，存放了一个要比较的元素的地址
    （2）e1指向的元素>e2指向的元素，返回>0的数字
             e1指向的元素==e2指向的元素，返回0
             e1指向的元素

    参数意义：

    （1）void* base：待排序数据的首元素地址

    （2）size_t num：无符号整形，num为待排序数据的个数

    （3）size_t size：无符号整形，待排序数据的一个元素的大小。单位：字节

    （4）cmp：函数指针

    （2）改造“两个数据的比较”

    我们有自己撰写的“比较函数”，所以肯定是直接调用该函数即可。

    1. if(cmp()>0)
    2. //根据返回的结果判断是否需要交换

    问题：比较的是两个相邻的元素，那怎么找到两个相邻元素的地址呢？

    1.void*的指针不可以进行解引用操作和+1或者-1操作

    2.需要将void*强转之后才能进行操作；因为不知道是比较什么数据类型，所以我们可以强转成char*

    处理办法： 

    base的地址就是元素的起始地址

    比较方法： 

    交换两个数据：

    当两个数据完成比较之后，满足条件就要交换

    bubble_qsort函数： 

    1. void bubble_qsort(void* base,size_t num,size_t size,int (*cmp)(const void* e1,const void* e2))
    2. {
    3. 	int i = 0;
    4. 	for (i=0;i-1;i++)
    5. 	{
    6. 		int j = 0;
    7. 		for (j=0;j-1-i;j++)
    8. 		{
    9. 			//冒泡排序的比较
    10. 			//if(arr[j]>arr[j+1])
    11. 			if( cmp((char*)base+j*size,(char*)base+(j+1)*size) >0)
    12. 			{
    13. 				//交换
    14. 				swap((char*)base + j * size, (char*)base + (j + 1) * size,size);
    15. 			}
    16. 		}
    17. 	}
    18. }

     交换部分：

    依旧是将相邻两个数据的起始地址作为交换；并且多了一个参数：size

    交换函数：

    1. void swap(char* buf1,char* buf2,size_t size)
    2. {
    3. 	int i = 0;
    4. 	for (i=0;i
    5. 	{
    6. 		char* tmp = *buf1;
    7. 		*buf1 = *buf2;
    8. 		*buf2 = tmp;
    9. 		buf1++;
    10. 		buf2++;
    11. 	}
    12. }

    分部思路完成

    3.整体思路步骤

    （1）整体代码（交换整形数据）

    1. #include
    2. //模拟内部交换的代码
    3. void swap(char* buf1, char* buf2, size_t size)
    4. {
    5. 	int i = 0;
    6. 	for (i = 0; i < size; i++)
    7. 	{
    8. 		char tmp = *buf1;
    9. 		*buf1 = *buf2;
    10. 		*buf2 = tmp;
    11. 		buf1++;
    12. 		buf2++;
    13. 	}
    14. }
    15. //模拟内部排序的代码
    16. void bubble_qsort(void* base,size_t num,size_t size,int (*cmp)(const void* e1,const void* e2))
    17. {
    18. 	int i = 0;
    19. 	for (i=0;i-1;i++)
    20. 	{
    21. 		int j = 0;
    22. 		for (j=0;j-1-i;j++)
    23. 		{
    24. 			if( cmp((char*)base+j*size,(char*)base+(j+1)*size) >0)
    25. 			{
    26. 				//交换
    27. 				swap((char*)base + j * size, (char*)base + (j + 1) * size,size);
    28. 			}
    29. 		}
    30. 	}
    31. }
    32. //打印函数
    33. void print_bubble(int arr[],int sz)
    34. {
    35. 	int i = 0;
    36. 	for (i=0;i
    37. 	{
    38. 		printf("%d ",arr[i]);
    39. 	}
    40. 	printf("\n");
    41. }
    42. //用来比较整形数据（个人撰写）
    43. int cmp_int(const void* e1,const void* e2)
    44. {
    45. 	return *((int*)e1) - *((int*)e2);
    46. }
    47. int main()
    48. {
    49. 	int arr[] = { 10,9,8,7,6,5,4,3,2,1 };
    50. 	int sz = sizeof(arr) / sizeof(arr[0]);
    51. 	print_bubble(arr,sz);
    52. 	bubble_qsort(arr,sz,sizeof(arr[0]),cmp_int);
    53. 	print_bubble(arr,sz);
    54. 	return 0;
    55. }

    （2）整体思路剖析

    （3）整体步骤

    待排序内容、传参：

    1. int main()
    2. {
    3. 	int arr[] = { 10,9,8,7,6,5,4,3,2,1 };
    4. 	int sz = sizeof(arr) / sizeof(arr[0]);
    5. 	print_bubble(arr,sz);
    6. 	bubble_qsort(arr,sz,sizeof(arr[0]),cmp_int);
    7. 	print_bubble(arr,sz);
    8. 	return 0;
    9. }

    比较函数：

    1. //用来比较整形数据（个人撰写）
    2. int cmp_int(const void* e1,const void* e2)
    3. {
    4. 	return *((int*)e1) - *((int*)e2);
    5. }

    排序函数：

    1. //模拟内部排序的代码
    2. void bubble_qsort(void* base,size_t num,size_t size,int (*cmp)(const void* e1,const void* e2))
    3. {
    4. 	int i = 0;
    5. 	for (i=0;i-1;i++)
    6. 	{
    7. 		int j = 0;
    8. 		for (j=0;j-1-i;j++)
    9. 		{
    10. 			if( cmp((char*)base+j*size,(char*)base+(j+1)*size) >0)
    11. 			{
    12. 				//交换
    13. 				swap((char*)base + j * size, (char*)base + (j + 1) * size,size);
    14. 			}
    15. 		}
    16. 	}
    17. }

    交换函数：

    1. //模拟内部交换的代码
    2. void swap(char* buf1, char* buf2, size_t size)
    3. {
    4. 	int i = 0;
    5. 	for (i = 0; i < size; i++)
    6. 	{
    7. 		char tmp = *buf1;
    8. 		*buf1 = *buf2;
    9. 		*buf2 = tmp;
    10. 		buf1++;
    11. 		buf2++;
    12. 	}
    13. }

    以上qsort函数的模拟已完成。如果需要排序其他的数据类型，只需要修改待排序数据、传参和比较函数即可

  • 相关阅读:
    Android 11 热点(softap)流程分析(二) WifiManager--AIDL
    如何在不安装 Microsoft Office 的情况下生成 Excel 文件？
    3D移动 translate3d
    Spring中的循环依赖解决方案
    2023年9月青少年机器人技术（三级）等级考试试卷-理论综合
    【基于Springboot、Mybatis后端框架开发——招生管理网站（系统）】附源码
    Windows通过ssh免密登录Ubuntu (3)
    什么是IFTMBF运输预定请求?
    Java Heap Space: Understanding and Resolving Memory Issues
    linux oracle 2022年10月份补丁集：11.2.0.4.221018 PSU补丁包已发布，包含 database，ojvm和GI
  • 原文地址：https://blog.csdn.net/2301_77053417/article/details/133000544