这节给的题目是从一串数字中寻找最大的K个数，而且考虑数据量比较大的情况。

解法一首先考虑了快速排序和堆排序，但是，它们对所有的数据都进行了排序，然后考虑使用部分排序算法，如选择排序和交换排序，它们能够从一串数字中选择前K个，但是，效率依旧不高。

解法二使用了快速排序算法，在快速排序算法中，用一个枢轴将数列分成了两个部分，左边的比枢轴小，右边的比枢轴大，然后再分别对两个数列进行递归，在这里，用枢轴来分的时候，左边的比枢轴大，右边的比枢轴小，当枢轴左边的元素个数大于或者等于K，那么，就返回左边数列的最大的K个数，当枢轴左边的元素个数n小于K，就返回左边数列和右边数列的最大的n-k-1个数。书中在实现的时候用到了两个数组，这里，我就按照快速排序的过程实现一遍。

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <iterator>
using namespace std;

vector<int>::iterator find_k(vector<int>::iterator beg, vector<int>::iterator end, int k)
{
    vector<int>::difference_type n = k;
    if(end - beg <= n) {
        return end;
    }

    vector<int>::iterator left = beg, right = end - 1;
    srand(time(NULL));
    int index = rand() % n;
    iter_swap(beg, beg + index);
    while(left < right) {
        while(*right < *left && left < right)
            --right;
        if(left < right) {
            iter_swap(left, right);
        }
        while(*left > *right && left < right)
            ++left;
        if(left < right) {
            iter_swap(left, right);
        }
    }
    n = left - beg;
    if(n + 1 >= k)
        return find_k(beg, left + 1, k);
    else
        return find_k(left + 1, end, k - n - 1);
}

int main()
{
    int arr[] = {5, 3, 8, 1, 2, 7, 6, 9};
    vector<int> ivec(arr, arr + 8);

        int k = 5;
    vector<int>::iterator iter = find_k(ivec.begin(), ivec.end(), k);
    copy(ivec.begin(), iter, ostream_iterator<int>(cout, " "));

    return 0;
}

上述的代码跟快速排序很像吧？为了使枢轴随机，不一定是第一个元素，代码使用了随机数生成函数，将第一个元素与后面的某一个元素进行调换。代码执行结果：

解法三是采用跟解法二类似的二分法，从二进制的角度看，将整数从高位到低位某位为0或者1进行二分。

解法四中，首先提出了一个问题，上面的方法都需要对数据访问多次，如果数据量很大的情况下，数据无法全都装入到内存中，会对效率造成很大的影响。

于是，就要求尽可能少地遍历所有数据。

首先，假设数据的前K个数据就是最大的K个数据，如果第K+1个数据比前K个数据的最小值小，那么前K+1个元素的最大的K个元素就是前K个元素，如果第K+1个数据比前K个数据的最小值大，那么，前K+1个元素的最大的K个元素就是将前K个元素中最小的元素剔除掉就是了。这样重复操作，遍历完所有的元素后，最大的K个数据也就出来了，而且只遍历了一遍数据。按照上述方案，可以得到以下代码：

#include <iostream>
#include <vector>
#include <iterator>
using namespace std;

vector<int>::iterator min_iter(vector<int>::iterator beg, vector<int>::iterator end)
{
    vector<int>::iterator m = beg;

    ++beg;
    while(beg != end) {
        if(*beg < *m) {
            m = beg;
        }
        ++beg;
    }

    return m;
}

void find_k(vector<int>::iterator beg, vector<int>::iterator end, int k)
{
    vector<int>::difference_type n = k;
    if(end - beg <= n) {
        return;
    }

    vector<int>::iterator iter = beg + k;
    while(iter != end) {
        vector<int>::iterator m = min_iter(beg, beg + k);
        if(*iter > *m) {
            iter_swap(iter, m);
        }
        ++iter;
    }
}

int main()
{
    int arr[] = {5, 3, 8, 1, 2, 7, 6, 9};
    vector<int> ivec(arr, arr + 8);

    int k = 5;
    find_k(ivec.begin(), ivec.end(), k);
    if(ivec.size() < k) {
        copy(ivec.begin(), ivec.end(), ostream_iterator<int>(cout, " "));
    }
    else {
        copy(ivec.begin(), ivec.begin() + k, ostream_iterator<int>(cout, " "));
    }

    return 0;
}

思路上面已经解释了，代码就不做过多解释。

以上代码只需要遍历一次所有的元素，主要的瓶颈就在于min_iter()求前K个元素的最小值上，那么，能够快速地得到前K个元素的最小值吗？

可以，使用堆，对前K个元素建小顶堆，那么就能够快速得到前K个元素的最小值了。这里只给出核心函数：

void find_k(vector<int>::iterator beg, vector<int>::iterator end, int k)
{
    vector<int>::difference_type n = k;
    if(end - beg <= n) {
        return;
    }

    make_heap(beg, beg + n, greater<int>());
    vector<int>::iterator iter = beg + n;
    while(iter != end) {
        if(*iter > *beg) {
            pop_heap(beg, beg + n, greater<int>());
            iter_swap(iter, beg + n - 1);
            push_heap(beg, beg + n, greater<int>());
        }
        ++iter;
    }
}

解法五首先提出了一种使用计数的方式，对每个值出现的次数进行计数，然后再从高到低得到最大的K个数，但是，这种方法仅适用于元素时正整数且取值范围不大的数据。

扩展问题：

1 如果需要找出N个数中最大的K个不同的浮点数呢？注意这里的“不同”两个字。

当然，最简单的办法就是对N个数进行排序，最后相等的数字相邻存放，然后从高到低遍历，遇到相等的不进行计数，最后就得到了最大的K个数。

如果可以对数列进行修改，可以先进行预处理，把相同的数据剔除掉，然后求得最大的K个数，不过，预处理的代价也很高。

2 如果是找到第k到m(0<k<=m<=n)大的数呢？

最简单的办法就是利用本节的方法，找到最大的k-1个数和最小的m-1个数，剩下的就是第k到m大的数。