小W有很强的好胜心，也有很明确的目标，总是希望当第k名，但是小W太菜了，经常达不到目标，于是他每次考试后都想知道第k名的分数是多少，然后以它为目标。 现在给出了每个人的分数，请求编程能力很强的你帮他迅速找到第k名的分数为多少，这样他才有更多的时间去学习。
Input
第一行为一个正整数t代表有t组数据。每组数据第一行为两个正整数n和k，第二行为n个正整数。 1?<?=k?<?=n?<?=107
Output
对于每组数据，输出第k大的数
Sample Input
1
6 2
1 2 3 4 5 6
Sample Output
5注意：这个题目我提交了不下十遍，每次都是以2000ms+的时间打回，对于时间复杂度O(n*log(n))时间（即使在快读的情况下）超过了3000ms+，十分疑惑；
以下代码都是超时的：
代码一：3204ms
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
const int maxa=1e7+10;
int n,ans;
int a[maxa];
int main(){int t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&ans);for(int i=0;i<n;i++)scanf("%d",&a[i]);sort(a,a+n);printf("%d\n",a[n-ans]);}
}代码二：快读+2136ms
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
const int maxa=1e7+10;
int n,k;
int a[maxa];
bool cmp(int a,int b){return a>=b;
}
void read(int &x){x=0;bool f=0;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') f=1;ch=getchar();}while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}x=f?(~x)+1:x;
}
int main(){int t;read(t);while(t--){read(n);read(k);for(int i=1;i<=n;i++)read(a[i]);sort(a+1,a+1+n,cmp);printf("%d\n",a[k]);}
}代码三：快读+nth_element+2696ms
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
const int maxa=1e7+10;
int n,k;
int a[maxa];
void read(int &x){x=0;bool f=0;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') f=1;ch=getchar();}while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}x=f?(~x)+1:x;
}
int main(){int t;read(t);while(t--){read(n);read(k);k=n-k;for(int i=0;i<n;i++)read(a[i]);nth_element(a,a+k,a+n);//a[k]>之前的数字，a[k]<之前的数字 printf("%d\n",a[k]);}
}代码四：快排+快读+2204ms;
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int k;
int a[10000005];
void read(int &x){x=0;bool f=0;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') f=1;ch=getchar();}while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}x=f?(~x)+1:x;
}
int partition(int l,int r,int a[]){int key=a[l],index=l;for(int i=l+1;i<r;i++)if(a[i]<key){index++;swap(a[index],a[i]);}swap(a[l],a[index]);return index;
}
void quickSort(int l, int r, int a[]){if(l<r){int mid=partition(l,r,a);if(k>=l&&k<=mid-1) quickSort(l,mid-1,a);else quickSort(mid+1,r,a);}
}
int main(){int t,n;scanf("%d",&t);while(t--){scanf("%d%d",&n,&k);k=n-k;for(int i=0;i<n;i++)scanf("%d",&a[i]);quickSort(0,n,a);printf("%d\n",a[k]);}return 0;
}代码五：非有序数组查找+快读+1998ms;
参考模板：https://mp.csdn.net/console/editor/html/106185358
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
const int maxa=1e7+10;
ll n,k;
ll a[maxa];
void read(ll &x){x=0;bool f=0;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') f=1;ch=getchar();}while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}x=f?(~x)+1:x;
}
ll search(ll left,ll right){ll ans=-1;while(left<=right){int w=rand()%(right-left+1)+left;swap(a[left],a[w]);ll temp=a[left],tleft=left,tright=right;while(tleft<tright){while(tleft<tright&&a[tright]>=temp) tright--;a[tleft]=a[tright];while(tleft<tright&&a[tleft]<=temp) tleft++;a[tright]=a[tleft];}a[tleft]=temp;if(tleft==k){ ans=a[tleft];break;}else if(tleft>k) right=tleft-1;else left=tleft+1;}return ans;
}
int main(){ll t;read(t);while(t--){ read(n);read(k);k=n-k+1;for(ll i=1;i<=n;i++)read(a[i]);printf("%lld\n",search(1,n)); }
}老哥们，救济孩子吧！！！