c语言快速排序和二分查找模型

柔情只为你懂 2022-08-02 05:40 150阅读 0赞

引言：

c语言中   stdlib   自定义了一个 qsort 快速排序函数

模型：

int cmp(const void \*a,const void \*b);

qsort(s,n,sizeof(s\[0\]),cmp);

示例代码：

//
    #include<stdio.h>
    #include<stdlib.h>
    
    int cmp(const void* a, const void* b)
    {
        return  *((int*)a) - *((int*)b);
    }
    
    //浜屽垎鏌ユ壘绠楁硶
    int search(int* arr, int arr_len, int value)
    {
       int  index = 0;
       int  min = 0;
       int  max = arr_len -1;
       int  middle = 0;
       if(arr[min] == value)
            return min;
       else if (arr[max] == value)
            return max;
    
       while(min < max)
       {
          middle = (min + max)/2;
          if(arr[middle] > value)
               max = middle -1;
          else if(arr[middle] < value)
    	   min = middle + 1;
          else 
    	   return middle;
       }
    
    }
    
    int main()
    {
        int a[] = {5,4,1,3,10,6,22,98,76,35};
         qsort(a, sizeof(a)/sizeof(int), sizeof(int), cmp);
        int i =0;
        for(i; i< sizeof(a)/sizeof(int); i++)
         printf(" %2d, ", a[i]);
        printf(" \n");
    
        int  index = search(a, sizeof(a)/sizeof(int), 35);
        printf("index=%d, num=%d\n", index, a[index]);
    }

//结构体的 快速排序

#include<stdio.h>
    #include<string.h>
    
    typedef unsigned int uint32_t;
    typedef char         uint8_t;
    typedef unsigned short uint16_t;
    
    typedef struct _BOOK{
            char name[32];
            int price;
    
    }Book;
    
    
    typedef struct _YOUXI{
      int num;
      Book book[4];
    }YouXi;
    
    int   cmp(void* a, void* b)
    {
        return ((YouXi*)a)->num - ((YouXi*)b)->num;
    }
    
    int  main()
    {
    
            YouXi  you[4] = {
       {1,{"luchenfei", 32}}, {4,{"chunchun", 37}}, {3,{"lili", 39}}, {2,{"mingming", 34}}};
            int i =0;
            for(i; i<4 ;i++)
            {
                    printf("num=%d, name=%s, price=%d\n", you[i].num, you[i].book->name, you[i].book->price);
            }
    #if 1
            qsort(you, 4, sizeof(YouXi), cmp);
    
            i =0;
            for(i; i<4 ;i++)
            {
                    printf("num=%d, name=%s, price=%d\n", you[i].num, you[i].book->name, you[i].book->price);
            }
    #endif
    }

结束语：

二分查找 + 快速 排序   在 具体应用时候 还是很不错一个 算法， 比如 解析 地理信息库， ip段 和 地址的映射 关系， 用ip 的开始ip 快排， 然后在 用二分  去查找。。

：关于 qsort c语言的 不同类型 double， 结构体 ， 字符串 排序 参见博客：  http://blog.sina.com.cn/s/blog\_5155e8d401009145.html