【C语言】乱序整数列快速排序二分查找【原创技术】.docVIP

实验内容 对乱序整数序列，先用快速排序按非减序排列，再进行二分查找，查找某个元素是否存在，若存在返回匹配的第一个下标位置（从0开始），不存在返回-1。 示例输入（第一行表示要查找的数，第二行以后表示数组元素，为编程方便，可限定为20个数，也可不限，自动分配空间）： 95 56 87 789 54 12 35 11 102 456 7821 2 44 245 56 879 45 82 57 62 30 示例输出（只输出数值即可，不许其他文字）： -1 提示： 分治法快速排序 第一步：分解 以aq为基准元素将ap:r划分成3段ap:q-1、aq和aq+1:r，使得ap:q-1中任何元素小于aq ，aq+1:r中任何元素大于aq ； 下标q在划分过程中确定。 第二步：递归求解 递归调用快速排序算法对ap:q-1和aq+1:r进行排序； 第三步：合并 对ap:q-1和aq+1:r的排序是就地进行的，ap:q-1和aq+1:r排好序后不需要执行任何计算，ap:r就已排好序。  源代码： //快速排序 + 二分查找 #include stdio.h int Partition(int a[],int p,int r) //对20个数进行划分，划分后进行快速排序{int i=p,j=r+1;int x=a[p];while(1){ while(a[++i]x ir);while(a[--j]x); if(i=j) break; int temp; //交换两个数的值temp=a[j];a[j]=a;a=temp;}a[p]=a[j];a[j]=x;return j;}void QuickSort(int a[],int p,int r) //进行快速排序{ if(pr){int q=Partition(a,p,r); QuickSort(a,p,q-1);QuickSort(a,q+1,r);}} int HalfSearch(int a[],int n,int goal) //定义二分查找函数{int high=n-1,low=0,middle;while (high=low) {middle=(high+low)/2;if(goala[middle]) high=middle-1; else if(goala[middle]) low=middle+1;else {return middle; }}return -1;} int main(){int i,goal,a[20]; scanf(%d,goal); //输入你要查找的数for (i=0;i20;i++) scanf(%d,a); //输入20个数 QuickSort(a,0,19); //调用快速排序函数，多20个数进行排序int search=HalfSearch(a,20,goal); //调用二分查找函数 printf(%d\n,search); //输出你要查找的数的情况return 0;}运行过程截图： 16 分钟前 上传 下载附件 (29.33 KB)  源代码下载： BinarySearch.cpp(1.28 KB, 下载次数: 0) 15 分钟前 上传 下载次数: 0  【C语言】分治法合并排序【原创技术】： 去学习 /forum.php?mod=viewthreadtid=1489