题目描述
给定一个长度为n的整数数列,以及一个整数k,请用快速选择算法求出数列的第k小的数是多少。
样例
5 3
2 4 1 5 3
本题的要点应该是通过k的位置对k所在部分的序列进行再次递归直到最后找到k位的数
这里要注意的是,每一轮排序之后,前j个数与后l-j个数的整体排序就已经确定,
我们需要做的是在其内部进行下一层的排序。
所以每一轮排序后就可以判断k属于哪一子部分,对那个子部分进行排序即可。
C++ 代码
#include<iostream>
using namespace std;
const int maxn = 1000005;
int a[maxn];
void quick_sort_kth(int a[], int l, int r, int k){
if(l >= r) return ;
int i = l-1, j = r+1, x = a[(l+r) >> 1];
while(i < j){
do i++; while(a[i] < x);
do j--; while(a[j] > x);
if(i < j) swap(a[i], a[j]);
else break;
}
//如果k<=j+1,则k在左子部分,对左边排序即可,反之对右边排序即可
if(k <= j+1) quick_sort_kth(a, l, j, k); // 这里注意的是由于数组下标的原因所以k需要与j+1相比较
else quick_sort_kth(a, j+1, r, k);
}
int main()
{
int n, k;
cin >> n >> k;
for(int i = 0; i < n; i++)
cin >> a[i];
quick_sort_kth(a, 0, n-1, k);
cout << a[k-1];
return 0;
}