1 /*
  2 本代码描述:
  3 
  4     随机生成10000位数，进行快速排序后，
  5 用二分查找法定位到某个要查询的数
  6 （键盘输入某个要查询的数），
  7   结果输出查询的时间，以及是否查到
  8   
  9   */
 10 #define N 10000
 11 #include<stdio.h>
 12 #include<stdlib.h>
 13 #include<time.h>    //因为后面要用到time()函数来返回当前时间来做随机数种子
 14 
 15 //这个快速排序的其中一个返回轴值的函数
 16 int Partition(int a[],int first,int end)       
 17 {
 18     int i;
 19     int j;
 20     int temp;
 21     i = first , j = end;            /*默认轴值位a[0]，即最左侧的a[i]*/
 22 
 23     while(i<j)                        /* 当i不等于j时此次循环一直执行下去*/
 24     {
 25         while(i<j && a[i]<=a[j])     /*先从右侧往左侧开始扫描*/
 26         {
 27             j--;                    /* 直到右侧j值不大于左侧的i值*/
 28         }
 29         if(i<j)
 30         {
 31             temp = a[i];
 32             a[i] = a[j];
 33             a[j] = temp;
 34             i++;                    /*交换位置后另外一方的坐标值自增1*/
 35         }
 36 
 37         while(i<j && a[i] <= a[j])    /*从左侧开始往右侧扫描*/    
 38         {
 39             i++;
 40         }
 41         if(i<j)
 42         {
 43             temp = a[i];
 44             a[i] = a[j];
 45             a[j] = temp;
 46             j--;
 47         }                            
 48     }
 49     return i ;                    /*直到i==j，返回本次轴值*/
 50 }
 51 
 52 
 53 //这个快速排序的其中一个拆分的函数
 54 void QuickSort(int a[],int first,int end)
 55 {
 56     int pivot;                 //记录轴值
 57     if(first<end)
 58     {
 59         pivot = Partition(a,first,end);
 60         QuickSort(a,first,pivot-1);
 61         QuickSort(a,pivot+1,end);
 62     }
 63 }
 64 
 65 //二分法
 66 int Search(int a[],int target,int low,int high)  //传入a[]升序数组与要查找的目标target和数组的首末位置
 67 {                                            
 68     int middle;
 69             
 70     middle  = (low+high)/2;      //初始化结束
 71 
 72     while( high >= low)        //二分查找现在开始，奏国歌，升国旗，敬礼
 73     {
 74         
 75 
 76         if(target > a[middle])
 77         {
 78             low = middle +1;    
 79             //  middle = (low+high)/2;  此代码会影响下面的a[middle]的判断 所以出错 
 80         }
 81         else if(target < a[middle])
 82         {
 83             high = middle - 1;        
 84             // middle = (low+high)/2;   删除此行以及上面一行代码。
 85         }
 86         else                  //此处else为 target == a[middle]
 87         {
 88             return (middle + 1);    //此处时关键，找到目标跳出循环并返回目标i                         
 89         }
 90         middle = (high + low) /2;
 91     }
 92     return -1;              //-1为没有找到目标值
 93 }
 94 
 95 
 96 void main()
 97 {
 98     int a[N] = {0};
 99     int i = 0;
100     int k,target;
101     clock_t begin,end;
102     srand((time(NULL))); //以系统时间为随机种子
103     
104 
105     begin = clock(); 
106     for(i = 0;i < N ;i++)      //随机赋值为数组a[10000]来了
107     {
108         a[i] = rand();        
109     }
110     end = clock();
111     printf("随机数赋值所用时间为:%f s\n",(double)(end - begin)/CLOCKS_PER_SEC);
112     printf("\n");
113 
114     begin = clock();         //快速排序
115     QuickSort(a,0,N-1);
116     end = clock();
117     printf("快速排序所用的时间为:%f s\n",(double)(end - begin)/CLOCKS_PER_SEC);
118     printf("\n");
119 
120     printf("排序后的第1234位为%d:\n\n",a[1233]);          //以第1233位为检测点
121     
122 
123     printf("第1230到1240位数字为:\n");
124     for(i=1229;i<1240;i++)
125         printf("%d ",a[i]);
126     printf("\n");
127     
128     printf("\n");
129     printf("输入所要查询的数:");        
130     scanf("%d",&target);
131 
132     begin = clock();        //二分法查找所需目标
133     k = Search(a,target,0,N-1);
134     if(k!=-1)
135     {
136         printf("%d已经找到，在第%d位\n",target,k);
137     }
138     else
139     {
140         printf("很遗憾没有找到！");
141     }
142     end = clock();
143     printf("本次查询%d所用的时间:%f s\n",target,(double)(end - begin)/CLOCKS_PER_SEC);
144     printf("\n");
145 
146 
147 
148     system("pause");
149     
150 }