!select.cpp

顺序统计select算法。从s个元素中找出第k个大的元素。

#include <iostream>
int a[200];
int s;
int k;
void sort(int a[],int s)  
{	
	int t,j,i;
	for(i=0;i<(s-1);i++)
		for(j=i+1;j<s;j++)
			if (a[i]>a[j]){
				t=a[i];a[i]=a[j];a[j]=t;
			}    

}
int select2 (int k,int d[],int S)
{
	if (S<10)
	{
		sort(d,S);

		return(d[k]);
	}
	else
	{
		int w=d[9];
		int d1[200],d2[200],d3[200];
		int t1=0,t2=0,t3=0;
		for (int i=0;i<S;i++)
		{
			if (d[i]<w)
			{
				d1[t1++]=d[i];		      
			}
			else
			{
				if (d[i]==w)
				{
					d2[t2++]=d[i];				  
				}
				else
				{
					d3[t3++]=d[i];				   
				}
			}
		}

		if (t1>=k) return (select2(k,d1,t1));
		else
		{
			if (t1+t2>=k) return (w);
			else return (select2(k-t1-t2,d3,t3));
		}
	}
}
 
 void main()
{
	std::cout<<"产生s个随机数（输入s）：";
	std::cin>>s;
	int i;
	for (i=0;i<s;i++)  //产生随机数
	{
	a[i]=rand()*0.002;
	std::cout<<a[i]<<"\t";
	} 
    sort(a,s);
	std::cout<<"选出第k小的数（输入k）：";
	std::cin>>k;
    std::cout<<"\n";
	std::cout<<"第"<<k<<"个大的数是："<<select2((k-1),a,s)<<'\n';
	std::cout<<"\n";
	std::cout<<"检验……"<<"\n";
	std::cout<<"排序后为："<<"\n";	
	for(i=0;i<s;i++) 
    std::cout<<a[i]<<"\t";
}