怀旧书本
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int a[N];
int n, k;

int quick_sort(int l, int r, int k) {
    if (l == r) return a[l];
    int i = l - 1, j = r + 1, m = a[l + r >> 1];
    while (i < j) {
        while (a[++i] < m);
        while (a[--j] > m);
        if (i < j) swap(a[i], a[j]);
    }
    
    int lcnt = j - l + 1;
    if (lcnt >= k) {
        return quick_sort(l, j, k);
    } else {
        return quick_sort(j + 1, r, k - lcnt);
    }
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    cout << quick_sort(0, n - 1, k) << endl;
    
    return 0;
    
}
本文为原创文章,欢迎分享,勿全文转载,如果内容你实在喜欢,可以加入收藏夹,说不定哪天故事又继续更新了呢。
本文地址:https://qoogle.top/quick-select/
最后修改日期:2020年4月30日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。