C++---快速选择（每日一道算法2023.4.8）-Toy模板网

这篇具有很好参考价值的文章主要介绍了C++---快速选择（每日一道算法2023.4.8）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

注意事项：
快速排序的一个拓展算法，建议先了解快排：快速排序—前后双指针法

题目：
给一个未排序的数列，列表中不包含重复元素，要求找到第k大的元素并输出。

输入格式
第一行两个整数，n，k，用空格隔开，分别表示序列长度和需要找到第k大的元素。
第二行有n个元素，用空格隔开，是序列中的所有元素。

输出格式
单个字符，输出序列中第k大的元素。

数据范围
0 < n < 10000；

输入:
10 6
5 3 2 1 4 7 6 9 8 10

输出：
6

#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 10010;
int x[N];
int n, k;

int quick_select(int a[], int l, int r, int k) {
    if (l >= r) {return a[k];}

    int mid = a[(l+r)/2], i = l-1, j = r+1;
    while (i < j) {
        while (a[++i] < mid);
        while (a[--j] > mid);
        if (i < j) swap(a[i], a[j]);
    }

    if (j >= k) {return quick_select(a, l, j, k);}
    else {return quick_select(a, j+1, r, k);}
}

int main() {
    cin >> n >> k;
    for (int i = 0; i<n; i++) cin >> x[i];
    cout << quick_select(x, 0, 9, k-1) << endl;
}