|
常用链接
留言簿(4)
随笔分类
随笔档案
搜索
最新评论

阅读排行榜
评论排行榜
Powered by: 博客园
模板提供:沪江博客
|
|
|
|
|
发新文章 |
|
|
经典的快速排序和二分查找
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;

int Partition(int a[],int p,int r)
  {
int ran=rand()%(r-p+1)+p; //随即选取卫兵
swap(a[ran],a[r]);
int x=a[r];
int i=p-1;
for (int j=p;j<r;j++)
 {
if (a[j]<=x) //小于卫兵的值进行对换
 {
i++;
swap(a[i],a[j]);
}
}
swap(a[i+1],a[r]);
return i+1;
}

void QuickSort(int a[],int p,int r)
  {
int q;
if (p<r)
 {
q=Partition(a,p,r);
QuickSort(a,p,q-1);
QuickSort(a,q+1,r);
}
}

int BinarySearch(int a[],int min,int max,int x)
  {
int mid;
while (min<max)
 {
mid=min+(max-min)/2;
if (a[mid]>=x)
max=mid;
else
min=mid+1; //若不加一可能存在无限循环的结果
}
if (a[min]==x)
return min;
else if(a[max]==x)
return max;
else
return -1;
}
void main()
  {
int num;
cin>>num;
int* a = new int[num];
cout<<"排序前:"<<endl;
for(int i=0;i<num;i++)
cin>>a[i];
QuickSort(a,0,num-1);
cout<<"排序后:"<<endl;
for (int j=0;j<num;j++)
 {
cout<<a[j]<<endl;
}
cout<<"输入要查找的数"<<endl;
int x;
cin>>x;
int result=BinarySearch(a,0,num-1,x);
if (result>=0)
cout<<"目标位置为:"<<result+1<<endl;
else
cout<<"目标不在数组中"<<endl;
}

|
|