求数组最小的k个元素，方法有很多，这里仅列举三种
1. 使用排序的方法，排序可以选用复杂度较低的快速排序，时间复杂度为O(n*logn),也可以使用线性时间排序，但这时需要O(N)的空间复杂度。下面是使用快速排序求得最小的k个元素的方法。
# include <iostream>
using namespace std;
# include <stdlib.h>
int cmp(const void* a,const void *b)
{
return *((int *)a)>*((int *)b);
}
int main()
{
int a[10]={10,12,30,45,51,62,70,8,9,0};
qsort(a,sizeof(a)/sizeof(int),sizeof(int),cmp);// 快速排序
int k=3;
int i=0;
for(i=0;i<k;i++)
cout<<a[i]<<endl;
system("pause");
return 0;
}
2.第二中方法是在新建大小为k的数组，选取最大的一个元素kmax,然后在从其余n-k个元素中依次选取，如果这个元素大于kmax，则它不在最小的k个元素之内，此时程序什么也不做，如果这个元素小于kmax,则kmax不在最小的k个元素之内，用这个元素替换kmax，在从这k个元素中选取新的kmax.这种方法的时间复杂度为O(n*k),程序为：
# include <iostream>
using namespace std;
# include <stdlib.h>
int cmp(const void* a,const void *b)
{
return *((int *)a)>*((int *)b);
}
int main()
{
int a[10]={10,12,30,45,51,62,70,8,9,0};
void findk(int a[],int n);
findk(a,10);
system("pause");
return 0;
}
int findkmax(int *b,int k) //寻找数组中最大元素kmax
{
int tmp=b[0];
int j=0;
int i;
for(i=0;i<k;i++)
{
if(*(b+i)>tmp){
tmp=*(b+i);
j=i;
}
}
return j;
}
void findk(int a[],int n)
{ int k;
int i=0;
int j;
printf("input k\n");
scanf("%d",&k);
int *b=(int *)malloc(k*sizeof(int));
for(i=0;i<k;i++)
*(b+i)=a[i];
j=findkmax(b,k);
for(i=k;i<n;i++)
{
if(a[i]<b[j])
{
b[j]=a[i];
j=findkmax(b,k);
}
}
for(i=0;i<k;i++)
printf("%d\t",b[i]);
}
这种方法还可以使用最大堆进行改进，建立一个最大堆，堆得元素个数是k,从其余n-k依次选取元素，如果这个元素小于堆顶元素，则用其替换堆顶元素，否则，什么也不做。这种方法的时间复杂度为：O(N*logk)。优化的地方在于最大堆的调整操作仅需要logk的时间，而在数组中找最大元素需要O(k)的时间。
3.可以使用最小堆，建立大小为N的最小堆，每次删除堆顶元素，删除k次，这样最小的k个元素就找到了。时间复杂度为O(k*logN)。程序为：
# include <iostream>
using namespace std;
# include <stdlib.h>
int main()
{
void perdown(int a[],int start,int end);
void findk(int a[],int k,int n);
int a[10]={10,2,13,44,5,46,17,68,9,40};
findk(a,3,10);
system("pause");
return 0;
}
void perdown(int a[],int start,int end) //调整堆序
{
int tmp,i;
tmp=a[start];
i=2*start+1;
while(i<=end)
{
if(i+1<=end&&a[i+1]<a[i])
i++;
if(a[i]>=tmp)
break;
a[start]=a[i];
start=i;
i=2*start+1;
}
a[start]=tmp;
}
void findk(int a[],int k,int n) //从堆中删除最小值
{
int i=0;
for(i=(n-1)/2;i>=0;i--)
{
perdown(a,i,n-1);
}
for(i=0;i<k;i++)
{
printf("%d\t",a[0]);
int tmp=a[0];
a[0]=a[n-1-i];
a[n-1-i]=tmp;
perdown(a,0,n-i-2);
}
}
原文：http://blog.csdn.net/u011608357/article/details/23095521