找出一个序列中前M个大值对应的索引(堆排序实现)
//用数组测试堆算法，不改变数组顺序，用数组下标成堆 #include <stdio.h> void push(float a[],int tmp[],int lenth) { int t,tlen=lenth; while(0!=tlen) { if(a[tmp[tlen]]>a[tmp[(tlen-1)/2]]) { t=tmp[tlen]; tmp[tlen]=tmp[(tlen-1)/2]; tmp[(tlen-1)/2]=t; } tlen=(tlen-1)/2; } } //最大值出堆 void pop(float a[],int tmp[],int lenth) { int max,t,tlen=0; t=tmp[lenth]; tmp[lenth]=tmp[0]; tmp[0]=t; while(tlen*2<(lenth-1)) { max = a[tmp[tlen*2+1]]>a[tmp[tlen*2+2]]?(tlen*2+1):(tlen*2+2); if(max==lenth)max--; if(a[tmp[tlen]]<a[tmp[max]]) { t=tmp[max]; tmp[max]=tmp[tlen]; tmp[tlen]=t; } tlen = max; } } void maxnp(float* x,int N,int* maxnp_id,int M) { int tmp[N],b[N]; int i; //初始化 for(i=0;i<N;i++) { b[i]=tmp[i]=i; } //成最大堆 for(i=1;i<N;i++) { push(x,tmp,i); } //出堆，取M个最大值 for(i=1;i<=M;i++) { b[i-1]=tmp[0]; pop(x,tmp,N-i); } for(i=0;i<M;i++) { maxnp_id[i] = b[i]; } } int main() { float x[5]={3.0,2.0,4.0,1.0,5.0}; int i; int maxnp_id[3] = {0}; maxnp(x,5,maxnp_id,3); for(i=0;i<3;i++) { printf("%d ",maxnp_id[i]); //b[i] } printf("\n"); return 0; }
