利用快排的思想，利用函数Partition()分段。①若pivot左边的数个数小于K，则输出包括pivot在内的左边的数（假设为m个,m <=K），然后以pivot右边的数组为源数组，在其中查找前K-m个最大的数。②否则，如果pivot(含)左边的数的个数大于K，则以其左边的这一段为查找子集，找其中K个最大的数。
从整个描述上来看，这是一个递归的过程，所以实现里用到了递归。代码如下：
/*
一个有N个整数组成的数组, 写一个函数, 找出数组中最大的K个数 例如：N=1000000 K=10
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef int * SeqList;
typedef int ReceType;
int Partition(SeqList R, int i, int j)
{//调用Partition(R, low, high)时, 对R[low..high]做划分,
//并返回基准记录的位置
ReceType pivot=R[i]; //用区间的第1个记录作为基准 '
while(i<j){ //从区间两端交替向中间扫描, 直至i=j为止
while(i<j&&R[j]<=pivot) //pivot相当于在位置i上
j--; //从右向左扫描, 查找第1个关键字小于pivot的记录R[j]
if(i<j) //表示找到的R[j]的关键字<pivot
R[i++]=R[j]; //相当于交换R[i]和R[j], 交换后i指针加1
while(i<j&&R[i]>=pivot) //pivot相当于在位置j上
i++; //从左向右扫描, 查找第1个关键字大于pivot的记录R[i]
if(i<j) //表示找到了R[i], 使R[i]>pivot
R[j--]=R[i]; //相当于交换R[i]和R[j], 交换后j指针减1
} //endwhile
R[i]=pivot; //基准记录已被最后定位
return i;
} //partition
void output(int x[], int n)
{
for (int i=0; i<n;i++)
{
printf("%d ", x[i]);
}
return;
}
/*找数组x中从from到to中子集的前k个最大值，并进行打印*/
void firstNLargeNums(int x[], int from, int to, int k)
{
if (k<=0) return;
int pos = Partition(x, from, to);
int len = pos - from +1; /*从from开始，到pos（含）的数的个数*/
if (len <= k)
{
output(x+from, len);/*输出这个数组从from开始的len个数（pivot及左边的数）*/
firstNLargeNums(x, pos+1, to, k-len);/*在pivot右边找剩下的k-len个最大的数*/
}else
{
firstNLargeNums(x, from, pos-1, k);/*否则， 在pivot左边找k个最大的数*/
}
}
/*测试用的主函数，用随机数发生器来产生数组*/
#define N 10
#define K 5
int main()
{
int *x = (int *) malloc(N*sizeof(int));
int i;
clock_t start,end;
double runtimelength;
start=clock(); /* 计时开始 */
/*产生随机N个整数构成的数组x*/
srand(time(NULL));
for (i=0;i<N;i++)
{
if(N>RAND_MAX) x[i] = (int)((double)rand() / RAND_MAX *N) ;
else x[i] = rand()%100;
}
if(N<20)
{
printf("原始数据:");
output(x, N);
}
printf("\n其中最大的%d个为：\n", K);
firstNLargeNums(x, 0, N-1, K);
end=clock(); /* 计时结束 */
printf("\n耗时：%6.1f 毫秒\n", runtimelength=(double)(end-start));
printf("\n");
free(x);
return 0;
}