今天要给100亿个数字排序，100亿个 int 型数字放在文件里面大概有 37.2GB，很是大，内存一次装不下了。那么确定是要拆分红小的文件一个一个来处理，最终在合并成一个排好序的大文件。

实现思路

1.把这个37GB的大文件，用哈希分红1000个小文件，每一个小文件平均38MB左右（理想状况），把100亿个数字对1000取模，模出来的结果在0到999之间，每一个结果对应一个文件，因此我这里取的哈希函数是 h = x % 1000，哈希函数取得”好”，能使冲突减少，结果分布均匀。

2.拆分完了以后，获得一些几十MB的小文件，那么就能够放进内存里排序了，能够用快速排序，归并排序，堆排序等等。

3.1000个小文件内部排好序以后，就要把这些内部有序的小文件，合并成一个大的文件，能够用二叉堆来作1000路合并的操做，每一个小文件是一路，合并后的大文件仍然有序。函数

首先遍历1000个文件，每一个文件里面取第一个数字，组成 (数字, 文件号) 这样的组合加入到堆里（假设是从小到大排序，用小顶堆），遍历完后堆里有1000个 (数字，文件号) 这样的元素
而后不断从堆顶拿元素出来，每拿出一个元素，把它的文件号读取出来，而后去对应的文件里，加一个元素进入堆，直到那个文件被读取完。拿出来的元素固然追加到最终结果的文件里。
按照上面的操做，直到堆被取空了，此时最终结果文件里的所有数字就是有序的了。
最后我用c++写了个实验程序，具体代码在这里能够看到。

如何拆分大文件？一个32G的大文件，用fopen()打开不会所有加载到内存的，而后for循环遍历啊，把每一个数字对1000取模，会获得0到999种结果，而后每种结果在写入到新的文件中，就拆分了。

转自：http://www.aiuxian.com/article/p-afrxrewt-g.html