来自「排序算法」· 代码 · 共 59 行

#include<iostream.h>

int partition(int a[],int left,int right)
{
	int x=a[left];
	while(left<right)
	{
		while(left<right&&x<=a[right])
			right--;
		a[left]=a[right];
		while(left<right&&x>=a[left])
			left++;
		a[right]=a[left];
	}
	a[left]=x;
	return left;
}

void Quicksort(int a[],int left,int right)
{
	int pos;
	if(left>=right)return;
	pos=partition(a,left,right);
	Quicksort(a,left,pos-1);
	Quicksort(a,pos+1,right);
}
//折半查找
int BinarySearch(int a[],int n,int K)
{
	int l=0,r=n-1,m;
	while(l<=r)
	{
		m=(l+r)/2;
		if(a[m]==K)
		{
			cout<<"success!"<<endl;
			return m;
		}
		else if(a[m]<K)
			l=m+1;
		else
			r=m-1;
	}
	cout<<"fail!"<<endl;
	return -1;
}

void main()
{
	int a[10]={3,45,21,14,67,9,4,24,13,89};
	int i,j=2;
	Quicksort(a,0,9);
	for(int n=0;n<10;n++)
		cout<<a[n]<<' ';
	cout<<endl;
	i=BinarySearch(a,10,j);
	cout<<i<<endl;

}