问题：给定n个整数，如何用最快的方法求出第k大的数？

　　我们当然可以对这n个整数排序然后直接输出第k大的数，时间复杂度为O(nlog n)。
　　但是实际上我们可以用基于快速排序所用到的思想，在每一层递归中，随机选取一个数为基准值，把比它大的数交换到左半段，把其余的数和基准值自身一起作为右半段。在这个过程中假设统计出比基准值大的数有cnt个，若k<=cnt，就在左半段中递归寻找第k大;若k>cnt，就在右半段中递归寻找第k-cnt大的数。递归边界为这一段区间长度为1。就返回这个数即为最初所找区间第k大的数。
　　因为是随机选取基准值，所以找第k大的数平均时间复杂度为n + n/2 + n/4 + ... + 1 = O(n)。
总的时间复杂度即为O(n)
实现代码：

#include<bits/stdc++.h>
using namespace std;
int a[100010];
void swap(int& x, int& y) {
    int temp = x;
    x = y;
    y = temp;
}
int random(int l, int r) {//返回一个在[l,r]范围内的随机整数
    return rand() % (r - l + 1) + l;
}
int find_kth(int l, int r, int k) {
    if (l == r)return a[l];//递归边界
    int temp = a[random(l, r)];//随机选取主元
    int cnt = 0;//计比主元大的个数
    int i = l, j = r;
    while (i <= j) {
        while (a[i] > temp && i <= j)i++, cnt++;
        while (a[j] <= temp && i <= j)j--;
        if (i < j) {
            swap(a[i], a[j]);
            cnt++;
        }
        i++, j--;
    }
    if (cnt >= k) {//若k<=cnt，就在左半段中递归寻找第k大
        return find_kth(l, l + cnt - 1, k);
    }
    else {//否则在就在右半段中递归寻找第k-cnt大的数
        return find_kth(l + cnt, r, k - cnt);
    }
}
int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++)cin >> a[i];
    int k; cin >> k;
    cout << find_kth(1, n, k) << endl;
}