欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

C标准库的两大神器:快速排序qsort和二分查找bsearch

程序员文章站 2024-01-23 14:51:28
...

文章目录

快速排序

stdlib.h中的排序函数为

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))

其中,

  • base为指向数组第一个元素的指针
  • nitems为待排序数组中元素个数
  • size为数组中每个元素的字节数
  • compar是个函数指针,为用于比较两个元素的函数,

其中,用于比较元素的compar符合我们的直觉,可定义为

int cmpInt (const void * a, const void * b);

当其返回值大于0时,表示a>b,等于0时,表示a=b,小于0时表示a<b

这种函数指针出现在C语言标准库中感觉还是很炫酷的,连带着让qsort也显得高级感十足,下面举个例子来测试一下

//sortList.c
#include <stdio.h>
#include <stdlib.h>

//用于比较的函数
int cmpInt (const void * a, const void * b){
   return (*(int*)a - *(int*)b);
}

void printList(int *lst, int N){
   for(int n = 0 ; n < N; n++ )
      printf("%d ", lst[n]);
    printf("\n");
}

int main(){
    int N = 8;
    int lst[N];
    for(int i=0; i<N; i++)
        lst[i] = rand();
    printf("the original list: ");
    printList(lst, N);
    
    qsort(lst, N, sizeof(int), cmpInt);
    printf("the qSorted list: ");
    printList(lst, N);
    
    return 0;
}

输出结果为

>gcc sortList.c
>a.exe
the original list: 41 18467 6334 26500 19169 15724 11478 29358
the qSorted list: 41 6334 11478 15724 18467 19169 26500 29358

二分查找

所谓二分查找,前提是有一个有序数组。假设这个数组是升序数组,那么先将这个数组从中间分开,变成两份,此之谓二分。然后用中间值和待查元素比较,如果中间值大于待查元素,那么就舍弃大份,用小份和待查元素继续二分查找,知道分完或者找到待查元素。

stdlib.h中的二分查找函数为

void *bsearch(const void *key, const void *base, size_t nitems, size_t size, int (*compar)(const void *, const void *))

其中,

  • key指向要查找的元素
  • base指向被查数组的第一个对象
  • nitems为数组中元素个数
  • size为数组中每个元素的字节数
  • compar用来比较两个元素的函数,和qsort中相似。

如果keybase数组中,则返回数组中等于key的值的指针,否则返回NULL

举个例子

//searchList.c
#include <stdio.h>
#include <stdlib.h>

int cmpInt (const void * a, const void * b){
   return (*(int*)a - *(int*)b);
}

void printPos(int* lst, int* pos, int key){
    if(pos == NULL)
        printf("%d is not in lst\n", key);
    else
        printf("Found %d at %d\n", *pos, pos-lst);
}

int main(){
    size_t N = 6;
    int lst[N];
    for(int i=0; i<N; i++)
        lst[i] = rand();
    int *p;

    //对乱序lst中的值进行查找
    printf("----search from unsorted values-----\n");
    for(int i = 0; i<N; i++){
	   p = (int*)bsearch(lst+i, lst, N, sizeof(int), cmpInt);
	   printPos(lst, p, lst[i]);
    }

    //对排序后的list进行查找
    printf("---------search from sorted values---------\n");
    qsort(lst, N, sizeof(int), cmpInt);
    for(int i = 0; i<N; i++){
	   p = (int*)bsearch(lst+i, lst, N, sizeof(int), cmpInt);
	   printPos(lst, p, lst[i]);
    }

    //对不在lst中的值进行查找
    printf("------search rand value ----------\n");
    int rd;
    for(int i = 0; i<3; i++){
        rd = rand();
        p = (int*)bsearch(&rd, lst, N, sizeof(int), cmpInt);
        printPos(lst, p, rd);
    }
   
   return 0;
}

得到其结果为

>gcc test.c
>a.exe
----search from unsorted values-----
Found 41 at 0
18467 is not in lst
Found 6334 at 2
26500 is not in lst
Found 19169 at 4
15724 is not in lst
---------search from sorted values---------
Found 41 at 0
Found 6334 at 1
Found 15724 at 2
Found 18467 at 3
Found 19169 at 4
Found 26500 at 5
------search rand value ----------
11478 is not in lst
29358 is not in lst
26962 is not in lst

必须要注意的一点是,二分查找输入的数组必须是有序的,bsearch只会机械地按照比较函数进行二分,而并没有排序的义务。如果输入是乱序,那么可事先通过qsort进行排序。