实验内容
对乱序整数序列，先用快速排序按非减序排列，再进行二分查找，查找某个元素是否存在，若存在返回匹配的第一个下标位置(从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
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); 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(p
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]) low=middle+1;else {return middle; }}return -1;}
int main(){int i,goal,a[20]; scanf("%d",&goal); //输入你要查找的数for (i=0;i<20;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=viewthread&tid=1489