在一个文件中有10G个整数，乱序排序，要求找出中位数。

在一个文件中有10G个整数，乱序排序，要求找出中位数。

首先说明一点，64bite的整数足以存储10G这个数值。

然后换个思维理解，比如有20个数，数的范围是（1-10），而内存只能装入两个数。用内存里的这两个数统计范围为（0,5），（6,10）的数出现的次数，比如内存里两个数的取值是4,16，显然中位数(姑且认为是求第10位）出现在（6,10）中的第6出现的数。
这个时候，内存两个数统计范围变成（6,8），（9,10），统计这两个区间内范围出现的数的次数，如果是8,8，中位数是在（6,8）中第6次出现的数。
第三次统计，内存两个数统计的范围是（6，7），（8），如果是7,1，那么所求的中位数还是（6,7）第6次出现的数。
第四次统计，内存两个数为（6），（7），如果内存第一个数>=6,则所求数为6，否则所求数为7。

首先假设是32位无符号整数。
1. 读一遍10G个整数，把整数映射到256M个区段中，用一个64位无符号整数给每个相应区段记数。
说明：整数范围是0 - 2^32 - 1，一共有4G种取值，映射到256M个区段，则每个区段有16（4G/256M = 16）种值，每16个值算一段， 0～15是第1段，16～31是第2段，……2^32-16 ～2^32-1是第256M段。一个64位无符号整数最大值是0～8G-1，这里先不考虑溢出的情况。总共占用内存256M×8B=2GB。
2. 从前到后对每一段的计数累加，当累加的和超过5G时停止，找出这个区段（即累加停止时达到的区段，也是中位数所在的区段）的数值范围，设为[a，a+15]，同时记录累加到前一个区段的总数，设为m。然后，释放除这个区段占用的内存。
3. 再读一遍10G个整数，把在[a，a+15]内的每个值计数，即有16个计数。
4. 对新的计数依次累加，每次的和设为n，当m+n的值超过5G时停止，此时的这个计数所对应的数就是中位数。
总结：
1.以上方法只要读两遍整数，对每个整数也只是常数时间的操作，总体来说是线性时间。
2. 考虑其他情况。
若是有符号的整数，只需改变映射即可。若是64为整数，则增加每个区段的范围，那么在第二次读数时，要考虑更多的计数。若过某个计数溢出，那么可认定所在的区段或代表整数为所求，这里只需做好相应的处理。噢，忘了还要找第5G+1大的数了，相信有了以上的成果，找到这个数也不难了吧。
3. 时空权衡。
花费256个区段也许只是恰好配合2GB的内存（其实也不是，呵呵）。可以增大区段范围，减少区段数目，节省一些内存，虽然增加第二部分的对单个数值的计数，但第一部分对每个区段的计数加快了（总体改变？？待测）。
4. 映射时尽量用位操作，由于每个区段的起点都是2的整数幂，映射起来也很方便。

"将64bit的整数空间平均分成256M个取值范围" <---B-Tree...

首先说明一点，64bite的整数足以存储10G这个数值。
然后换个思维理解，比如有20个数，数的范围是（1-10），而内存只能装入两个数。用内存里的这两个数统计范围为（0,5），（6,10）的数出现的次数，比如内存里两个数的取值是4,16，显然中位数(姑且认为是求第10位）出现在（6,10）中的第6出现的数。
这个时候，内存两个数统计范围变成（6,8），（9,10），统计这两个区间内范围出现的数的次数，如果是8,8，中位数是在（6,8）中第6次出现的数。
第三次统计，内存两个数统计的范围是（6，7），（8），如果是7,1，那么所求的中位数还是（6,7）第6次出现的数。
第四次统计，内存两个数为（6），（7），如果内存第一个数>=6,则所求数为6，否则所求数为7。
这样应该能理解了吧。追问。。不理解，越看越糊涂。。麻烦讲得比较易懂点可以吗？谢谢你~