实验内容

对乱序整数序列，先用快速排序按非减序排列，再进行二分查找，查找某个元素是否存在，若存在返回匹配的第一个下标位置（从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 && i<r);
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(p<r)
{
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(goal<a[middle]) high=middle-1;
else if(goal>a[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;
}

更多详细信息： 去学习