当前位置:   article > 正文

用冒泡排序模拟C语言中的内置快排函数qsort!

用冒泡排序模拟C语言中的内置快排函数qsort!

目录

 ​编辑

1.回调函数的介绍

2. 回调函数实现转移表

3. 冒泡排序的实现

4. qsort的介绍和使用

5. qsort的模拟实现 

6. 完结散花


 

                                            悟已往之不谏,知来者犹可追  

创作不易,宝子们!如果这篇文章对你们有帮助的话,别忘了给个免费的赞哟~

1.回调函数的介绍

这里首先介绍一下回调函数的概念~

回调函数是使用函数指针(地址)调用的函数。

如果我们把一个函数的指针(地址)作为一个参数传递给另一个函数,当我们通过指针找到这个函数并对其进行调用时,这个被调用的函数就是回调函数。

回调函数不是由该函数的实现方直接调用,而是在特定的事件或条件发生时由另外的一方调用的,用于对该事件或条件进行响应

  1. #include<stdio.h>
  2. test(void (*print)())
  3. {
  4. print();
  5. }
  6. void print()
  7. {
  8. printf("这是一个回调函数\n");
  9. }
  10. int main()
  11. {
  12. test(print);
  13. return 0;
  14. }


2. 回调函数实现转移表

现在我们来实现一个简单的计算器~

  1. #include <stdio.h>
  2. int add(int a, int b)
  3. {
  4. return a + b;
  5. }
  6. int sub(int a, int b)
  7. {
  8. return a - b;
  9. }
  10. int mul(int a, int b)
  11. {
  12. return a * b;
  13. }
  14. int div(int a, int b)
  15. {
  16. return a / b;
  17. }
  18. int main()
  19. {
  20. int x, y;
  21. int input = 1;
  22. int ret = 0;
  23. do
  24. {
  25. printf("*************************\n");
  26. printf(" 1:add 2:sub \n");
  27. printf(" 3:mul 4:div \n");
  28. printf(" 0:exit \n");
  29. printf("*************************\n");
  30. printf("请选择:");
  31. scanf("%d", &input);
  32. switch (input)
  33. {
  34. case 1:
  35. printf("输⼊操作数:");
  36. scanf("%d %d", &x, &y);
  37. ret = add(x, y);
  38. printf("ret = %d\n", ret);
  39. break;
  40. case 2:
  41. printf("输⼊操作数:");
  42. scanf("%d %d", &x, &y);
  43. ret = sub(x, y);
  44. printf("ret = %d\n", ret);
  45. break;
  46. case 3:
  47. printf("输⼊操作数:");
  48. scanf("%d %d", &x, &y);
  49. ret = mul(x, y);
  50. printf("ret = %d\n", ret);
  51. break;
  52. case 4:
  53. printf("输⼊操作数:");
  54. scanf("%d %d", &x, &y);
  55. ret = div(x, y);
  56. printf("ret = %d\n", ret);
  57. break;
  58. case 0:
  59. printf("退出程序\n");
  60. break;
  61. default:
  62. printf("选择错误\n");
  63. break;
  64. }
  65. } while (input);
  66. return 0;
  67. }

我们可以很容易的观察到上述代码有一部分是多次重复的~

 这部分只有函数的调用是不一样的,所以我们是不是可以把这部分封装成一个函数calc(),在calc函数中调用不同的加减乘除函数就行了呢~

  1. #include <stdio.h>
  2. int add(int a, int b)
  3. {
  4. return a + b;
  5. }
  6. int sub(int a, int b)
  7. {
  8. return a - b;
  9. }
  10. int mul(int a, int b)
  11. {
  12. return a * b;
  13. }
  14. int div(int a, int b)
  15. {
  16. return a / b;
  17. }
  18. void cacl(int(*p)(int x, int y))
  19. {
  20. int x = 0;
  21. int y = 0;
  22. printf("输入操作数:");
  23. scanf("%d %d", &x, &y);
  24. int ret = p(x, y);
  25. printf("ret = %d\n", ret);
  26. }
  27. int main()
  28. {
  29. int input = 1;
  30. do
  31. {
  32. printf("*************************\n");
  33. printf(" 1:add 2:sub \n");
  34. printf(" 3:mul 4:div \n");
  35. printf(" 0:exit \n");
  36. printf("*************************\n");
  37. printf("请选择:");
  38. scanf("%d", &input);
  39. switch (input)
  40. {
  41. case 1:
  42. cacl(add);
  43. break;
  44. case 2:
  45. cacl(sub);
  46. break;
  47. case 3:
  48. cacl(mul);
  49. break;
  50. case 4:
  51. cacl(div);
  52. break;
  53. case 0:
  54. printf("退出程序\n");
  55. break;
  56. default:
  57. printf("选择错误\n");
  58. break;
  59. }
  60. } while (input);
  61. return 0;
  62. }

3. 冒泡排序的实现

常见的排序有插入排序、选择排序、希尔排序、冒泡排序、快速排序等等~

在讲qsort前,这里我们先了解一下冒泡排序~

顾名思义,冒泡排序就是让元素像泡泡一样慢慢往上移动~

 这里我用C语言来实现一下~

  1. void bull_sort(int* arr,int len)
  2. {
  3. assert(arr);//判断指针的有效性
  4. for (int i = 0; i < len - 1; i++)
  5. {
  6. int flag = 1;//假设已经有序
  7. for (int j = 0; j < len - 1 - i; j++)
  8. {
  9. if (arr[j] > arr[j + 1])
  10. {
  11. int tmp = arr[j];
  12. arr[j] = arr[j + 1];
  13. arr[j + 1] = tmp;
  14. flag = 0;
  15. }
  16. }
  17. if (flag == 1)
  18. break;
  19. }
  20. }
  21. int main()
  22. {
  23. int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
  24. int len = sizeof(arr) / sizeof(arr[0]);
  25. bull_sort(arr, len);
  26. for (int i = 0; i < len; i++)
  27. {
  28. printf("%d ", arr[i]);
  29. }
  30. return 0;
  31. }

运行效果~

 

4. qsort的介绍和使用

接下来我们就来看看qsort啦~

注意我们在使用qsort时要引入头文件#include<stdlib.h>

这里简单的举个栗子来使用一下qsort啦~

  1. int cmp_int(const void* a, const void* b)
  2. {
  3. assert(a && b);
  4. return *(int*)a - *(int*)b;
  5. }
  6. int main()
  7. {
  8. int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
  9. int len = sizeof(arr) / sizeof(arr[0]);
  10. assert(arr);//判断指针的有效性
  11. qsort(arr, len, sizeof(arr[0]), cmp_int);
  12. for (int i = 0; i < len; i++)
  13. {
  14. printf("%d ", arr[i]);
  15. }
  16. return 0;;
  17. }

效果如下~

 我们还可以使用qsort比较结构体类型的变量!

我们通过结构体中的名字来比较结构体变量的大小~

  1. struct S
  2. {
  3. char name[20];
  4. int age;
  5. };//定义一个结构体类型
  6. int cmp_stu_by_age(const void* a,const void* b)
  7. {
  8. return strcmp(((struct S*)a)->name, ((struct S*)b)->name);
  9. }
  10. int main()
  11. {
  12. struct S student[3] = { {"zhangsan",18},{"lisi",17},{"wanglaowu",16} };//定义一个结构体数组并初始化
  13. int len = sizeof(student) / sizeof(student[0]);
  14. qsort(student, len, sizeof(student[0]), cmp_stu_by_age);
  15. return 0;
  16. }

排序前~

排序后~

5. qsort的模拟实现 

对比上面我们自己写的冒泡排序和C语言中的内置快排,我们会发现我们自己写的冒泡排序只能对int类型的数据进行排序(有局限性),而qsort却可以对任意类型的数据进行排序。

接下来这里我就使用冒泡排序的算法模拟实现qsort~

  1. int cmp_int(const void* a, const void* b)
  2. {
  3. assert(a && b);
  4. return *(int*)a - *(int*)b;
  5. }
  6. void swap(char* buf1,char* buf2,size_t num)//一个一个字节交换
  7. {
  8. while (num--)
  9. {
  10. char tmp = *(buf1);
  11. *(buf1) = *(buf2);
  12. *(buf2) = tmp;
  13. buf1++;
  14. buf2++;
  15. }
  16. }
  17. void my_qsort(void* arr, size_t len, size_t num, int (*cmp_int)(const void*,const void*))
  18. {
  19. assert(arr);//判断指针的有效性
  20. for (int i = 0; i < len - 1; i++)
  21. {
  22. int flag = 1;//假设已经有序
  23. for (int j = 0; j < len - 1 - i; j++)
  24. {
  25. if(cmp_int((char*)arr + j * num, (char*)arr + (j + 1) * num)>0);
  26. {
  27. swap(((char*)arr + j * num), ((char*)arr + (j + 1) * num),num);
  28. flag = 0;
  29. }
  30. }
  31. if (flag == 1)
  32. break;
  33. }
  34. }
  35. int main()
  36. {
  37. int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
  38. size_t len = sizeof(arr) / sizeof(arr[0]);
  39. my_qsort(arr, len, sizeof(arr[0]), cmp_int);
  40. for (int i = 0; i < len; i++)
  41. {
  42. printf("%d ", arr[i]);
  43. }
  44. return 0;
  45. }

运行效果如下~

 

6. 完结散花

好了,这期的分享到这里就结束了~

如果这篇博客对你有帮助的话,可以用你们的小手指点一个免费的赞并收藏起来哟~

如果期待博主下期内容的话,可以点点关注,避免找不到我了呢~

我们下期不见不散~~

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/AllinToyou/article/detail/732248
推荐阅读
相关标签
  

闽ICP备14008679号