min_k.cpp

从文件中读取一定量的数据

#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
void quicksort(int A[],int left,int right){//nlogn
	int i,j;
	if(left<right){
		i=left;
		j=right;
		A[0]=A[i];
		do{
			while(A[j]>A[0] && i<j)
				j--;
			if(i<j){
				A[i]=A[j];
				i++;
			}
			while(A[i]<A[0] && i<j) 
				i++;
			if(i<j){
				A[j]=A[i];
				j--;
			}
		}while(i!=j);
		A[i]=A[0];
		quicksort(A,left,i-1);
		quicksort(A,i+1,right);
	}
}

int select(int B[],int low,int high,int k){
	int p=high-low+1;//log1
	int *A=new int[p+1];
	for(int w=1;w<=p;w++)
		A[w]=B[w];
	if(p<44){
		quicksort(A,low,high);//nlogn
			return A[k];
	}
	else{
		int q=p/5;//log1

		int *M=new int[q+1];		
	/*	int *N=new int[5];
		for(int i=1;i<=q;i++)
		{
			for(int j=1;j<=5;j++)
			{
				N[j]=A[(i-1)*5+j];

			}
			quicksort(N,1,5);
			M[i]=N[3];

		}*/

	for(int i=1;i<=q*5;i+=5)//logn
			quicksort(A,i,i+4);
	//	int *M=new int[q+1];
		for(i=1;i<=q;i++)//log(n/5)
			M[i]=A[5*i-2];

		int mm=select(M,1,q,q/2+1);//T(n/5)
		int *A1=new int[p+1];
		int *A2=new int[p+1];
		int *A3=new int[p+1];
		int n1=0,n2=0,n3=0;
		for(int j=1;j<=p;j++){//logn   
			if(B[j]<mm)	
				A1[++n1]=B[j];
			else if(B[j]==mm)
				A2[++n2]=B[j];
			else if(B[j]>mm)
				A3[++n3]=B[j];


		}
		if(n1>=k)
			return select(A1,1,n1,k);
		if(n1+n2>=k)
			return mm;
		if(n1+n2<k)
			return select(A3,1,n3,k-n1-n2);
	}	

}


int main(){
	int n,K,x;
	char ch;
	ifstream in;
	do{
		cout<<"请输入数组元素个数：n=";
		cin>>n;
		int *a=new int[n+1];

		cout<<"数组元素为："<<endl;
		in.open("data.txt");
		for(int i=1;i<=n;i++){
			in>>a[i];
			cout<<setw(4)<<a[i]<<" ";
			if(i%10==0)
				cout<<endl;
		}
		in.close();
		cout<<endl;
		do{
			cout<<"请输入一个整数K(K<="<<n<<"):"<<endl;
			cin>>K;
		}while(K>n||K<=0);
		cout<<"数组中的前"<<K<<"个最小元素为："<<endl;
		x=select(a,1,n,K);
		int m=1,j=0;
		in.open("data.txt");
		int value;
		while(in>>value&&m<=n){
			if(value<=x){
				cout<<setw(4)<<value<<" ";
				j++;
				if(j%10==0)
					cout<<endl;
			}
			m++;
		}
		in.close();		
		cout<<endl;
		cout<<"其中第"<<K<<"小元素为："<<x<<endl;
		cout<<"是否继续(y/n)?"<<endl;
		cin>>ch;
	}while(ch=='y');
	
	return 0;
}