刚刚完成师兄给的一道题目:
随机生成10000位数，进行快速排序后，用二分查找法定位到某个要查询的数（键盘输入某个要查询的数）， 结果输出查询的时间，以及是否查到
分享下自己的解题思路:
1，要懂得如何随机生成数
2，要了解快速排序以及二分法思想
3，要直到如何测试出程序运行时间
下面是自己写的代码，欢迎各位提出宝贵的意见以及见解，小生感激不尽
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 else139 {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 }
你不能左右天气，但你能转变你的心情
