欢迎访问我的博客：blog.chungzh.cn

参考 NOIP2008 普及组初赛试题。

快速排序：找一个基准值（val），把大于基准值的数放到数组左边，把小于基准值的数放到右边，然后按照左右两边元素的个数和 $k$ 的大小关系来判断往左边还是右边递归求解。

时间复杂度是 $O(n)$。

#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;
}