小笔记：基于快排思想找第 k 大的数
Zirnc
2022-09-08 14:11:08
欢迎访问我的博客：[blog.chungzh.cn](https://blog.chungzh.cn)
参考 **NOIP2008 普及组初赛试题**。
快速排序：找一个基准值（`val`），把大于基准值的数放到数组左边，把小于基准值的数放到右边，然后按照左右两边元素的个数和 $k$ 的大小关系来判断往左边还是右边递归求解。
时间复杂度是 $O(n)$。
```cpp
#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[10005];
int kth(int left, int right, int n) {
int tmp, val;
if (left == right) return left;
// 随机选择基准数
tmp = rand() % (right - left) + left;
swap(a[tmp], a[left]);
val = a[left];
int L = left, R = right;
while (L < R) {
while (L < R && a[R] < val) R--;
if (L < R) {
a[L] = a[R];
L++;
} else {
break;
}
while (L < R && a[L] > val) L++;
if (L < R) {
a[R] = a[L];
R--;
} else {
break;
}
}
a[L] = val;
// 小于和等于基准值的元素个数都不够 k 大，往右递归
if (L < n) return kth(L + 1, right, n);
// 小于基准值的元素个数比 k 大，往左递归
if (L > n) return kth(left, L - 1, n);
// 否则当前值就是第 k 大数
return L;
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
int ans = a[kth(1, n, k)];
cout << ans << endl;
return 0;
}
```