快速选择算法

基础递归式解法 $O(n)$

C++ 代码

#include <iostream>
#include <vector>

using namespace std;

int QuickSelect(vector<int> &nums, int lo, int hi, int k){ //保证k一定在[lo, hi]区间内
    if(lo == hi) return nums[lo];
    int pivot = nums[lo], i = lo, j = hi;
    while(i < j){
        while(i < j && nums[j] >= pivot) --j; nums[i] = nums[j];
        while(i < j && nums[i] <= pivot) ++i; nums[j] = nums[i];
    }
    nums[i] = pivot;
    return k <= i ? QuickSelect(nums, lo, i, k) : QuickSelect(nums, i + 1, hi, k);
}

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> nums(n);
    for(int i = 0; i < n; ++i) cin >> nums[i];
    cout << QuickSelect(nums, 0, n - 1, k - 1) << endl;
    return 0;
}

快排变种递归式解法 $O(n)$

C++ 代码

#include <iostream>
#include <vector>

using namespace std;

int QuickSelect(vector<int> &nums, int lo, int hi, int k){ //保证k一定在[lo, hi]区间内
    if(lo == hi) return nums[lo];
    int mi = lo, pivot = nums[lo];
    for(int i = lo + 1; i <= hi; ++i){
        if(nums[i] < pivot) swap(nums[++mi], nums[i]);
    }
    swap(nums[lo], nums[mi]);
    return k <= mi ? QuickSelect(nums, lo, mi, k) : QuickSelect(nums, mi + 1, hi, k); 
}

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> nums(n);
    for(int i = 0; i < n; ++i) cin >> nums[i];
    cout << QuickSelect(nums, 0, n - 1, k - 1) << endl;
    return 0;
}

迭代式解法 $O(n)$

C++ 代码

#include <iostream>
#include <vector>

using namespace std;

int QuickSelect(vector<int> &nums, int k){
    for(int lo = 0, hi = nums.size() - 1; lo < hi;){
        int i = lo, j = hi, pivot = nums[lo];
        while(i < j){
            while(i < j && nums[j] >= pivot) --j; nums[i] = nums[j];
            while(i < j && nums[i] <= pivot) ++i; nums[j] = nums[i];
        }
        nums[i] = pivot;
        if(i <= k) lo = i + 1;
        if(i >= k) hi = i - 1;
    }
    return nums[k];
}

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> nums(n);
    for(int i = 0; i < n; ++i) cin >> nums[i];
    cout << QuickSelect(nums, k - 1) << endl;
    return 0;
}