NC207028 第k小数

思路

求第k小的数，第一时间就能想到和排序有关，但这个数据量用冒泡排序什么的肯定会很糟糕，所以用到了快速排序

在快速排序时，我们先选取一个基准值，然后把数组中所有比基准值小的数放到基准值左边，比基准值大的数放到基准值右边，等于基准值的数任意放在哪一边。
每一次完成这样的操作以后，我们根据k和基准值的大小关系，选取左区间或右区间递归，直到区间里只剩一个数，那就是我们要的第k小数

代码

#include <iostream>

using namespace std;
int num[5000005];

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

int deal(int left, int right, int k) {
    //如果left和right相等，说明只剩第k小的数
    if (left == right)return num[k];
    int lPtr = left;
    int rPtr = right;
    //选区间中间的值为基准值进行快速排序
    int pivot = num[(left + right) >> 1];
    while (lPtr <= rPtr) {
        while (num[lPtr] < pivot)lPtr++;
        while (num[rPtr] > pivot)rPtr--;
        if (lPtr <= rPtr) {
            swap(num[lPtr], num[rPtr]);
            lPtr++;
            rPtr--;
        }
    }
    //运行完上面的循环以后rPtr在lPtr的左边
    //根据k的位置选择区间递归
    if (k <= rPtr)return deal(left, rPtr, k);
    return deal(lPtr, right, k);
}

int main() {
    int T;  //数据组数
    T = read();
    int n;  //数列长度
    int k;  //求第k小的数
    while (T-- > 0) {
        n = read();
        k = read();
        for (int i = 0; i < n; ++i) {
            num[i] = read();
        }
        cout << deal(0, n, k) << endl;
    }

}