给定若干整数，请设计一个高效的算法，确定第k小的数。测试数据有多组，处理到文件尾。每组测试数据的第1行输入2个整数n，k（1≤k≤n≤1000000）。第2行输入n个整数，每个数据的取值范围在0到1000000之间。对于每组测试，输出第k小的数。用c++编写代码，采用最快的算法

可以使用快速排序的思想，不过只需要对需要搜索的那一边继续递归下去，直到找到第k小的数为止。

具体实现可以参考以下代码：

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1000005;
int arr[MAXN];

int quick_select(int left, int right, int k) {
    if (left == right) return arr[left];
    int i = left, j = right, x = arr[left + (right - left) / 2];
    while (i <= j) {
        while (arr[i] < x) i++;
        while (arr[j] > x) j--;
        if (i <= j) {
            swap(arr[i], arr[j]);
            i++; j--;
        }
    }
    if (left + k - 1 <= j) return quick_select(left, j, k);
    if (left + k - 1 >= i) return quick_select(i, right, k - (i - left));
    return arr[j + 1];
}

int main() {
    int n, k;
    while (cin >> n >> k) {
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        cout << quick_select(0, n - 1, k) << endl;
    }
    return 0;
}