经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C 语言 » 查看文章
C语言库函数qsort及bsearch快速排序算法使用解析
来源:jb51  时间:2022/2/14 13:36:13  对本文有异议

qsort

qsrot 就是C语言库函数中的快速排序函数,对数组,结构体都可以实现快速排序, 他在头文件<stdlib.h>中使用,声明格式为:

  1. void qsort(void* base, size_t nums, size_t size, int (*compare)(const void *, const void*))

这么烦人一长串的参数各是什么意思呢,base 是指向要排序的数组的第一个元素的指针。nums是由 base 指向的数组中元素的个数。size 是数组中每个元素的大小,以字节为单位。compare 是用来比较两个元素的函数,这个比较函数需要我们自己补全。

含义

void*代表着任意类型的数组,这个数组也就是我们想用来排序的对象数组;size_t 在系统里面被定义成 int 类型的,所以我们可以把 size_t修饰的数默认为一个整数。

为什么要细化出数组大小和元素大小?这和我排序有毛关系?其实这是为了区分不同类型的数组,int 和 char 类型的数组每个元素所占空间就不一样,自然要区别开。

  1. int main()
  2. {
  3. int arr[6] = { 1,4,5,8,2,3};
  4. qsort(arr, 6, sizeof(arr[0]), compare);
  5. }

最后的 compare 函数我是直接将这个元素作为参数传进来,那么问题来了,这个比较函数怎么写?

我们根本不用管那个 *compare 的指针什么鬼,他就相当于告诉你这里在用一个外部函数,我们只要明白整个函数名儿上去就是妥妥的了,这个函数名不一定就叫 compare ,诸君自便。

实现

后面的(const void , const void)自然就是这个函数的参数了,两个 void* 实际运用的时候就看成 a ,b,既然是外部函数我们就要自己动手了,我们的最终目的是为了排序,比较函数就应该实现数组元素大小的比较,本质上说就是在比较 a和b 的大小,而a,b是我数组中任意的两两元素。

那首先要做的就是把这个不知道什么类型的 void 指针变成我们给定的,之前代码中给的是整型数组,这里就要对应变成整型指针,这两个指针指向数组中的两个整数,既然要比较,我们就直接做减法看正负即可,把这两个指针转换成真正的整数后就大功告成了:

  1. int* p = (int*)a;
  2. int* q = (int*)b;
  3. int c = *p;
  4. int d = *q;

成品如下:

  1. #include<stdlib.h>
  2. int compare(const void* a,const void* b)
  3. {
  4. int* p = (int*)a;
  5. int* q = (int*)b;
  6. int c = *p;
  7. int d = *q;
  8. return c - d;
  9. }
  10. int main()
  11. {
  12. int i = 0;
  13. int arr[6] = { 1,4,5,8,2,3 };
  14. qsort(arr, 6, sizeof(arr[0]), compare);
  15. for (i = 0; i < 6; i++)
  16. {
  17. printf("%d ", arr[i]);
  18. }
  19. return 0;
  20. }

结果如下

在这里插入图片描述

结构体的排序也是同理,如下:

  1. #include<stdlib.h>
  2. int compare(const void* a,const void* b)
  3. {
  4. int* p = (int*)a;
  5. int* q = (int*)b;
  6. int c = *p;
  7. int d = *q;
  8. return c - d;
  9. }
  10. int main()
  11. {
  12. int i = 0;
  13. int arr[6] = { 1,4,5,8,2,3 };
  14. qsort(arr, 6, sizeof(arr[0]), compare);
  15. for (i = 0; i < 6; i++)
  16. {
  17. printf("%d ", arr[i]);
  18. }
  19. return 0;
  20. }

结果就是根据结构体中 a 成员大小来排的:

在这里插入图片描述

格局打开

1.上面是实现从小到大排列,要实现从大到小排只需 return d - c 即可。
2.如果是比较浮点数,注意在两个数相差不大时,介于(-1,1),因为现在是整型指针,返回值也是整型,return 回来的就是个 0,造成无意义操作,怎么处理呢?很简单,改成如下即可:

  1. int compare(const void* a,const void* b)
  2. {
  3. int* p = (int*)a;
  4. int* q = (int*)b;
  5. int c = *p;
  6. int d = *q;
  7. if(c - d<0)
  8. {
  9. return -1;
  10. }
  11. else
  12. {
  13. return 1;
  14. }
  15. }

bsearch

bsearch (binary search)也是C语言库函数,功能是执行二分查找,声明定义如下

  1. void *bsearch(const void *key, const void *base, size_t nums, size_t size, int (*compar)(const void *, const void *))

和 qsort 一样是又臭又长,且随我慢慢看,key 是指向要查找的元素的指针,类型转换为 void*,其他的和 qsort 里的是一样的不再赘述。

强调一下,bsearch()的使用有一个硬性要求,这个数组必须要有顺序性,从大到小或从小到大否则达咩,所以建议和 qsort 配套实验更佳。

这个 key 就是我们的查找目标,void* 代表着一个指针,所以我们在函数里面是不能直接给出的 key 的值,那我们就取他对应的地址就行

  1. int key = 5;
  2. bsearch(&key,arr,6,sizeof(int),compare1);

接下来顺水推舟验证一下:

  1. judge = (int*) bsearch (&key, values, 5, sizeof (int), cmpfunc);
  2. if( judge != NULL )
  3. {
  4. printf("find %d is true\n", *judge);
  5. }
  6. else
  7. {
  8. printf("%d can not be found\n", *judge);
  9. }
  10. return(0);
  11. }

整个代码如下:

  1. #include<stdlib.h>
  2. int compare(const void* a, const void* b)
  3. {
  4. int* p = (int*)a;
  5. int* q = (int*)b;
  6. int c = *p;
  7. int d = *q;
  8. return c - d;
  9. }
  10. int compare1(const void* key, const void* a)
  11. {
  12. return (*(int*)key-*(int*)a);
  13. }
  14. int main()
  15. {
  16. int* judge;
  17. int arr[6] = { 1,4,5,8,2,3 };
  18. qsort(arr, 6, sizeof(arr[0]), compare);
  19. int key = 5;
  20. judge = (int*)bsearch(&key, arr, 5, sizeof(int), compare1);
  21. if (judge != NULL)
  22. {
  23. printf("find %d is true\n", *judge);
  24. }
  25. else
  26. {
  27. printf("%d can not be found\n", *judge);
  28. }
  29.  
  30. return(0);
  31. }

在这里插入图片描述

今天就先到这里吧,摸了家人们,更多关于C语言库函数qsort及bsearch快速排序算法的资料请关注w3xue其它相关文章!

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号