• 深入解析 qsort 函数（下），用冒泡排序模拟实现 qsort 函数

            前言：对于库函数有适当了解的朋友们，对于 qsort 函数想必是有认知的，因为他可以对任意数据类型进行排序的功能属实是有点厉害的，本次分享，笔者就给大家带来 qsort 函数的全面的解读

            本次知识的分享笔者分为上下俩卷文章进行讲解，在本篇文章中，给大家带来 qsort 函数的函数内部构造解析，以及如何通过冒泡排序模拟实现 qsort 的函数功能

    上卷：深入解析 qsort 排序（上），它为什么是万能排序？

    目录

    一.模拟实现函数参数

    二.确定算法大体的框架

    三.实现函数的判断逻辑、

    函数指针部分：

    具体判断方法函数：

    四.交换函数的实现

    代码实现：

    五.完整功能测试

    六.完整代码

    一.模拟实现函数参数

    首先我们打开 cplusplus 官网查看 qsort 的参数要求和含义

    qsort - C++ Reference (cplusplus.com)

    具体参数信息如下 

    •  void* base：待排序数组的第一个元素的地址
    • size_t num：待排序数组的元素个数
    • size_t size：待排序数组中一个元素的大小
    • int (*compar)(const void*, const void*)：函数指针-cmp指向了一个函数，这个函数是用来比较两个元素的，e1和e2中存放的是需要比较的两个元素的地址

    根据上面的定义说明，我们对函数参数进行模拟

    void my_qsort(void* base, size_t num, size_t size, int (*compare)(const void* e1, const void* e2))

    二.确定算法大体的框架

            正如标题所说，笔者这里使用较为容易理解的冒泡排序，当然其他的快速排序，选择排序，堆排序，希尔排序等算法都是可以使用的，笔者这里只是为了方便讲解具体实现流程和细节，所以选择的冒泡排序的算法

             在选择好了使用什么算法进行模拟实现后，我们就需要来设计大体的框架了，首先，我们列出一般冒泡排序的形式，然后在这基础上进行删改

    1. 	for (int i = 0; i < num - 1; i++)
    2. 	{
    3. 		//每一趟
    4. 		for (int j = 0; j < num - i - 1; j++)
    5. 		{
    6. 			//排序：前一个元素大于后一个就进行交换
    7. 			if (arr[j] > arr[j + 1])
    8. 			{
    9. 				int temp = 0;
    10. 				temp = arr[j];
    11. 				arr[j] = arr[j + 1];
    12. 				arr[j + 1] = temp;
    13. 			}
    14. 		}
    15. 	}

    在这里，我们需要修改的地方主要是俩点

    1. 判断部分，考虑到不同数据的复杂类型，判断部分不能再使用这样简单数组的方式进行判断，应该设计成一个函数指针，针对不同的数据类型调用不同的函数来进行不同的判断
    2. 交换部分 ，考虑不同的数据的复杂类型，交换部分也不能使用 int 型的临时变量来进行交换数据，应该设计成对任意数据类型都能交换的方式，也就是对字节直接进行操作，对于不同的数据类型，我们直接对其内存存储的字节进行交换，这样就能达到目的和要求

    三.实现函数的判断逻辑、

    函数指针部分：

            首先，为了实现不同的判断方法，我们要有一个函数指针去调用不同的判断方法，我们根据 qsort 的参数要求设计如下函数指针

    int (*compare)(const void* e1, const void* e2)

            这个函数指针有俩个参数，分别代表着需要判断排序的数据，我们调用的参数的返回值是有要求的，如下图 

    那我们就可以将这个判断逻辑的函数的返回值来作为 if 语句判断依据，实现实例如下

    1. if (compare((char*)base + j * size, (char*)base + (j + 1) * size) > 0)
    2. {
    3.  
    4. }

            这代表着，如果判断函数返回值大于0，那我们就执行交换操作，如果等于0或者小于0就不执行交换操作，那我们实现了函数调用的接口，我们还得具体的实现判断逻辑函数，方便进行调用

    具体判断方法函数：

            根据我们在上卷文章中讲解的判断逻辑和实现方法，我们可以同样试用在这里，具体细节如有不懂可以访问下面的链接

    深入解析 qsort 排序（上），它为什么是万能排序？

    1. //比较函数--整形
    2. int comp_int(const void* e1, const void* e2)
    3. {
    4. 	return *(int*)e1 - *(int*)e2;
    5. }
    6.  
    7. //比较函数--浮点型
    8. int comp_float(const void* a, const void* b)
    9. {
    10. 	return *(float*)b - *(float*)a;
    11. }
    12.  
    13. //比较函数--按照年龄
    14. int comp_age(const void* a, const void* b)
    15. {
    16. 	return ((struct stu*)b)->age - ((struct stu*)a)->age;
    17. }
    18.  
    19. //比较函数--按照姓名
    20. int comp_name(const void* a, const void* b)
    21. {
    22. 	return strcmp(((struct stu*)a)->name, ((struct stu*)b)->name);
    23. }

    四.交换函数的实现

            首先，我们要确定我们要进行交换的对象，对于冒泡排序来说，需要交换的只是前后俩个元素，那我们拿到他们的地址就可以进行交换了，我们具体实现如下

    1. //交换
    2. swap((char*)base + j * size, (char*)base + (j + 1) * size, size);

    这里分别对三个参数进行一下解释：

    1. (char*)base + j * size ：确定要交换的第一个数据的地址
    2. (char*)base + (j + 1) * size ：确定要交换的第二个数据的地址
    3. size ：确定这俩个数据直接隔了多少个字节，方便逐字节进行操作

            对于参数为什么这样设定，有小伙伴可能不理解，下面笔者就以 int 类型举例，我们知道，int 类型占 4 个字节，而 char* 指针解引用可以访问一个字节，而数据在内存中存储的最小字节都是 1 个字节，那我们就可以 通过 char* 指针来逐个访问字节，就像下面这张图一样，我们逐个交换俩个数据中的每一个字节，在交换完成后，我们就相当于把这俩个数字进行了交换 

            在逐个交换字节后，宏观上给我们的感受就是直接交换了我们的数据内容，也就是说我们使用俩个 char* 指针分别访问要交换的俩个在数据，每一次交换一个字节后，指针加一，我们就可以继续访问交换后面的字节，在这里循环往复交换 size 个字节后，这俩个数据就被我们完全交换了

    代码实现：

            注意，在具体写代码的过程中不要非法访问空间，在下方代码的注释部分，笔者对错误代码进行了注释，大家在写过程中一定得注意，在指针访问一些只读区域或者不是我们申请的空间的区域就会出现段错误，就像注释部分的代码，我们定义一个空指针，然后再对这个空指针进行解引用访问赋值的操作就会出现报错

    1. //交换函数
    2. void swap(char* buf1, char* buf2, size_t size)
    3. {
    4. 	//逐个字节进行交换，一共有size个字节
    5. 	for (int i = 0; i < size; i++)
    6. 	{
    7. 		//错误示范
    8. 		//char* temp = 0;
    9. 		//*temp = *buf1;
    10. 		//*buf1 = *buf2;
    11. 		//*buf2 = *temp;
    12. 		//buf1++;
    13. 		//buf2++;
    14. 		
    15. 		//正确示范
    16. 		char temp = *buf1;
    17. 		*buf1 = *buf2;
    18. 		*buf2 = temp;
    19. 		buf1++;
    20. 		buf2++;
    21. 	}
    22. }

    五.完整功能测试

            我们仍然使用在上篇文章中的用例进行测试，观察我们设计的函数能不能完成我们预期的功能，在这里对整形数组，浮点型数组，结构体数组进行测试

    1. int main()
    2. {
    3. 	int arr1[] = { 9,8,7,6,5,4,3,2,1,0 };
    4. 	int sz = sizeof(arr1) / sizeof(arr1[0]);
    5. 	print1(arr1);
    6. 	my_qsort(arr1, sz, sizeof(int), comp_int);
    7. 	print1(arr1);
    8.  
    9. 	float arr2[5] = { 1.2,3.4,5.6,7.8,9.9 };
    10. 	print2(arr2);
    11. 	my_qsort(arr2, 5, sizeof(float), comp_float);
    12. 	print2(arr2);
    13.  
    14.  
    15. 	struct stu arr3[] = { {"zhangsan",19},{"lisi",20},{"wangswu",21} };
    16. 	my_qsort(arr3, 3, sizeof(arr3[0]), comp_name);
    17. 	my_qsort(arr3, 3, sizeof(arr3[0]), comp_age);
    18.  
    19. 	system("pause");
    20.  
    21. 	return 0;
    22. }

    观察结果：

            我们可以发现和我们预期的一样，对于不同数据类型，我们自己模拟的函数都可以实现排序功能 

    六.完整代码

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include
    3. #include
    4. #include
    5.  
    6. //结构体
    7. struct stu
    8. {
    9. 	char name[20];
    10. 	int age;
    11. };
    12.  
    13. void print1(int* arr)
    14. {
    15. 	for (int i = 0; i < 10; i++)
    16. 	{
    17. 		printf("%d ", *(arr + i));
    18. 	}
    19. 	printf("\n");
    20. }
    21.  
    22. void print2(float* arr)
    23. {
    24. 	for (int i = 0; i < 5; i++)
    25. 	{
    26. 		printf("%.2f ", *(arr + i));
    27. 	}
    28. 	printf("\n");
    29. }
    30.  
    31. //比较函数--整形
    32. int comp_int(const void* e1, const void* e2)
    33. {
    34. 	return *(int*)e1 - *(int*)e2;
    35. }
    36.  
    37. //比较函数--浮点型
    38. int comp_float(const void* a, const void* b)
    39. {
    40. 	return *(float*)b - *(float*)a;
    41. }
    42.  
    43. //比较函数--按照年龄
    44. int comp_age(const void* a, const void* b)
    45. {
    46. 	return ((struct stu*)b)->age - ((struct stu*)a)->age;
    47. }
    48.  
    49. //比较函数--按照姓名
    50. int comp_name(const void* a, const void* b)
    51. {
    52. 	return strcmp(((struct stu*)a)->name, ((struct stu*)b)->name);
    53. }
    54.  
    55. //交换函数
    56. void swap(char* buf1, char* buf2, size_t size)
    57. {
    58. 	//逐个字节进行交换，一共有size个字节
    59. 	for (int i = 0; i < size; i++)
    60. 	{
    61. 		//错误示范
    62. 		//char* temp = 0;
    63. 		//*temp = *buf1;
    64. 		//*buf1 = *buf2;
    65. 		//*buf2 = *temp;
    66. 		//buf1++;
    67. 		//buf2++;
    68. 		
    69. 		//正确示范
    70. 		char temp = *buf1;
    71. 		*buf1 = *buf2;
    72. 		*buf2 = temp;
    73. 		buf1++;
    74. 		buf2++;
    75. 	}
    76. }
    77.  
    78. //void qsort(void* base, size_t num, size_t size,int (*compar)(const void*, const void*));
    79. void my_qsort(void* base, size_t num, size_t size, int (*compare)(const void* e1, const void* e2))
    80. {
    81. 	//使用冒泡排序
    82. 	for (int i = 0; i < num - 1; i++)
    83. 	{
    84. 		//每一趟
    85. 		for (int j = 0; j < num - i - 1; j++)
    86. 		{
    87. 			//排序：前一个元素大于后一个
    88. 			if (compare((char*)base + j * size, (char*)base + (j + 1) * size) > 0)
    89. 			{
    90. 				//交换
    91. 				swap((char*)base + j * size, (char*)base + (j + 1) * size, size);
    92. 			}
    93. 		}
    94. 	}
    95. }
    96.  
    97. int main() 
    98. {
    99. 	int arr1[] = { 9,8,7,6,5,4,3,2,1,0 };
    100. 	int sz = sizeof(arr1) / sizeof(arr1[0]);
    101. 	print1(arr1);
    102. 	my_qsort(arr1, sz, sizeof(int), comp_int);
    103. 	print1(arr1);
    104.  
    105. 	float arr2[5] = { 1.2,3.4,5.6,7.8,9.9 };
    106. 	print2(arr2);
    107. 	my_qsort(arr2, 5, sizeof(float), comp_float);
    108. 	print2(arr2);
    109.  
    110.  
    111. 	struct stu arr3[] = { {"zhangsan",19},{"lisi",20},{"wangswu",21} };
    112. 	my_qsort(arr3, 3, sizeof(arr3[0]), comp_name);
    113. 	my_qsort(arr3, 3, sizeof(arr3[0]), comp_age);
    114.  
    115. 	system("pause");
    116.  
    117. 	return 0;
    118. }

            

            本次分享的俩篇文章就到此为止啦，希望我的分享对您有所帮助，文章中如有错误，欢迎积极指正，您的认可就是我最大的动力，那我们下次分享再见

  • 相关阅读:
    Spring学习
    FPGA TestBench编写学习
    Oracle 本地客户端连接远程 Oracle 服务端并使用 c# 连接测试
    【计算机毕业设计】网上商城购物系统
    算法刷题2(C++)链表遍历算法
    SQL基础知识笔记
    DEJA_VU3D - Cesium功能集 之 059-腾讯地图纠偏
    服务器的外网IP查阅方式
    自制OS1-1到2-11==BIOS MBR loader
    基于Java+SpringBoot+Vue前后端分离人事管理系统设计和实现
  • 原文地址：https://blog.csdn.net/m0_69519887/article/details/132896910