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 }