回顾快速排序步骤：

1. 找到分界点x
2. 左边所有数小于等于x，右边所有数大于等于x
3. 左右递归排序

左边数量Sl，右边数量Sr

1. k < = Sl
   第k小的数一定在左边，递归左边
2. k > Sl
   第k小的数一定在右边，递归右边，k -> k - Sl

时间复杂度O(n)

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n, k;
int q[N];

int quick_sort(int l, int r, int k) {
    if (l >= r) return q[l];
    int x = q[(l + r) / 2], i = l - 1, j = r + 1;
    while (i < j) {
        do i ++; while (q[i] < x);
        do j --; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }

    int sl = j - l + 1;
    if (k <= sl) {
        return quick_sort(l, j, k);
    }
    else {
        return quick_sort(j + 1, r, k - sl);
    }
}

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