题解：

quick sort三部曲

核心思想:
分治, 先找到一个分界点，然后分区使得左分区 left <= x, 右分区 right >= x, 然后递归处理左右分区
（注意：分区后，分界点x并不一定在左右分区的边界上，并且左右分区也是无序的）

step1: 选择分界点x, 一般选择 q[l], q[l+r>>1], q[r]
step2: 分区，使得左右分区 left<=x, right >=x
step3: 对左右分区递归调用

但是对于快速选择算法：
step2当中：左边sl, 右边sr
如果k <= sl, 递归左分区
如果k > sl, 递归右分区

时间复杂度O(n)

第一层：O(n)
第二层：O(n/2)
第三层：O(n/4)
…
总的时间复杂度O = n(1 + 1/2 + 1/4 + 1/8 + …) = O(2n)

c语言

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int q[N];

int quick_sort(int q[], int l, int r, int k)
{
    if(l >= r) return q[l];

    int x = q[(l+r)>>1], 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]);
    }

    if(j - l + 1 >= k) return quick_sort(q, l, j, k);
    else return quick_sort(q, j + 1, r, k - (j-l+1));
}

int main()
{
    int n, k;
    cin >> n >> k;

    for(int i = 0; i < n; i++) cin >> q[i];

    cout << quick_sort(q, 0, n - 1, k);

    return 0;
}