/*P186 (9)利用分治法求一组数据中最大的两个数和最小的两个数,具体算法可参照P150*/
#include<stdio.h>


int Swap(int x,int y){
	int t;
	t=x;
	x=y;
	y=t;
}


int select(int a[],int left,int right,int k){
	int i,j,pivot;
	if(left>=right){
		return a[left];
	}//
	pivot=a[left];
	i=left+1;
	j=right;
	while(1){
		do{
			i++;
		}while(a[i]<pivot);
		do{
			j--;
		}while(a[j]>pivot);
		if(i>=j){
			break;
		}
		Swap(a[i],a[j]);
	}
	if((j+1)==k){
		return pivot;
	}
	a[left]=a[j];
	a[j]=pivot;
	if(j+1<k){
		return select(a,j+1,right,k-j-1);
	}
	else{
		return select(a,left,j-1,k);
	}
} 


int xzwt(int a[],int n,int k){
	if(k<1||k>n){
		return 0;
	}
	return select(a,0,n-1,k);
}


int main(){
	int n,a[100],i,k,b[4],m;
	printf("输入你数据数量：\n");
	scanf("%d",&n);
	printf("输入一串数字：\n");
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	printf("输入你要选择的第k大的4个数字：\n");
	for(i=0;i<4;i++){	
		scanf("%d",&b[i]);
	}
	m=xzwt(a,n,b[2]);	
	printf("第%d大的数字为：%d\n",b[2],m); 
	m=xzwt(a,n,b[3]);	
	printf("第%d大的数字为：%d\n",b[3],m); 
	m=xzwt(a,n,b[0]);	
	printf("第%d大的数字为：%d\n",b[0],m); 
	m=xzwt(a,n,b[1]);	
	printf("第%d大的数字为：%d\n",b[1],m); 
	
	
}