問題：
從一組數中選出其中最大的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.2cto.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;
downshift(k);
}
}
for (i=1; i<=k; i++)
cout << H[i] << " ";
cout << endl;
}
作者：linyunzju
