这节给的题目是从一串数字中寻找最大的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大的数。
[编程之美] 2.5 寻找最大的K个数,布布扣,bubuko.com
原文：http://blog.csdn.net/luofengmacheng/article/details/20942777