转载

二分法查找和快速排序

二分法是分治算法的一种特殊形式，利用分治策略求解时，所需时间取决于分解后子问题的个数、子问题的规模大小等因素，而二分法，由于其划分的简单和均匀的特点，是查找数据时经常采用的一种有效的方法。

快速排序的实质也是二分法，下面就写一个快速排序＋二分法查找的栗子:chestnut:：

1 #include<stdio.h>   2    3    4 //快速排序   5 void QuickSort(int * a,int left,int right)   6 {   7     if(left>right)   8     {   9         return;  10     }  11     int stand=a[left];  12     int i=left;  13     int j=right;  14     //得到基准数位置  15     while(i!=j)  16     {  17         while(i<j&&a[j]>=stand)  18         {  19             --j;  20         }  21         while(i<j&&a[i]<=stand)  22         {  23             ++i;  24         }  25         if(i<j)  26         {  27             int temp=a[i];  28             a[i]=a[j];  29             a[j]=temp;  30         }  31     }  32     //将基准数放入找出的位置  33     a[left]=a[i];  34     a[i]=stand;  35     //递归  36     QuickSort(a,left,i-1);  37     QuickSort(a,i+1,right);  38     return;  39 }  40   41   42 //递归实现二分法查找  43 int BinarySearch(int * a,int key,int low,int high)  44 {  45     if(low>high||key<a[low]||key>a[high])        //越界处理  46     {  47         return -1;  48     }  49     int middle=(low+high)/2;  50     if(key==a[middle])  51     {  52         return middle;  53     }  54     if(middle==low||middle==high)  55     {  56         if(key==a[low])  57         {  58             return low;  59         }  60         if(key==a[high])  61         {  62             return high;  63         }  64         else  65         {  66             return -1;  67         }  68     }  69     if(key<a[middle])  70     {  71         return BinarySearch(a,key,low,middle);  72     }  73     if(key>a[middle])  74     {  75         return BinarySearch(a,key,middle,high);  76     }  77 }  78   79 //循环实现二分法查找  80 int BinarySearchByCircle(int * a,int key,int high)  81 {  82     int low=0;  83     int middle;  84     while(high>=low)  85     {  86         middle=(high+low)/2;  87         if(key==a[middle])  88         {  89             return middle;  90         }  91         if(key<a[middle])  92         {  93             high=middle-1;  94         }  95         if(key>a[middle])  96         {  97             low=middle+1;  98         }  99     } 100     return -1; 101 } 102  103 int main() 104 { 105     int a[]={5,23,5,7,1}; 106     printf("----------------快速排序--------------/n"); 107     QuickSort(a,0,4); 108     for(int i=0;i<5;i++) 109     { 110         printf("%d/n",a[i]); 111     } 112     printf("/n---------------非递归二分法查找元素5的位置-----------------/n"); 113     printf("%d/n",BinarySearchByCircle(a,5,4)); 114     printf("/n---------------递归二分法查找元素5的位置------------------/n"); 115     printf("%d/n",BinarySearch(a,5,0,4)); 116     return 0; 117 }

运行结果为：

二分法查找和快速排序