c++中内置函数qsort(快速排序)和bsearch(二分查找)详解

c/c++qsort(快速排序)和bsearch(二分查找算法)

前两天自己写代码的时候,在程序中对于一些简单的排序和查找算法都得自己去写,个人觉得非常麻烦,然后我看官方的api手册偶然发现了在其他标准库函数中有封装好了的快速排序算法和二分查找算法,然后经过本人的一中午的时间的硬肝,终于把其用法给搞懂了,现在给大家分享一下:

c++中内置函数qsort(快速排序)和bsearch(二分查找)详解
c++中内置函数qsort(快速排序)和bsearch(二分查找)详解

这是我从官方的api手册中截图过来的,两个函数的参数在官方文档中解释的很清楚,我就不再解释了。

  1. int型数据进行排序

我们来看这两个函数中都需要传入一个名为compare()的函数,在该compare函数中有两个类型为void的常指针,这个函数是需要自己定义的,用来对buf中指定的数据类型进行排序。

如果buf中定义的数据类型是int型的话,那么我们可以简单的定义该compare函数:(默认按照升序排列,如果需要降序排列,只需要将compare函数中的返回值改为*(int *)b-*(int *)a

int compare(const void* a,const void* b)  //参数格式固定
{
    return *(int *)a-*(int *)b;
}
  1. double型的数据进行排序

注:此处最好自己改写compare函数,因为要是使用像整型那样相减的话,如果是两个很接近的数则可能返回一个很小的小数(大于-1,小于1或者等于0),而cmp的返回值是int型,因此会将这个小数返回0,系统认为是相等,失去了本来存在的大小关系

此处贴上我的代码(给大家提醒一个错误,我看到很多其他博主这个地方使用三元运算符*(double *)a-*(double *)b?1:-1,这个地方我这样写是有问题的,无法得到正确的排序结果,输出的仍然会是乱序),看下面贴图:
c++中内置函数qsort(快速排序)和bsearch(二分查找)详解

c++中内置函数qsort(快速排序)和bsearch(二分查找)详解

这个地方卡了我一中午,我能想到的原因就是当数据为double型时做+或-运算时,因为在内存中存的数由于精确地的问题,存在小尾数,所以看似相等的两个double型的数据相减,不一定为0,所以在此处,我们需要人为的让它返回0。

事实也确实如此,看下面贴图,我明明存的是4.000000000000x(x取1~9),但是在输出时却出现了尾随机小数,甚至于有的数小数部分明明存的是整小数,但是还是出现了尾随机数,并且接近于我们的数字。

c++中内置函数qsort(快速排序)和bsearch(二分查找)详解

如果像这样的话,还想要使用qsort函数时,能够得到正确的结果,那么compare函数需要改写为如下形式:

int compare(const void* a,const void* b)  //参数格式固定
{
    int sum;
    double ans=*(double *)a-*(double *)b; //强制类型转换
    if(ans>0)
        sum=1;
    else if(ans<0)
        sum=-1;
    else
        sum=0;
    return sum;
}
  1. 对char型数组排序(同int类型)
char word[100];

int compare(const void* a,const void* b)  //参数格式固定
{
    char* aa = (char*)a;    //强制类型转换
    char* bb = (char*)b;
    return *aa - *bb;
}
  1. 对字符串进行排序
int compare(const void* a,const void* b)  //参数格式固定
{
    char* aa = (char*)a;  //强制类型转换
    char* bb = (char*)b;
    return strcmp(aa,bb);
}
上一篇:E.干饭人


下一篇:C语言常用库函数:快速排序qsort与查找bsearch