题目描述
给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。
输入格式
第一行包含两个整数 n 和 k。
第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整数数列。
算法
- 找到分界点x，三种划分方式：q[L]，q[(L + R) >> 1]，q[R]
- 左边所有数Left <= x，右边所有数Right >= x
- 递归排序Left，递归排序Right
代码
点击查看代码
#include<iostream>
using namespace std;
const int N = 100010;
int n, k;
int q[N];
int quick_sort(int l, int r, int k){
if(l == r) return q[l];
int x = q[l], i = l - 1, j = r + 1;
while(i < j){
while(q[++i] < x);
while(q[--j] > x);
if(i < j) swap(q[i], q[j]);
}
int sl = j - l + 1;
if(sl >= k) return quick_sort(l, j, k);
return quick_sort(j + 1, r, k - sl);
}
int main(){
cin >> n >> k;
for(int i = 0; i < n; i++){
cin >> q[i];
}
cout << quick_sort(0, n - 1, k) << endl;
return 0;
}