对有 5 亿整数的大文件排序
一、需求
有1个大文件包含5亿个数（文件大小好几个G），其中每一行都是一个随机整数（不重复），现在要对这个文件进行排序。
二、实现
2.1 位图法
核心思想是，创建一个拥有5亿bits的BitSet（位图），BitSet每一位初始时都为false。然后读取包含正整数的文件，对于每一个数i，将bitSet[i]设置为true。最后遍历位图，如果bitSet[j]为true，那么输出 j。
采用位图法，也可以判断某个给定的数是否在大文件中，只需要判断bitSet的指定位是否为true即可。
下面是我写的一个简单的demo，用于对文件中的数字排序：
data.txt内容如下：
代码如下：
public static void main(String[] args) {
BitSet bitSet = new BitSet(100);
try (BufferedReader br = new BufferedReader(new FileReader("F:\\data.txt"))) {
String line = null;
while ((line = br.readLine()) != null) {
int value = Integer.valueOf(line);
bitSet.set(value);
}
} catch (Exception e) {
e.printStackTrace();
}
for (int i = 0; i < bitSet.length(); i++) {
if (bitSet.get(i)) {
System.out.println(i);
}
}
}结果如下：
1
7
9
12
32
43
87
765
325432.2 外部排序
在内存极小的情况下，采用分治策略，利用外存保存中间结果，再用多路归并来排序。
map-reduce思想：
内存中维护一个极小的缓冲区buffer，将大文件bigdata按行读入，直到buffer满或者大文件读完时，对buffer中的数据调用内排进行排序，排序后将有序结果写入磁盘临时文件bigdata.xxx.part.sorted，循环利用buffer直到大文件处理完毕，得到n个有序的临时文件。
接下来，对n个有序的临时文件进行归并排序，方法如下：假如有三个临时文件，其中文件1：3,6,9，文件2：2,4,8，文件3：1,5,7。
第一回合：文件1的最小值：3 , 排在文件1的第1行，文件2的最小值：2，排在文件2的第1行，文件3的最小值：1，排在文件3的第1行 那么，这3个文件中的最小值是：min(1,2,3) =1。也就是说，最终大文件的当前最小值，是文件1、2、3的当前最小值的最小值。上面拿出了最小值1，写入大文件。
第二回合：文件1的最小值：3，排在文件1的第1行，文件2的最小值：2，排在文件2的第1行，文件3的最小值：5，排在文件3的第2行。那么，这3个文件中的最小值是：min(5,2,3) = 2，将2写入大文件。
接下来，重复上述操作，直到所有小文件的内容都写到了大文件。
参考：