算法!大家写写看谁的最快?

Question

40亿=
40 0000 0000=4 000 000 000
=2^32 = 4G
每个正数占4个字节.
需要磁盘空间 16G
一个文件8G,先不管是否支持这么大的文件.
32位地址的内存空间是4G,肯定无法全部加载.
.....
讨论这个问题有什么意思?

Answer 1

最简单的想法，排4G-1次，每次取出未排序部分名字最靠前的(姑且认为搂住想根据名字排序)
不过我很笨的，高手写出算法来我copy吧

Answer 2

treeroot(根根)强人 + 牛人

Answer 3

int range=10000000;
int[] s=new int[range];
while(!isEnd()) s[read()]++;
for(int x=0; x<range; x++)
    while(s[x]--)
        write(x);以上是box sort算法.对正整数排序
需要自行实现boolean isEnd(), int read(), void write(int)
range值请按需要设置,它取决于你要排序的数的最大值,并受限于内存的大小
如上所示为10000000,表示将要排序的最大值为10000000,并将使用40M(10000000 * 4字节/整数)内存

Answer 4

包含40亿个整数的文件?
这句话我不明白，这个文件是什么格式的？文本还是二进制？
可以想象一下，如果该文件是文本，考虑该文件的大小：
最小的情况：每个整数都为0--9之间的数，这样算成字符占两个字节，加上每两个整数之间肯定需要分割符，该分隔符也占两个字节，所以针对每一个整数，需要四个字节。形如：1,3,9,0,6,5,9,4,2,.........
这样需要的空间是4*4,000,000,000个字节=16G
最大的情况：我们简单的假设平均每个整数都为一个10位的整数，看看会发生什么情况，如1000000000，
这个整数加上它后面的分隔符，占用的空间是22个字节，那么整个文件占用的字节数为：
22*4G=88G    按照这样的思路，在最坏的情况下，这个文件可以到无穷大！这取决于每个整数的位数！所以，这个问题本身是没有什么问题的，关键是你先给我弄来足够的硬盘空间和足够大的内存，还有超强的cpu。否则说什么都是没意义的

Answer 5

怎么不切实际了,这是我们面试时一家公司的考题;
上面说的件是.txt
用外排是一定的了.