题目

在一堆数中，找到最大（小）的K个，或者时第k个。如果我们找到了后k个数，那么最大的k个也就找到了。
所以下面的方法都在找第k大的数

方法一

当然时最本的方法，先排序，然后在取数。

方法二

快排的思想，递归进行，将k转化为下标，向下标k靠拢

//代码没跑，思想就是这样。
#include <vector>

using namespace std;

size_t findBigK_partition(vector<int> &source,size_t start,size_t end)
{

    size_t low=start;
    for(size_t i=start;i<end;i++)
    {
        if(source[i]<source[end])
        {
            swap(source[i],source[low]);
            low++;
        }
    }
    swap(source[low],source[end]);
    return low;
}
//
void findBigK_quicksort(vector<int> &source ,size_t start,size_t end,const size_t &k)
{
    if(start >= end)
    {
        return;
    }
    size_t mid = findBigK_partition(source,start,end);
    
    if(mid > k)
    {
        findBigK_quicksort(source,start,mid,k);
    }else if(mid == k){
        return ;
    }else if(mid >k){
        findBigK_quicksort(source,mid,end,k);
    }
}

int findBigK_quick(vector<int> source,size_t k)
{
    k=source.size()-k;
    findBigK_quicksort(source,0,source.size(),k);
    return source[k];
}

方法三

内存有要求的情况下

使用最小二叉堆。始终保存最大的k个数，小于的直接抛弃，如果当前数比现在大，那么替换堆顶元素，然后下沉。只需要遍历一次。
如果k个数，仍然不满足内存的要求，那么先求最大的m（m>k）个数，然后在求m～k之间的数。也就是分段求。不再该范围的数直接舍弃，那么就需要多次遍历数组。

方法四

如果数据量不大，或者范围固定，那么直接使用桶排序，然后最后在统计。