• C语言进阶之冒泡排序

              

                                  ✨ 猪巴戒：个人主页✨

                   所属专栏：《C语言进阶》

            🎈跟着猪巴戒，一起学习C语言🎈

    目录

    前情回顾

    1、回调函数

    2、冒泡排序

    3、库函数qsort

    cmp（sqort中的比较函数，需要我们自定义）

    整形的升序排列

    整形的倒序排列

    结构体的排序

    结构体按照名字(char类型)排序

    结构体按照年龄(int类型)排序

    库函数qsort的模拟实现（bubble_sort）

    呈现bubble_sort函数的整体代码：

     bubble_sort的结构体排序

    age: 

    name:

    前情回顾

    函数指针

    我们有一个函数，为Add,我们将函数的地址用指针来存储，这个指针就叫做函数指针。

    1. int Add(int x,int y)
    2. {
    3.     return x+y;
    4. }
    5.  
    6. int main()
    7. {
    8.     int (*pf)(int,int) = Add;//pf就是函数指针。
    9.     return 0;
    10. }

    函数指针数组

    把函数指针放在数组中，就是函数指针的数组。

    1. int Add(int x,int y)
    2. {
    3.     return x+y;
    4. }
    5. int Sub(int x,int y)
    6. {
    7.     return x-y;
    8. }
    9. int Mul(int x,int y)
    10. {
    11.     return x*y;
    12. }
    13. int Div(int x,int y)
    14. {
    15.     return x/y;
    16. }
    17. int main()
    18. {
    19.     int (*arr[4])(int ,int) = {Add,Sub,Mul,Div};//这个就是函数指针数组。
    20.     return 0;
    21. }

    0ef772519fa440768e39c8e8e92b995b.png

    函数指针数组就可以调用函数：

    1. int main()
    2. {
    3.     int i = 0;
    4.     scanf("%d",&i);
    5.     int ret = arr[i](8,4);
    6.     printf("%d\n",ret);
    7. }

    1、回调函数

    回调函数就是应该通过函数指针调用的函数。如果你把函数的指针（地址）作为参数传递给另一个函数，当这个指针被用来调用其所指向的函数时，我们就说这是回调函数。回调函数不是由这个函数的实现方直接调用，而是在特定的事件或条件发生时由另外的一方调用的，用于对该事件或条件进行响应。

    我们可以把Add函数称为回调函数。

    1. int Add(int x,int y)
    2. {
    3.     return x+y;
    4. }
    5. int main()
    6. {
    7.     int (*pf)(int,int) = Add;
    8.     int ret = pf(8,4);
    9.     return 0;
    10. }

    2、冒泡排序

    对一个数组进行升序排序。

    1. void bubble_sort(int arr[],int sz)
    2. {
    3.     int i=0;
    4.     //趟数
    5.     for(i=0;i-1;i++)
    6.     {
    7.         //一趟冒泡排序的过程
    8.         int j = 0;
    9.         for(j=0;j-1-i;j++)
    10.         {
    11.             if(arr[j]>arr[j+1])
    12.             {
    13.                 int tmp = arr[j];
    14.                 arr[j] =arr[j+1];
    15.                 arr[j+1] = tmp;
    16.             }
    17.         } 
    18.     }
    19. }
    20. int main()
    21. {
    22.     int arr[] = {9,8,7,6,5,4,3,2,1 };
    23.     //把数组排成升序
    24.     int sz = sizeof(arr)/sizeof(arr[0]);
    25.     bubble_sort(arr,sz);
    26.     int i = 0;
    27.     for(i=0;i
    28.     {
    29.         printf("%d",arr[i]};
    30.     }

    这个冒泡排序不够高效，如果我们进行一趟冒泡排序，但是一个数字都没有交换，就说明这个数组已经排序好了，就不用继续排序了，

    我们可以通过，在进行这一趟冒泡排序前设定int flag = 1;

    如果数字进行了交换，就把flag的值改为0；

    没有数字进行交换，那么flag的值还是1；

    我们通过判断flag的值看数组是否已经排好序。

    1. void bubble_sort(int arr[],int sz)
    2. {
    3.     int i=0;
    4.     //趟数
    5.     for(i=0;i-1;i++)
    6.     {
    7.         int flag = 1;//假设数组是排好序的。
    8.         //一趟冒泡排序的过程
    9.         int j = 0;
    10.         for(j=0;j-1-i;j++)
    11.         {
    12.             if(arr[j]>arr[j+1])
    13.             {
    14.                 int tmp = arr[j];
    15.                 arr[j] =arr[j+1];
    16.                 arr[j+1] = tmp;
    17.                 flag = 0;//数组进行了排序
    18.             }
    19.         }  
    20.         if(flag == 1)
    21.         {
    22.             break;
    23.         }    
    24.     }
    25.     
    26. }
    27. int main()
    28. {
    29.     int arr[] = {9,8,7,6,5,4,3,2,1 };
    30.     //把数组排成升序
    31.     int sz = sizeof(arr)/sizeof(arr[0]);
    32.     bubble_sort(arr,sz);
    33.     int i = 0;
    34.     for(i=0;i
    35.     {
    36.         printf("%d",arr[i]};
    37.     }
    38.     return 0;
    39. }

    3、库函数qsort

    使用快速排序的思想实现的一个排序函数。

    qsort可以排序任何类型的数据

    1. void qsort(void* base,//你要排序的数据的起始位置
    2.            size_t num,//待排序的数据元素的个数
    3.            size_t width,//待排序的数据元素的大小(单位是字节)
    4.            int(* cmp)(const void* e1,const void* e2)//函数指针-比较函数
    5.            );

    cmp（sqort中的比较函数，需要我们自定义）

    int(* cmp)(const void* e1,const void* e2)中的e1,e2就是我们要比较数据的地址。

    在这个比较函数中我们实现不同类型的元素比较

    void*是无具体类型的指针，可以接收任何类型的地址

    void*是无具体类型的指针，所以不能解引用操作，也不能+-整数

    当比较函数返回的是大于0的数字，那么两组数据就会进行交换。

    进行整型数据的比较， 这是进行升序排列

    1. int cmp_int(const void* e1,const void* e2)
    2. {
    3.    return (*(int*)e1 - *(int*)e2);
    4. }

    整形的升序排列

    通过qsort来将数组进行升序排序

    1. //比较两个整形元素
    2. //e1指向一个整形
    3. //e2指向另外一个整形
    4. #include 
    5. #include 
    6. int cmp_int(const void* e1,const void* e2)
    7. {
    8.     return (*(int*)e1 - *(int*)e2);
    9. }
    10. int main()
    11. {
    12.     int arr[] = {9,8,7,6,5,4,3,2,1};
    13.     
    14.     int sz = sizeof(arr) / sizeof(arr[0]);
    15.     
    16.     qsort(arr,sz,sizeof(arr[0]),cmp_int);
    17.     
    18.     int i = 0;
    19.     for(i=0;i
    20.     {
    21.         printf("%d ",arr[i]);
    22.     }    
    23.     return 0;
    24. }

    cmp_int就是回调函数 

    整形的倒序排列

    当我们需要进行降序排列，只要将e2和e1的顺序倒过来就可以实现

    1. int cmp_int(const void* e1,const void* e2)
    2. {
    3.     return (*(int*)e2 - *(int*)e1);
    4. }

    结构体的排序

    结构体按照名字(char类型)排序

    char类型的数据不能够直接比较，我们用到strcmp进行比较，

    库函数strcmp

    头文件

    int strcmp( const char *string1, const char *string2 );

    如果string1小于string2，就会返回小于0的数

    如果string1等于string2，就会返回0

    如果string1大于string2，就会返回大于0的数

    1. #include
    2. #include
    3. struct Stu
    4. {
    5.     char name[20];
    6.     int age;
    7. };
    8. int cmp_stu_by_name(const void* e1,const void* e2)
    9. {
    10.     return strcmp(((struct Stu*)e1)->name,((struct Stu*)e2)->name);
    11. }
    12. int main()
    13. {
    14.     struct Stu s[] = {{"zhangsan",15},{"lisi",30},{"wangwu",25}};
    15.     int sz = sizeof(s) / sizeof(s[0]);
    16.     qsort(s,sz,sizeof(s[0]),cmp_stu_by_name);
    17.     return 0;
    18. }

    cmp_stu_by_name就是回调函数

    结构体按照年龄(int类型)排序

    1. #include
    2. #include
    3. struct Stu
    4. {
    5.     char name[20];
    6.     int age;
    7. };
    8. int cmp_stu_by_age(const void*e1,constvoid* e2)
    9. {
    10.      return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
    11. }
    12. int main()
    13. {
    14.     struct Stu s[] = {{"zhangsan",15},{"lisi",30},{"wangwu",25}};
    15.     int sz = sizeof(s) / sizeof(s[0]);
    16.     qsort(s,sz,sizeof(s[0]),cmp_stu_by_age);
    17.     return 0;
    18. }

    库函数qsort的模拟实现（bubble_sort）

    如何实现qsort函数？库函数qsort的设计原理是什么？

    创建自定义函数实现库函数qsort的功能。

    基于qsort实现原理，实现将整形数组升序排列

    设计自定义函数bubble_sort，等同于库函数qsort

    void bubble_sort(void* base, int sz, int width, int(*cmp)(const void* e1, const void* e2))

    void qsort( void *base, size_t num, size_t width, int (__cdecl *compare )(const void *elem1, const void *elem2 ) );

    base：数据的起始位置，首元素的地址

    sz: 数据元素的个数，比较数组的话，就是数组中元素的个数

    width:待排序的数据元素的大小(单位是字节),比较整形数组的话，就是4个字节，数组元素占内存的大小

    cmp:自定义的比较函数。

     关于bubble_sort的设计细节

    这是我们对解决整形数组升序排列问题，也就是冒泡排序，原来的的bubble_sort.

    但是我们现在要设计的bubble_sort，需要与qsort有相同的功能（排序任何类型的数据）

    1. void bubble_sort(int arr[],int sz)
    2. {
    3.     int i=0;
    4.     //趟数
    5.     for(i=0;i-1;i++)
    6.     {
    7.         int flag = 1;//假设数组是排好序的。
    8.         //一趟冒泡排序的过程
    9.         int j = 0;
    10.         for(j=0;j-1-i;j++)
    11.         {
    12.             if(arr[j]>arr[j+1])
    13.             {
    14.                 int tmp = arr[j];
    15.                 arr[j] =arr[j+1];
    16.                 arr[j+1] = tmp;
    17.                 flag = 0;//数组进行了排序
    18.             }
    19.         }  
    20.         if(flag == 1)
    21.         {
    22.             break;
    23.         }    
    24.     }
    25.     
    26. }

    1.

    void bubble_sort(void* base, int sz, int width, int(*cmp)(const void* e1, const void* e2))

    参数void类型可以接收任何类型的数据

    2.

    判断大小，

    原来：数组元素比较大小

    现在：比较一种无知类型元素大小，通过比较函数（cmp）来比较，由于我们不知道要比较的元素类型是什么，但是我们要找到每个元素的地址，就通过（char*)base + j * width,

    第一个元素的地址就是首元素的地址，

    第二个元素的地址就是首元素的地址加上一个元素的字节

    width:待排序的数据元素的大小(单位是字节)

    在bubble_sort中，cmp((char*)base + j * width, (char*)base + (j + 1) * width)

    3.

    自定义函数（cmp）的实现，已知我们要比较的是整形元素的大小，和库函数qsort解决整形的升序排列一样

    1. int cmp_int(const void* e1, const void* e2)
    2. {
    3. 	return *(int*)e1 - *(int*)e2;
    4. }

    4.

    交换元素

     cmp_int的功能

    当比较函数返回的是大于0的数字，那么两组数据就会进行交换。

    进行整型数据的比较， 这是进行升序排列

    在bubble_sort中，当cmp判断>0时

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

    进行交换

    交换函数

    我们要找到各个元素我们才能进行比较，所以和cmp函数的实现类似，

    我们要传递的参数

    Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);

    找到了各个元素的地址，也知道元素的大小（字节），就可以进行比较，

    一个一个字节进行比较，

    Swap函数实现：

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

     5.

    为了函数的高效性，我们把原来的flag的设计保留。

    也就是int flag = 1;(假设数组已经排列好）

    如果在这一趟的冒泡排序的过程中，数字进行了交换，就把flag的值改为0；

    没有数字进行交换，那么flag的值还是1，就可以直接跳出循环；

    呈现bubble_sort函数的整体代码：

    1. #include
    2. void Swap(char* buf1, char* buf2, int width)
    3. {
    4. 	int i = 0;
    5. 	for (i = 0; i < width; i++)
    6. 	{
    7. 		char tmp = *buf1;
    8. 		*buf1 = *buf2;
    9. 		*buf2 = tmp;
    10. 		buf1++;
    11. 		buf2++;
    12. 	}
    13. }
    14. int cmp_int(const void* e1, const void* e2)
    15. {
    16. 	return *(int*)e1 - *(int*)e2;
    17. }
    18. void bubble_sort(void* base, int sz, int width, int(*cmp)(const void* e1, const void* e2))
    19. {
    20. 	int i = 0;
    21. 	//趟数
    22. 	for (i = 0; i < sz - 1; i++)
    23. 	{
    24. 		int flag = 1;//假设数组是排好序
    25. 		//一趟冒泡排序的过程
    26. 		int j = 0;
    27. 		for (j = 0; j < sz - 1 - i; j++)
    28. 		{
    29. 			if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
    30. 			{
    31. 				//交换
    32. 				Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
    33. 				flag = 0;
    34. 			}
    35. 		}
    36. 		if (flag == 1)
    37. 		{
    38. 			break;
    39. 		}
    40. 	}
    41. }
    42. int main()
    43. {
    44. 	int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
    45. 	//0 1 2 3 4 5 6 7 8 9
    46. 	//把数组排成升序
    47. 	int sz = sizeof(arr) / sizeof(arr[0]);
    48. 	//bubble_sort(arr, sz);
    49.  
    50. 	bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);
    51.  
    52. 	int i = 0;
    53. 	for (i = 0; i < sz; i++)
    54. 	{
    55. 		printf("%d ", arr[i]);
    56. 	}
    57. }

    e12eca3b78924dceba38b973cb8aff85.png

     bubble_sort的结构体排序

    前面有完整的bubble_sort的实现，这里就不把bubble_sort写上了

    1. #include
    2. struct Stu 
    3. {
    4. 	char name[20];
    5. 	int age;
    6. };
    7. int cmp_stu_by_age(const void* e1, const void* e2)
    8. { 
    9. 	return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
    10. }
    11. int cmp_stu_by_name(const void* e1, const void* e2)
    12. {
    13. 	return strcmp(((struct Stu*)e1)->name , ((struct Stu*)e2)->name);
    14. }
    15. void test()
    16. {
    17. 	struct Stu s[] = { {"zhangsan", 15}, {"lisi", 30}, {"wangwu", 25} };
    18. 	int sz = sizeof(s) / sizeof(s[0]);
    19. 	bubble_sort(s, sz, sizeof(s[0]), cmp_stu_by_name);
    20. 	//bubble_sort(s, sz, sizeof(s[0]), cmp_stu_by_age);
    21. }
    22. int main()
    23. {
    24. 	test();
    25. 	return 0;
    26. }

    age: 

    90d276b4d2b4434996091f6029b1cc47.png

    name:

    f364844a2fa2439c82aef0a529082e32.png

  • 相关阅读:
    专访阿里云：AI 时代服务器操作系统洗牌在即，生态合作重构未来
    [Elastic-Job2.1.5源码]-12-调度作业的服务器IP和进程信息的持久化是如何设计的?
    python 数据保存为npy和npz格式并读取
    Nature Electronics|微器件在柔性基底上的高密度集成（可穿戴电子/界面调控/电子皮肤/柔性电子）
    Django笔记二十五之数据库函数之日期函数
    2023-10-20 游戏开发-开源游戏-记录
    Scala中编写多线程爬虫程序并做可视化处理
    C++在HotSpot VM中一种巧妙的内存管理方式
    Spring Framework 6正式发布，携JDK 17&Jakarta EE开启新篇章
    大数据Doris（十二）：扩容缩容
  • 原文地址：https://blog.csdn.net/2302_79491024/article/details/134528631