线形时间选择.cpp

2

#include<iostream.h>
int Partition (int a[],int ,int );
void QuickSort(int a[],int ,int );
int Partition (int a[],int ,int ,int);
void Swap(int &,int &);
# define M 50
void main()
{
	int i,a[M],n,p,r,m;
	int Select(int a[],int,int,int);
    cout<<"请输入序列的长度n"<<endl;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cout<<"请输入序列数"<<endl;
		cin>>a[i];
	}
	cout<<"请输入查询的范围p和r"<<endl;
	cin>>p>>r;
	cout<<"请输入查询第几大的数m"<<endl;
	cin>>m;
  cout<<"数为"<<Select(a,p,r,m);
}
int Select(int a[],int p,int r,int k)
{
		if((r-p+1)<k)
		{
			cout<<"数据输入错误"<<endl;
			return 0;
		}
	if(r-p<5){
		QuickSort(a,p,r);
		return a[p+k-1];
	}
	for(int i=0;i<=(r-p-4)/5;i++)
	{
		QuickSort(a,p+5*i,p+5*i+4);
		int temp;
		temp=a[p+i];
	    a[p+i]=a[p+5*i+2];
        a[p+5*i+2]=temp;
	}
	int  x;
	x=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);
    i =Partition(a,p,r,x);
	int j=i-p+1;
	if(k<=j) return Select(a,p,i,k);
	else return Select(a,i+1,r,k-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 Partition (int a[],int p,int r)
{
int i=p,j=r+1;
int x=a[p];
while(true){
	while(a[++i]<x);
	while(a[--j]>x);
	if(i>=j) break;
	Swap(a[i],a[j]);
}
a[p]=a[j];
a[j]=x;
return j;
}
int Partition (int a[],int p,int r,int x)
{
int i=p,j=r+1;
while(true){
	while(a[++i]<x);
	while(a[--j]>x);
	if(i>=j) break;
	Swap(a[i],a[j]);
}
a[p]=a[j];
a[j]=x;
return j;
}
void Swap(int &x,int &y)
{
int temp=x;
    x=y;
   y=temp;
}