http://bbs.csdn.net/topics/310150772
可以借鉴一下以下方法的：
有1亿个浮点数，请找出其中最大的10000个。提示：假设每个浮点数占4个字节，1亿个浮点数就要站到相当大的空间，因此不能一次将全部读入内存进行排序。
~~~~~~~~~~~~~
既然不可以一次读入内存, 那可以这么试试:
方法1: 读出100w个数据, 找出最大的1w个, 如果这100w数据选择够理想, 那么以这1w个数据里面最小的为基准, 可以过滤掉1亿数据里面99%的数据, 最后就再一次在剩下的100w(1%)里面找出最大的1w个咯~~
方法2: 分块, 比如100w一个块, 找出最大1w个, 一次下来就剩下100w数据需要找出1w个了.（注意消重，这剩下的100w个数据应该是互不相同的。即每找出一个块里最大的1w个，就应该hash存储。下一个块中若出现了已存储的数据，则不计在此块的top 1w里，这样才能保证最终剩下的100w里面寻找top 1w就接近1亿里面的top 1w。想想：如果每个块的top 1w都基本是重复的，不消重的话，最终的结果有可能就少于1w个。）
对于上面提到的找出100w个数据里面最大的1w个, 说起来比较罗嗦, 还是说说找到第1w个大的数字的方法:
用快速排序的方法, 分2堆, 如果大的那堆个数N大于1w个, 继续对大堆快速排序一次分成2堆, 如果大堆个数N小于1w, 就在小的那堆里面快速排序一次, 找第10000-N大的数字; 递归以上过程, 就可以找到第1w大的数. 据说也是STL的search_n()的方法;（更好的一种类似的方法是将这些数以5个为一组，每组通过插入排序找出其中位数，再找出其中位数的中位数，依次递归，找出最终一个中位数x，然后按照x对序列进行快排，且设x是序列的第k大的数，如果要找的是第i大的数，则比较k与i的关系，如果相等，直接返回x，否则如果k>i，则在小的那堆里面继续按照这种方式快排，如果k<i，则在大堆里面找第i-k大的数。）
参考上面的找出第1w大数字, 相信楼主就可以类似的方法找出前1w大数字了
真的很感谢有这么多人回答，我的思路就是基本上排序+分块，
首先1亿个数我分成了200块，每块50W个，对每个块进行多路归并排序（这里不考虑快速排序，相对来说比较低率，不稳定），
排序好后存储在硬盘文件。
我写了下，大约是15S左右，
然后在用一个两维数组记录这200组数据中的最大和最小值，然后把这200个中位数的平均数求出来，其实没有别的目的
（目的是为了找一个适合的中位数偏移点，因为这个平均数不一定就是1亿个数的，可以叫做先猜一个机率最大的吧）
如果我们这么时候求得的平均数是N
然后就是一个超级土的试探法了，
建立一个偏差数组left[5][200],right[5][200],主要是用来保存N这个数在每个块里面小于N和大于N 5个的数，用来在后面读取
1。从文件里一个一个读取排序好的块，顺便把left,right两数组填充，找出<=N的数所在的index,最后把这些index相加为sum，看sum是否==1亿/2-1
如果相等了，那证明这个数就是中位数了，
2.如果小于
就又从left[0][200]里取最大的一个值，把left[0]排序一下，这样肯定是最接近N的，然后重复1，但是不改变left,right，看是否是中位数，
如果sum继续小于,那么继续2，但是要取left[1][200]最大了,如果sum这时候大于了，证明中位数肯定存在于left[0][200]其中的一个了，
这时候就锁定了，在left[0]用折半找按上面方法计算sum找中位数，
3。如果大于，和2步骤就是相反的。
这个算法虽然可以找到相关的值，但是在从文件重复读块加载到内存方面不知道读取了多少次，效率肯定不是一般的差，想了一两天，没思路了，哎。
| 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117 | 内存只能容纳100W个数, 现在有1亿数,混序, 然后求这一亿个数的中位数, 中位数(就是一个有序数组的中间数字,数组长度为偶数就是两个,奇数则只有一个) /*****************************************************************************//* this program should find out the median(s) in N(logN)/(logB) no matter there/* is duplicated data or not./* /* with memory limitation: 4MB memory available./* I would like to express the idea with code./* here is just the pseudocode with out any optimization for easy understanding./* /* maybe, there is no need to check sum == N/2 or N/2+1, but this will get the /* median(s) as soon as possible with out more recursive invoking./* /* sorry for any logical problem. please let me know if you found any./*****************************************************************************/ int N = 100000000;// total data number is Nint B = 1000000; // number of buckets.int min, max;scan data from 0 to N-1 get min and max; // O(N); void find_median(int num=0, int min, int max){ if(min == max) { if(N%2) { print medians are min and max; } else print median is min; // show you the result return; // exit } /* count all the data in O(N)*/ int m = max-min > B ? (max-min) / B : 1; int cnt[B] = {0}; // count the data read. while(!EOF) { int data = read_data()-min; if(data >= min && data <= max) cnt[data/m]++; } int sum = num, median_1, median_2, i = 0; while(sum < N/2) sum += cnt[i++]; i--; // median is in the range of [i*m, (i+1)*m-1] /* get median(s) when sum is N/2 */ if(sum == N/2) { if(N%2) { // N is even and there are two medians. median_1 = (i+2)*m-1; median_2 = i*m; while(!EOF) { int data = read_data()-min; if(data/m == i) { median_2 = (data > median_2 ? data : median_2); } if(data/m == i+1) { median_1 = (data < median_1 ? data : median_1); } } pintf medians are median_1 and median_2; return; } } else { // N is an odd number and there is one median. median_1 = (i+2)*m-1; while(!EOF) { int data = read_data(); if(data/m == i+1) median_1 = (data < median_1 ? data : median_1); } print median is median_1; return; } /* get median(s) when sum is N/2+1 */ if(sum == N/2+1) { if(N%2) { // N is even and there are two medians. median_1 = i*m; median_2 = i*m; while(!EOF) { int data = read_data(); if(data/m == i) { median_1 = max; median_2 = (data > median_2 ? data : median_2); } } pintf medians are median_1 and median_2; return; } } else { median_2 = i*m; // get (N/2+1)th data. while(!EOF) { int data = read_data(); if(data/m == i) median_2 = (data > median_2 ? data : median_2); } print median is median_2; return; } /* recursively to find out the median(s) */ min = (i+1)*m-1; max = i*m; // get min and max for next processing while(!EOF) { int data = read_data()-min; if(data/m == i) { min = (data < min ? data : min); max = (data > max ? data : max); } } find_median(sum, min, max);} |