寻找第k小的数

给定若干整数，请设计一个高效的算法，确定第k小的数。

输入格式:

测试数据有多组，处理到文件尾。每组测试数据的第1行输入2个整数n，k（1≤k≤n≤1000000）。第2行输入n个整数，每个数据的取值范围在0到1000000之间。

输出格式:

对于每组测试，输出第k小的数。

输入样例:

5 3
1 2 2 2 1
9 3
1 2 3 4 5 6 9 8 7

输出样例:

2
3

提示:

如果提交后超时，请注意需要设计的是高效的算法！如果你初学《数据结构》，暂时设计不出来，请学完相关知识再回头来做。
也可以使用STL之sort、nth_element函数求解。
另外，由于输入数据特别多，为减少输入数据的耗时，建议使用以下的输入外挂函数：

void scan_d(int &num)    
{
        char in;
        in=getchar();
        while(in<'0'||in>'9') in=getchar(); 
        num=in-'0';
        while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}
}

调用方法如下：

int n;
scan_d(n);

//这题也算是投机取巧，此前也会超时，把cin换成scanf就可以了 

 #include
using namespace std;
int main(){
    int n,k,i;
    while(cin>>n>>k){
        int a[1000005];
        for(i=0;i         sort(a,a+n);
        cout<     }
    return 0;
}