题目：有20个数组， 每个数组里面有500个数， 升序排列， 求出这10000个数字中最大的500个。 求复杂度。
暴力法，直接将20个数组中的数据全部合并，重新排序，然后取出最大的500个。 如果空间允许的情况下，排序的时间复杂度根据选择的排序算法来决定。
从20个数组中各取一个数，并记录每个数的来源数组，建立一个含20个元素的大根堆。 此时堆顶就是最大的数，取出堆顶元素，并从堆顶元素的来源数组中取下一个数加入堆，再取最大值，一直这样进行500次即可。 时间复杂度：500*log(20) 怎么记录每个数的来源数组？ 用结构体记录，一个成员记录值，一个记录来源，按成员值比较 也可以单独用一个数组存储。
/* 原题：有20个数组，每个数组里面有500个数，升序排列，求出这10000个数中最大的500个，求复杂度。 算法实现：为简化，设有5个数组，每个数组里面有10个数，升序排列，求出50个数中最大的5个数。 */ #include<iostream> using namespace std; void CreatHeap(int s[],int n) //建堆，最大堆即首元素是最大的 { //从最后一个非叶子节点开始 int i,j,k; i=n/2-1; j=2*i+1; for(k=i;k>=0;k--) { i=k; j=2*i+1; while(j<=n) { if(j+1<=n&&s[j]<s[j+1])j=j+1; if(s[i]<s[j]) { int temp=s[i]; s[i]=s[j]; s[j]=temp; i=j; j=2*i+1; } else break; } } } int main() { int a[5][10]={ {1,2,3,4,5,6,7,8,45,47}, {11,12,13,14,15,16,17,18,19,20}, {21,22,23,24,25,26,27,28,29,30}, {31,32,33,34,35,36,37,38,39,40}, {41,42,43,44,45,46,47,48,49,50}}; int b[5]={9,9,9,9,9};//作为标记当前取该数组的哪个 int temp[5]; int count=0; int result[10]; for(int m=0;m<10;m++) { for(int i=0;i<5;i++) { int r=b[i]; temp[i]=a[i][r]; } CreatHeap(temp,5);//需要标记最大的值temp[0]在那个数组中 int max=temp[0]; result[count++]=max; for(int i=0;i<5;i++) { int k=b[i]; if(max==a[i][k]) { b[i]=b[i]-1; break; } } } for(int i=0;i<10;i++) { cout<<result[i]<<endl; } }