编程之美2.5——寻找最大的K个数

问题：
从一组数中选出其中最大的K个数，当这组数的个数为几百、几百万、几百亿时分别适合采用哪些算法？

个数为几百时，使用顺序统计法（看算法导论第9章）：
     算法思想是对输入数组进行递归划分，一边的数据小于选定数，另一边的数据大于等于选定数。但和快速排序不同的是，快速排序会递归处理划分的两边，而顺序统计法只处理划分的一边。其随机化算法的期望时间为O(n)。
[cpp]
#include <iostream>
#include <cstdlib>
using namespace std;

#define MAXN 103
int A[MAXN];

void select(int u, int v, int k)
{
    int s = rand()%(v-u+1)+u;
    int a = A[s];
    A[s] = A[u];
    A[u] = a;
    int i, j=u;
    for (i=u; i<=v; i++)
        if (A[i] > a)
        {
            int tmp = A[++j];
            A[j] = A[i];
            A[i] = tmp;
        }
    A[u] = A[j];
    A[j] = a;
    if (j == k) return;
    else if (j < k)
        select(j+1, v, k);
    else
        select(u, j-1, k);
}

int main()
{
    int n, k, i, j;
    cin >> n >> k;
    for (i=0; i<n; i++)
        cin >> A[i];
    select(0, n-1, k-1);
    for (i=0; i<k; i++)
        cout << A[i] << " ";
    cout << endl;
}
个数为几百万时，数据量较大不适合全装入内存中，能容忍多次访问，可使用二分中值法（用法有点奇怪，个人不太喜欢）：
      本质上是通过二分思想找出第K大的数的值。算法从[Min, Max]开始逐渐缩小第K大的数取值的范围，时间复杂度为O(N*log(Max-Min))。
[cpp]
#include <iostream>
#include <cstdlib>
using namespace std;

int binary(FILE *in, int v)
{
    rewind(in);
    int a, sum = 0;
    while (fscanf(in, "%d", &a)!=EOF)
    {
        if (a >= v) sum++;
    }
    return sum;
}

void finded(FILE *in, int v)
{
    rewind(in);
    int a;
    while (fscanf(in, "%d", &a)!=EOF)
    {
        if (a >= v)
            cout << a << " ";
    }
    cout << endl;
}

int main()
{
    int n, k;
    cin >> n >> k;
    FILE* in = fopen("dat.txt","r");
    int min, max;
    int a;
    fscanf(in, "%d", &a);
    min = max = a;
    while (fscanf(in, "%d", &a)!=EOF)
    {
        if (a < min) min = a;
        if (a > max) max = a;
    }
    while (max > min)
    {
        int mid = (min+max)/2;
        int ns = binary(in, mid);
        if (ns == k)
        {
            finded(in, (min+max)/2);
            break;
        }
        else if (ns < k) max = mid;
        else min = mid;
    }
}

个数为几万亿时，数据量较大不适合全装入内存中，且无法容忍多次访问，所有数据只能访问一次，推荐使用最小堆法（上面那种情况也推荐使用这个方法），但要求K较小，否则无法在内存存下整个最小堆。
      用容量为K的最小堆来存储最大的K个数，最小堆的堆顶元素就是最大K个数中最小的一个。每次考虑一个新的元素时，将其与堆顶的元素进行比较，只有当它大于堆顶元素时，才用其替换堆顶元素，并更新最小堆。时间复杂度为O(N*logK)。
[cpp] www.zzzyk.com
#include <iostream>

using namespace std;

#define MAXN 103

int H[MAXN];

void upshift(int s)
{
    int tmp = H[s];
    while (s>1 && H[s>>1] > tmp)
    {
        H[s] = H[s>>1];
        s >>= 1;
    }
    H[s] = tmp;
}

void downshift(int n)
{
    int tmp = H[1];
    int i=1, j=i<<1;
    while (j <= n)
    {
        if (j+1 <= n && H[j+1] < H[j]) j++;
        if (H[j] < tmp) H[i] = H[j];
        else break;
        i = j;
        j = j<<1;
    }
    H[i] = tmp;
}

int main()
{
    int n, k, i, A;
    cin >> n >> k;
    for (i=1; i<=k; i++)
    {
        cin >> H[i];
        upshift(i);
    }
    for (; i<=n; i++)
    {
        cin >> A;
        if (A > H[1])
        {
            H[1] = A;

补充：软件开发 , C++ ,