acwing786，第k小数，快速查找（快排思想）

int quick_sort(int q[], int l, int r, int k)//第k小快速查找时间复杂度一般为2N，o(N)级；数组，左边，右边，第k小 
{
    if (l >= r) return q[l];//只剩一个数，找到了 

    int i = l - 1, j = r + 1, x = q[l + r >> 1];//i j事先前推一格是为了下面while先加，先加而不是后加的好处就是退出来的时候i j就是错一位或同的i j 
    while (i < j)
    {
        while (q[++i] < x);
        while (q[--j] > x);
        if (i < j) swap(q[i], q[j]);//如果i j没相遇就优雅地调换两个不顺序数的位置 
    }

    if (j >= k) return quick_sort(q, l, j, k);//如果左区域最大能包k，那k就在左区域 
    else return quick_sort(q, j + 1, r, k);//否则就在右区域 
}

#include <iostream>

using namespace std;

const int N = 100010;

int q[N];

int quick_sort(int q[], int l, int r, int k)//数组，左边，右边，第k小 
{
    if (l >= r) return q[l];//只剩一个数，找到了 

    int i = l - 1, j = r + 1, x = q[l + r >> 1];//i j事先前推一格是为了下面while先加，先加而不是后加的好处就是退出来的时候i j就是错一位或同的i j 
    while (i < j)
    {
        while (q[++i] < x);
        while (q[--j] > x);
        if (i < j) swap(q[i], q[j]);//如果i j没相遇就优雅地调换两个不顺序数的位置 
    }

    if (j >= k) return quick_sort(q, l, j, k);//如果左区域最大能包k，那k就在左区域 
    else return quick_sort(q, j + 1, r, k);//否则就在右区域 
}

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);

    for (int i = 1; i <= n; i ++ ) scanf("%d", &q[i]);//输入数组 

    cout << quick_sort(q, 1, n, k) << endl;//数组，左边，右边，第k小 

    return 0;
}