快速选择算法

快速排序的思想
1. 当区间为1时，要找的数一定在这个区间中
2. 选择一个x，做区间分界
3. 对区间进行调整
4. 由于left区间，严格小于right区间的（从分界线来看），可通过区间大小判断第k个数在哪个区间中
5. 递归

时间复杂度$O(n)$
1. 可近似看成每次处理$n, n / 2, n / 4, …$, 复杂度总和为$O(n)$
2. 函数中的k：指需要找的这个数是l～r这个区间中的第k个数

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e6 + 10;
int q[N];
int n, k;


int quick_select(int l, int r, int k) {
    if (l == r) return q[l];
    int x = q[l], i = l - 1, j = r + 1;  //可对x的选择进行调整，选择q[l],q[r],q[l+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 len = j - l + 1;
    if (k <= len) return quick_select(l, j, k);
    else return quick_select(j + 1, r, k - len);
}

int main() {
    int n;
    cin >> n >> k;
    for (int i = 0; i < n; i++) scanf("%d", q + i);
    cout << quick_select(0, n - 1, k) << endl;

    return 0;
}