&&& 经过几天的痛苦沉思，最终决定，把原程序员面试题狂想曲系列正式更名为程序员编程艺术系列，同时，狂想曲创作组更名为编程艺术室。之所以要改名，我们考虑到三点：1、为面试服务不能成为我们最终或最主要的目的，2、我更愿把解答一道道面试题，ACM题等各类程序设计题目的过程，当做一种艺术来看待，3、艺术的提炼本身是一个非常非常艰难的过程，但我们乐意接受这个挑战。
&&& ok，如果任何人对本编程艺术系列有任何意见，或发现了本编程艺术系列任何问题，漏洞，bug，欢迎随时提出，我们将虚心接受并感激不尽，以为他人创造更好的价值，更好的服务。
第一节、如何给磁盘文件排序
问题描述：
输入：给定一个文件，里面最多含有n个不重复的正整数（也就是说可能含有少于n个不重复正整数），且其中每个数都小于等于n，n=10^7。
输出：得到按从小到大升序排列的包含所有输入的整数的列表。
条件：最多有大约1MB的内存空间可用，但磁盘空间足够。且要求运行时间在5分钟以下，10秒为最佳结果。
分析：下面咱们来一步一步的解决这个问题，
&&&&1、归并排序。你可能会想到把磁盘文件进行归并排序，但题目要求你只有1MB的内存空间可用，所以，归并排序这个方法不行。
&&&&2、位图方案。熟悉位图的朋友可能会想到用位图来表示这个文件集合。例如正如编程珠玑一书上所述，用一个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。采取这个位图的方案是因为我们面对的这个问题的特殊性：1、输入数据限制在相对较小的范围内，2、数据没有重复，3、其中的每条记录都是单一的整数，没有任何其它与之关联的数据。
&&& 所以，此问题用位图的方案分为以下三步进行解决：
第一步，将所有的位都置为0，从而将集合初始化为空。第二步，通过读入文件中的每个整数来建立集合，将每个对应的位都置为1。第三步，检验每一位，如果该位为1，就输出对应的整数。
&&& 经过以上三步后，产生有序的输出文件。令n为位图向量中的位数（本例中为），程序可以用伪代码表示如下：
&&& 上面只是为了简单介绍下位图算法的伪代码之抽象级描述。显然，咱们面对的问题，可不是这么简单。下面，我们试着针对这个要分两趟给磁盘文件排序的具体问题编写完整代码，如下。
&而后测试了一下上述程序的运行时间，采取位图方案耗时14s，即14000ms：
本章中，生成大数据量（1000w）的程序如下，下文第二节的多路归并算法的c++实现和第三节的磁盘文件排序的编程实现中，生成的1000w数据量也是用本程序产生的，且本章内生成的1000w数据量的数据文件统一命名为“data.txt”。
&&& 不过很快，我们就将意识到，用此位图方法，严格说来还是不太行，空间消耗10^7/8还是大于1M（1M=空间，小于10^7/8）。
&&& 既然如果用位图方案的话，我们需要约1.25MB（若每条记录是8位的正整数的话，则24*1024*8) ~= 1.2M）的空间，而现在只有1MB的可用存储空间，那么究竟该作何处理呢?
updated && correct：
&&&@yansha：&上述的位图方案，共需要扫描输入数据两次，具体执行步骤如下：
第一次，只处理1—4999999之间的数据，这些数都是小于5000000的，对这些数进行位图排序，只需要约=625000Byte，也就是0.625M，排序后输出。第二次，扫描输入文件时，只处理00000的数据项，也只需要0.625M（可以使用第一次处理申请的内存）。
因此，总共也只需要0.625M
位图的的方法有必要强调一下，就是位图的适用范围为针对不重复的数据进行排序，若数据有重复，位图方案就不适用了。
&&&&3、多路归并。诚然，在面对本题时，还可以通过计算分析出可以用如2的位图法解决，但实际上，很多的时候，我们都面临着这样一个问题，文件太大，无法一次性放入内存中计算处理，那这个时候咋办呢？分而治之，大而化小，也就是把整个大文件分为若干大小的几块，然后分别对每一块进行排序，最后完成整个过程的排序。k趟算法可以在kn的时间开销内和n/k的空间开销内完成对最多n个小于n的无重复正整数的排序。
& & 比如可分为2块（k=2，1趟反正占用的内存只有1.25/2M），1~4999999，和9999。先遍历一趟，首先排序处理1~4999999之间的整数（用=625000个字的存储空间来排序0~4999999之间的整数），然后再第二趟，对0000之间的整数进行排序处理。在稍后的第二节、第三节、第四节，我们将详细阐述并实现这种多路归并排序磁盘文件的方案。
&&&&4、读者思考。经过上述思路3的方案之后，现在有两个局部有序的数组了，那么要得到一个完整的排序的数组，接下来改怎么做呢?或者说，如果是K路归并，得到k个排序的子数组，把他们合并成一个完整的排序数组，如何优化？或者，我再问你一个问题，K路归并用败者树 和 胜者树 效率有什么差别?这些问题，请读者思考。
第二节、多路归并算法的c++实现
&&& 本节咱们暂抛开咱们的问题，阐述下有关多路归并算法的c++实现问题。在稍后的第三节，咱们再来具体针对咱们的磁盘文件排序问题阐述与实现。
&&& 在了解多路归并算法之前，你还得了解归并排序的过程，因为下面的多路归并算法就是基于这个流程的。其实归并排序就是2路归并，而多路归并算法就是把2换成了k，即多（k）路归并。下面，举个例子来说明下此归并排序算法，如下图所示，我们对数组8 3 2 6 7 1 5 4进行归并排序：
&&& 归并排序算法简要介绍：
一、思路描述：
&&& 设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上：R[low..m]，R[m+1..high]，先将它们合并到一个局部的暂存向量R1(相当于输出堆)中，待合并完成后将R1复制回R[low..high]中。
&&& 二路归并排序的过程是：
&&& (1)把无序表中的每一个元素都看作是一个有序表，则有n个有序子表；
&&& (2)把n个有序子表按相邻位置分成若干对（若n为奇数，则最后一个子表单独作为一组），每对中的两个子表进行归并，归并后子表数减少一半；
&&& (3)反复进行这一过程，直到归并为一个有序表为止。
&&& 二路归并排序过程的核心操作是将一维数组中相邻的两个有序表归并为一个有序表。
二、分类：
&&& 归并排序可分为：多路归并排序、两路归并排序 。
&&& 若归并的有序表有两个，叫做二路归并。一般地，若归并的有序表有k个，则称为k路归并。二路归并最为简单和常用，既适用于内部排序，也适用于外部排序。本文着重讨论外部排序下的多（K）路归并算法。
三、算法分析：&
&&& 1、稳定性:归并排序是一种稳定的排序。
&&& 2、存储结构要求:可用顺序存储结构。也易于在链表上实现。
&&& 3、时间复杂度: 对长度为n的文件，需进行lgn趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。。
&&& 4、空间复杂度:需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。
&&&&&& 注意:若用单链表做存储结构，很容易给出就地的归并排序。
&&& 总结：与快速排序相比，归并排序的最大特点是，它是一种稳定的排序方法。归并排序一般多用于外排序。但它在内排方面也占有重要地位，因为它是基于比较的时间复杂度为O(N*Log(N))的排序算法中唯一稳定的排序，所以在需要稳定内排序时通常会选择归并排序。归并排序不要求对序列可以很快地进行随机访问，所以在链表排序的实现中很受欢迎。
&&& 好的，介绍完了归并排序后，回到咱们的问题。由第一节，我们已经知道，当数据量大到不适合在内存中排序时，可以利用多路归并算法对磁盘文件进行排序。
&&& 我们以一个包含很多个整数的大文件为例，来说明多路归并的外排序算法基本思想。假设文件中整数个数为N(N是亿级的)，整数之间用空格分开。首先分多次从该文件中读取M（十万级）个整数，每次将M个整数在内存中使用快速排序之后存入临时文件，然后使用多路归并将各个临时文件中的数据再次整体排好序后存入输出文件。显然，该排序算法需要对每个整数做2次磁盘读和2次磁盘写。以下是本程序的流程图：
&&&&本程序是基于以上思想对包含大量整数文件的从小到大排序的一个简单实现，这里没有使用内存缓冲区，在归并时简单使用一个数组来存储每个临时文件的第一个元素。下面是多路归并排序算法的c++实现代码（在第四节，将给出多路归并算法的c实现）：&
程序测试：读者可以继续用小文件小数据量进一步测试。
第三节、磁盘文件排序的编程实现
&&& ok，接下来，我们来编程实现上述磁盘文件排序的问题，本程序由两部分构成：
1、内存排序
由于要求的可用内存为1MB，那么每次可以在内存中对250K的数据进行排序，然后将有序的数写入硬盘。
那么10M的数据需要循环40次，最终产生40个有序的文件。
2、归并排序
将每个文件最开始的数读入(由于有序，所以为该文件最小数)，存放在一个大小为40的first_data数组中；选择first_data数组中最小的数min_data，及其对应的文件索引index；将first_data数组中最小的数写入文件result，然后更新数组first_data(根据index读取该文件下一个数代替min_data)；判断是否所有数据都读取完毕，否则返回2。
所以，本程序按顺序分两步，第一步、Memory Sort，第二步、Merge Sort。程序的流程图，如下图所示（感谢F的绘制）。
然后，编写的完整代码如下：
其中，生成数据文件data.txt的代码在第一节已经给出。
程序测试：
&&&&1、咱们对1000W数据进行测试，打开半天没看到数据，
&&&&2、编译运行上述程序后，data文件先被分成40个小文件data[1....40]，然后程序再对这40个小文件进行归并排序，排序结果最终生成在result文件中，自此result文件中便是由data文件的数据经排序后得到的数据。
&&&&3、且，我们能看到，data[i]，i=1...40的每个文件都是有序的，如下图：
&&&&4、最终的运行结果，如下，单位统一为ms：
&&& 由上观之，我们发现，第一节的位图方案的程序效率是最快的，约为14s，而采用上述的多路归并算法的程序运行时间约为25s。时间主要浪费在读写磁盘IO上，且程序中用的库函数qsort也耗费了不少时间。所以，总的来说，采取位图方案是最佳方案。
小数据量测试：
&&& 我们下面针对小数据量的文件再测试一次，针对20个小数据，每趟对4个数据进行排序，即5路归并，程序的排序结果如下图所示。
运行时间：
0ms，可以忽略不计了，毕竟是对20个数的小数据量进行排序：
沙海拾贝：
&&& 我们不在乎是否能把一个软件产品或一本书最终完成，我们更在乎的是，在完成这个产品或创作这本书的过程中，读者学到了什么，能学到什么?所以，不要一味的马上就想得到一道题目的正确答案，请跟着我们一起逐步走向山巅。
第四节、多路归并算法的c实现
&&& 本多路归并算法的c实现原理与上述c++实现一致，不同的地方体现在一些细节处理上，且对临时文件的排序，不再用系统提供的快排，即上面的qsort库函数，是采用的三数中值的快速排序（个数小于3用插入排序）的。而我们知道，纯正的归并排序其实就是比较排序，在归并过程中总是不断的比较，为了从两个数中挑小的归并到最终的序列中。ok，此程序的详情请看：
程序测试：
在此，我们先测试下对个数据的文件进行40趟排序，然后再对100个数据的文件进行4趟排序（读者可进一步测试）。如弄几组小点的数据,输出ID和数据到屏幕，再看程序运行效果。
10个数, 4组40个数, 5组55个数, 6组100个数, 7组
（备注：1、以上所有各节的程序运行环境为windows xp + vc6.0 + e5200 cpu 2.5g主频，2、感谢5为本文程序所作的大量测试工作）
全文总结：
1、关于本章中位图和多路归并两种方案的时间复杂度及空间复杂度的比较，如下：
&&&&&&&&&&&&& 时间复杂度&&&&& &空间复杂度
位图&&&&&& & O(N)&&&&&&&&&& && &0.625M
多位归并& &O(Nlogn)&&&&&&& 1M&&&
（多路归并，时间复杂度为O（k*n/k*logn/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有些不够，所以可以用来排序。内存可以当输入缓冲区使用。&
4、海量数据处理
&&& 有关海量数据处理的方法或面试题可参考此文，。日后，会逐步实现这十个处理海量数据的方法。同时，送给各位一句话，解决问题的关键在于熟悉一个算法，而不是某一个问题。熟悉了一个算法，便通了一片题目。
& &&updated：有一读者朋友针对本文写了一篇文章为，海量数据多路归并排序的c++实现（归并时利用了败者树），地址为：。谢谢，欢迎参考。
以下是自己已编译OK 的程序代码，（可能与上面的有冲突的地方）
本文已收录于以下专栏：
相关文章推荐
如何给10^7个数据量的磁盘文件排序
问题描述：
输入：一个最多含有n个不重复的正整数（也就是说可能含有少于n个不重复正整数）的文件，其中每个数都小于等于n，且n=10^7。
输出：得到...
作者:July，yansha，5，编程艺术室。
出处：http://blog.csdn.net/v_JULY_v 。
经过几天的痛苦沉思，最终决定，把原程序员面试...
第十章、如何给10^7个数据量的磁盘文件排序
作者:July，yansha，5，编程艺术室。
出处：http://blog.csdn.net/v_JULY_v 。
第十章、如何给10^7个数据量的磁盘文件排序
作者:July，yansha，5，编程艺术室。
出处：http://blog.csdn.net/v_JULY_v 。
http://blog.csdn.net/v_july_v/article/details/6451990
第十章、如何给10^7个数据量的磁盘文件排序
作者:July，yansh...
第一节、如何给磁盘文件排序
问题描述：
输入：一个最多含有n个不重复的正整数（也就是说可能含有少于n个不重复正整数）的文件，其中每个数都小于等于n，且n=10^7。
输出：得到按从小到大升序排列...
本文转载自http://blog.csdn.net/v_july_v/article/details/6451990
第十章、如何给10^7个数据量的磁盘文件排序
问题描述：
输入：给定一个文件，里面含有多个不重复的正整数，其中每个数都小于等于n，并且正整数的总个数小于n，n=10^7。
输出：得到按从小到大升序排列的包含所有输入的整数的列表。
条件：最多...
##【参考】给大数据量的磁盘文件排序@(Eg - 数据结构与算法分析)[外部排序|noteton]###如何给磁盘文件排序####问题描述**输入：**给定一个文件，里面最多含有n个不重复的正整数（也...
问题描述：
输入：一个最多含有n个不重复的正整数（也就是说可能含有少于n个不重复正整数）的文件，其中每个数都小于等于n，且n=10^7。
输出：得到按从小到大升序排列的包含所有输入的整数的列表。
他的最新文章
讲师：董晓杰
讲师：姚远
他的热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)数据库表数据量大怎么优化查询速度_百度知道
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。
数据库表数据量大怎么优化查询速度
我有更好的答案
●在条件表达式中经常用到的不同值较多的列上建立检索，合理地合并数据库表（尽管有时可能影响表的规范化，技术上叫正规表达式，……other columns FROM cust。注意：临时表创建后不会反映主表的修改。在主表中数据频繁修改的情况下，注意不要丢失数据。 7．用排序来取代非顺序存取非顺序磁盘存取是最慢的操作，表现在磁盘存取臂的来回移动。SQL语句隐藏了这一情况，使得我们在写应用程序时很容易写出要求存取大量非顺序页的查询。有些时候，用数据库的排序能力来替代非顺序的存取能改进查询。;O下面以关系数据库系统Informix为例。还可以使用并集来避免顺序存取。尽管在所有的检查列上都有索引。但这种匹配特别耗费时间： SELECT cust.name，可以在可疑的索引上进行检查.name INTO TEMP cust_with_balance 然后以下面的方式在临时表中查询：SELECT ＊ FROM cust_with_balance WHERE postcode&“98000” 临时表中的行要比主表中的行少：SELECT ＊ FROM orders WHERE (customer_num=104 AND order_num&gt，就要正确地增建索引；●group by或order by子句中列的次序与索引的次序不一样；●排序的列来自不同的表。为了避免不必要的排序、年龄……）和选课表（学号、课程号、成绩）。如果两个表要做连接，就要在“学号”这个连接字段上建立索引，那么应当试图简化它，一个嵌套3层的查询;0 AND cust.postcode&“98000” ORDER BY cust.name 如果这个查询要被执行多次而不止一次，而不经常连接的字段则由优化器自动生成索引。●在频繁进行排序或分组（即进行group by或order by操作）的列上建立索引，而且物理顺序就是所要求的顺序，减少了磁盘I&#47。1．合理使用索引索引是数据库中重要的数据结构，它的根本目的就是为了提高查询效率，所以查询工作量可以得到大幅减少。例如语句：SELECT ＊ FROM customer WHERE zipcode[2，如缩小排序的列的范围等。当能够利用索引自动以适当的次序产生输出时，优化器就避免了排序的步骤。2．避免或简化排序应当简化或避免对大型表进行重复的排序。例如：SELECT cust.0 ORDER BY“80”，在where子句中采用了非开始子串，因而这个语句也不会使用索引。 6．使用临时表加速查询把表的一个子集进行排序并创建临时表，有时能加速查询。它有助于避免多重排序操作。如果建立索引不但不会提高查询效率，反而会严重降低更新速度。●如果待排序的列有多个，可以在这些列上建立复合索引（compound index）。●使用系统工具。如Informix数据库有一个tbcheck工具，但某些形式的where子句强迫优化器使用顺序存取。下面的查询将强迫对orders表执行顺序操作，在不同值少的列上不要建立索引。比如在雇员表的“性别”列上只有“男”与“女”两个不同值，因此就无必要建立索引，但是在上面的语句中优化器还是使用顺序存取路径扫描整个表，rcvbles，必要时进行修复，其使用原则如下，rcvbles WHERE cust.customer_id = rcvlbes.customer_id AND rcvblls.balance&gt，3]&gt，并按客户的名字进行排序，效率越低，因此应当尽量避免子查询。如果子查询不可避免，那么要在子查询中过滤掉尽可能多的行。5．避免困难的正规表达式MATCHES和LIKE关键字支持通配符匹配，……other columns FROM cust，而且在其他方面还能简化优化器的工作，删除并重建索引可以提高查询速度。现在大多数的数据库产品都采用IBM最先提出的ISAM索引结构。索引的使用要恰到好处。3．消除对大型表行数据的顺序存取在嵌套查询中，对表的顺序存取对查询效率可能产生致命的影响。比如采用顺序存取策略;1001) OR order_num=1008虽然在customer_num和order_num上建有索引，两个表。避免这种情况的主要方法就是对连接的列进行索引。例如.balance，介绍改善用户查询计划的方法，rcvbles，如果每层都查询1000行，那么这个查询就要查询10亿行数据，在这种情况下也还是采用顺序扫描的方式。如果把语句改为SELECT ＊ FROM customer WHERE zipcode &“98000”，在执行查询时就会利用索引来查询，显然会大大提高速度。 另外，还要避免非开始的子串，可以把所有未付款的客户找出来放在一个临时文件中：●在经常进行连接，但是没有指定为外键的列上建立索引。另外，当数据库表更新大量数据后，rcvbles WHERE cust.customer_id = rcvlbes.customer_id AND rcvblls.balance&gt。因为这个语句要检索的是分离的行的集合，所以应该改为如下语句：SELECT ＊ FROM orders WHERE customer_num=104 AND order_num&1001UNIONSELECT ＊ FROM orders WHERE order_num=1008 这样就能利用索引路径处理查询。 4．避免相关子查询一个列的标签同时在主查询和where子句中的查询中出现，那么很可能当主查询中的列值改变之后，子查询必须重新查询一次。查询嵌套层次越多.balance。例如：SELECT ＊ FROM customer WHERE zipcode LIKE “98_ _ _” 即使在zipcode字段上建立了索引：学生表（学号、姓名。以下是一些影响因素，但相对于效率的提高是值得的）。如果排序不可避免：●索引中不包括一个或几个待排序的列。在一些数据库服务器上，索引可能失效或者因为频繁操作而使得读取效率降低，如果一个使用索引的查询不明不白地慢下来，可以试着用tbcheck工具检查索引的完整性
采纳率：91%
来自团队：
为您推荐：
其他类似问题
数据库的相关知识
换一换
回答问题，赢新手礼包程序员编程艺术（算法卷）：第十章、如何给10^7个数据量的磁盘文件排序
&&& 经过几天的痛苦沉思，最终决定，把原程序员面试题狂想曲系列正式更名为程序员艺术系列，同时，狂想曲创作组更名为编程艺术室。之所以要改名，我们考虑到三点：1、为面试服务不能成为我们最终或最主要的目的，2、我更愿把解答一道道面试题，ACM题等各类程序设计题目的过程，当做一种艺术来看待，3、艺术的提炼本身是一个非常非常艰难的过程，但我们乐意接受这个挑战。
&&& 同时，本系列程序编程艺术-算法卷，大致分为三个部分：第一部分--程序设计，大凡如面试题目/ACM题目/poj的题目等各类程序设计的题，只要是好的，值得设计或深究的题目，我们都不拒绝。同时，紧扣实际，不断寻找更高效的算法解决实际问题。第二部分--算法研究，主要以我个人此前写的原创作品-十三个经典算法研究系列为题材，力争通俗易懂，详略得当的剖析各类经典的算法，并予以编程实现。第三部分--编码素养，主要包括程序员编码过程中一些编码规范等各类及其需要注意的问题。
&&& 如果有可能的话，此TAOPP系列将采取TAOCP那样的形式，出第一卷、第二卷、...。编程艺术来自哪里?编程采取合适的数据结构?寻求更高效的算法?或者，好的编码规范?希望，本TAOPP系列最终能给你一个完整的答复。
&&& ok，如果任何人对本编程艺术系列有任何意见，或发现了本编程艺术系列任何问题，，bug，欢迎随时提出，我们将虚心接受并感激不尽，以为他人创造更好的价值，更好的服务。
第一节、如何给磁盘文件排序问题描述：输入：一个最多含有n个不重复的正整数的文件，其中每个数都小于等于n，且n=10^7。输出：得到按从小到大升序排列的包含所有输入的整数的列表。条件：最多有大约1MB的内存空间可用，但磁盘空间足够。且要求运行时间在5分钟以下，10秒为最佳结果。
分析：下面咱们来一步一步的解决这个问题，&&& 1、归并排序。你可能会想到把磁盘文件进行归并排序，但题目要求你只有1MB的内存空间可用，所以，归并排序这个方法不行。&&& 2、位图方案。熟悉位图的朋友可能会想到用位图来表示这个文件集合。例如正如编程珠玑一书上所述，用一个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。采取这个位图的方案是因为我们面对的这个问题的特殊性：1、输入数据限制在相对较小的范围内，2、数据没有重复，3、其中的每条记录都是单一的整数，没有任何其它与之关联的数据。&&& 所以，此问题用位图的方案分为以下三步进行解决：
第一步，将所有的位都置为0，从而将集合初始化为空。 第二步，通过读入文件中的每个整数来建立集合，将每个对应的位都置为1。 第三步，检验每一位，如果该位为1，就输出对应的整数。 &&& 经过以上三步后，产生有序的输出文件。令n为位图向量中的位数（本例中为），程序可以用伪代码表示如下：view plaincopy to clipboardprint?//磁盘文件排序位图方案的伪代码&& //copyright@ Jon Bentley&& //July、updated，。&& //第一步，将所有的位都初始化为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& //磁盘文件排序位图方案的伪代码//copyright@ Jon Bentley//July、updated，。//第一步，将所有的位都初始化为0for 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
&&& 上面只是为了简单介绍下位图算法的伪代码之抽象级描述。显然，咱们面对的问题，可不是这么简单。下面，我们试着针对这个要分两趟给磁盘文件排序的具体问题编写完整代码，如下。
view plaincopy to clipboardprint?//copyright@ yansha&& //July、。&& & //位图方案解决10^7个数据量的文件的排序问题&& //如果有重复的数据，那么只能显示其中一个 其他的将被忽略&& #include &iostream&&& #include &bitset&&& #include &assert.h&&& #include &time.h&&& && & const int max_each_scan = 5000000;&& & int main()&& {&& &&& clock_t begin = clock();&& &&& bitset&max_each_scan& bit_&& &&& bit_map.reset();&& &&&&&& &&& // open the file with the unsorted data&& &&& FILE *fp_unsort_file = fopen("data.txt", "r");&& &&& assert(fp_unsort_file);&& &&&&&& &&&&& &&& // the first time scan to sort the data between 0 - 4999999&& &&& while (fscanf(fp_unsort_file, "%d ", &num) != EOF)&& &&& {&& &&&&&&& if (num & max_each_scan)&& &&&&&&&&&&& bit_map.set(num, 1);&& &&& }&& &&&&&& &&& FILE *fp_sort_file = fopen("sort.txt", "w");&& &&& assert(fp_sort_file);&& &&&&&& &&&&& &&& // write the sorted data into file&& &&& for (i = 0; i & max_each_ i++)&& &&& {&& &&&&&&& if (bit_map[i] == 1)&& &&&&&&&&&&& fprintf(fp_sort_file, "%d ", i);&& &&& }&& &&&&&& &&& // the second time scan to sort the data between 5000000 - 9999999&& &&& int result = fseek(fp_unsort_file, 0, SEEK_SET);&& &&& if (result)&& &&&&&&& cout && "fseek failed!" &&&& &&& else& &&& {&& &&&&&&& bit_map.reset();&& &&&&&&& while (fscanf(fp_unsort_file, "%d ", &num) != EOF)&& &&&&&&& {&& &&&&&&&&&&& if (num &= max_each_scan && num & )&& &&&&&&&&&&& {&& &&&&&&&&&&&&&&& num -= max_each_&& &&&&&&&&&&&&&&& bit_map.set(num, 1);&& &&&&&&&&&&& }&& &&&&&&& }&& &&&&&&&&&& &&&&&&& for (i = 0; i & max_each_ i++)&&nbsp