问题描述：
给定一个n个元素序列（乱序），在线性时间内（O（n））找出其中第k大的元素（1<=k<=n）；
(输入元素均为double型数据)
输入说明：
第一行输入一个正整数n；
第二行输入n个double型数据代表整个序列；
第三个输入需要查找的第search大的数据（1<=search<=n）;
输出说明：
输出这个序列中第search大的元素即可；
input_case1:
6
0.2 3.6 9.6 -1 0 44
4
output_case1:
3.6
input_case2:
10
1.2 0.66 0.99 99.5 -100 20 32.5 44.3 3.12 10.3
6
output_case2:
10.3
input_case3:
16
0.2 3.6 9.6 -1 0 44 1.2 0.66 0.99 99.5 -100 20 32.5 44.3 3.12 10.3
9
output_case3:
3.6

code：

#include<bits/stdc++.h>
using namespace std;

template<class T>
int Partition(T *a,int p,int r,T x){//一次快排的Parition函数 
	int i=p;
	int j=r+1;
	
	while(i<j){
		while(a[++i]<x&&i<r);
		while(a[--j]>x);
		if(i>=j)break;
		swap(a[i],a[j]);
	}
	a[p]=a[j];
	a[j]=x;
	return j;//返回放置的位置 
}

template<class T>
T Select(T *a,int p,int r,int k){//线性时间选择函数 
	if(r-p<=75){//小规模问题直接调用快排即可 
		sort(a,a+(r-p+1));
		return a[p+k-1];
	}else{//较大规模问题分治处理 
		for(int i=0;i<=(r-p-4)/5;i++){//分组排序（每组5个） 
			sort(a+p+4*i,a+(p+4*i+4));
			swap(a[p+i],a[p+4*i+2]);//将中位数调到前面 
		}
		
		T x=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);//x为中位数的中位数 
		int index=Partition(a,p,r,x);//调用一次快排函数 
		int j=index-p+1;//j为左边区间的元素个数 
		if(k>=j)return Select(a,index+1,r,k-j);//对应右区间 
		else Select(a,p,index,k);//对应左区间 
	}
}

int main(){
	
	int n;
	scanf("%d",&n);
	double a[n];
	for(int i=0;i<n;i++){
		scanf("%lf",&a[i]);
	}
	int search;//search代表第几个大的函数 
	cin>>search;
	double mid=Select(a,0,n-1,search);
	cout<<mid<<endl;
	return 0;
}