适用范围：大数据的排序，去重
基本原理及要点：外排序的归并方法，置换选择败者树原理，最优归并树
扩展：
##问题实例：
有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制大小是1M。返回频数最高的100个词。
这个数据具有很明显的特点，词的大小为16个字节，但是内存只有1M做hash明显不够，所以可以用来排序。内存可以当输入缓冲区使用。
关于多路归并算法及外排序的具体应用场景，请参见blog内此文。
###问题2 输入：给定一个文件，里面最多含有n个不重复的正整数（也就是说可能含有少于n个不重复正整数），且其中每个数都小于等于n，n=10^7。 输出：得到按从小到大升序排列的包含所有输入的整数的列表。 条件：最多有大约1MB的内存空间可用，但磁盘空间足够。且要求运行时间在5分钟以下，10秒为最佳结果。
####解法一、位图方案
你可能会想到把磁盘文件进行归并排序，但题目要求你只有1MB的内存空间可用，所以，归并排序这个方法不行。
熟悉位图的朋友可能会想到用位图来表示这个文件集合。例如正如编程珠玑一书上所述，用一个20位长的字符串来表示一个所有元素都小于20的简单的非负整数集合，边框用如下字符串来表示集合{1,2,3,5,8,13}：
0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0
上述集合中各数对应的位置则置1，没有对应的数的位置则置0。
参考编程珠玑一书上的位图方案，针对我们的10^7个数据量的磁盘文件排序问题，我们可以这么考虑，由于每个7位十进制整数表示一个小于1000万的整数。我们可以使用一个具有1000万个位的字符串来表示这个文件，其中，当且仅当整数i在文件中存在时，第i位为1。采取这个位图的方案是因为我们面对的这个问题的特殊性：
- 输入数据限制在相对较小的范围内，
- 数据没有重复，
- 其中的每条记录都是单一的整数，没有任何其它与之关联的数据。
所以，此问题用位图的方案分为以下三步进行解决：
- 第一步，将所有的位都置为0，从而将集合初始化为空。
- 第二步，通过读入文件中的每个整数来建立集合，将每个对应的位都置为1。
- 第三步，检验每一位，如果该位为1，就输出对应的整数。
经过以上三步后，产生有序的输出文件。令n为位图向量中的位数（本例中为1000 0000），程序可以用伪代码表示如下：
//磁盘文件排序位图方案的伪代码
//copyright@ Jon Bentley
//July、updated，2011.05.29。
//第一步，将所有的位都初始化为0
for i ={0,....n}
bit[i]=0;
//第二步，通过读入文件中的每个整数来建立集合，将每个对应的位都置为1。
for each i in the input file
bit[i]=1;
//第三步，检验每一位，如果该位为1，就输出对应的整数。
for i={0...n}
if bit[i]==1
write i on the output file
上述的位图方案，共需要扫描输入数据两次，具体执行步骤如下：
第一次，只处理1—4999999之间的数据，这些数都是小于5000000的，对这些数进行位图排序，只需要约5000000/8=625000Byte，也就是0.625M，排序后输出。 第二次，扫描输入文件时，只处理4999999-10000000的数据项，也只需要0.625M（可以使用第一次处理申请的内存）。 因此，总共也只需要0.625M 位图的的方法有必要强调一下，就是位图的适用范围为针对不重复的数据进行排序，若数据有重复，位图方案就不适用了。
不过很快，我们就将意识到，用此位图方法，严格说来还是不太行，空间消耗10^7/8还是大于1M（1M=1024*1024空间，小于10^7/8）。
既然如果用位图方案的话，我们需要约1.25MB（若每条记录是8位的正整数的话，则10000000/(102410248) ~= 1.2M）的空间，而现在只有1MB的可用存储空间，那么究竟该作何处理呢？
####解法二、多路归并
诚然，在面对本题时，还可以通过计算分析出可以用如2的位图法解决，但实际上，很多的时候，我们都面临着这样一个问题，文件太大，无法一次性放入内存中计算处理，那这个时候咋办呢？分而治之，大而化小，也就是把整个大文件分为若干大小的几块，然后分别对每一块进行排序，最后完成整个过程的排序。k趟算法可以在kn的时间开销内和n/k的空间开销内完成对最多n个小于n的无重复正整数的排序。
比如可分为2块（k=2，1趟反正占用的内存只有1.25/2M），14999999，和50000009999999。先遍历一趟，首先排序处理14999999之间的整数（用5000000/8=625000个字的存储空间来排序04999999之间的整数），然后再第二趟，对5000001~1000000之间的整数进行排序处理。
我们下面针对20个小数据的文件举例说明，每趟对4个数据进行排序，即5路归并，程序的排序结果如下图所示。
运行时间：
0ms，可以忽略不计了，毕竟是对20个数的小数据量进行排序：
####解法总结：
1、关于本章中位图和多路归并两种方案的时间复杂度及空间复杂度的比较，如下：
时间复杂度 空间复杂度
位图 O(N) 0.625M 多位归并 O(Nlogn) 1M
（多路归并，时间复杂度为O（kn/klogn/k ），严格来说，还要加上读写磁盘的时间，而此算法绝大部分时间也是浪费在这上面）
2、bit-map
适用范围：可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下 基本原理及要点：使用bit数组来表示某些元素是否存在，比如8位电话号码 扩展：bloom filter可以看做是对bit-map的扩展
问题实例：
1)已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。 8位最多99 999 999，大概需要99m个bit，大概10几m字节的内存即可。
2)2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。
将bit-map扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出现2次及以上。或者我们不用2bit来进行表示，我们用两个bit-map即可模拟实现这个2bit-map。
3、[外排序适用范围]大数据的排序，去重基本原理及要点：外排序的归并方法，置换选择败者树原理，最优归并树扩展。问题实例：1).有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制大小是1M。返回频数最高的100个词。这个数据具有很明显的特点，词的大小为16个字节，但是内存只有1m做hash有些不够，所以可以用来排序。内存可以当输入缓冲区使用。