cpp2.cpp

设计算法实现在一个具有在n各互不相同元素的数组A[1…n]中找出所有前k个最小元素的问题

#include "iostream.h"
void print(int a[],int m,int n)
{   for(int i=m;i<=n;i++)
		cout<<a[i]<<" ";
}
void sort(int a[],int low,int high)
{   int i,j,h,t;
	for(i=low;i<high;i++)
	{   h=i;
		for(j=i+1;j<=high;j++)
			if(a[j]<a[h])  h=j;
		if(h!=i)  {	t=a[h];	a[h]=a[i];	a[i]=t;	}
	}
}
void select(int a[],int low,int high,int k,int d)
{   int p=high-low+1;
	if(p<44)
	{   sort(a,low,high);
		if(d==1)  print(a,low,low+k-1);
	}
	else
	{   int mm,h1=0,h2=0,h3=0;
		int q=p/5;
		int *m=new int[q+1];
		int *a1=new int[high-low+2];
		int *a2=new int[high-low+2];
		int *a3=new int[high-low+2];
		for(int i=1;i<=q;i=i++)
		{   sort(a,(i-1)*5+1,(i-1)*5+5);
			m[i]=a[(((i-1)*5+1)+((i-1)*5+5))/2];
		}
		select(m,1,q,(q+1)/2,0);
		mm=m[(q+1)/2];
		for(int j=low;j<=high;j++)
		{   if(a[j]<mm)        { h1++;	a1[h1]=a[j]; }
			else if(a[j]==mm)  { h2++;	a2[h2]=a[j]; }
			else if(a[j]>mm)   { h3++;	a3[h3]=a[j]; }
		}
		if(h1>=k)   select(a1,1,h1,k,1);
		else if(h1+h2<k)
		{   sort(a1,1,h1); print(a1,1,h1);
			sort(a2,1,h2); print(a2,1,h2);
			select(a3,1,h3,k-h1-h2,1);
		}
		else if(h1+h2>=k)
		{   sort(a1,1,h1); print(a1,1,h1);
			sort(a2,1,h2); print(a2,1,h2);
		}
	}
}
void main()
{   int n,k,d=1,s;
	cin>>s;
	for(int j=1;j<=s;j++)
	{   cin>>n; 		
		int *a=new int[n+1];
		for(int i=1;i<=n;i++)
			cin>>a[i];
		cin>>k;
		select(a,1,n,k,d);
		cout<<endl;
		if(j!=s)
			cout<<endl;
	}
}