最近看到这个问题，抽时间看了一下。
在编程珠玑里面，对于这个问题有很详尽的描述，这里我将读后感发出来与大家共享。
众所周知，磁盘文件往往很大，而内存很小，在给磁盘文件的排序过程中，磁盘访问时间远远大于内存里面的排序时间，想要快速将磁盘文件排序输出，就要尽量的避免多次访问磁盘。
常规的做法是基于磁盘的归并排序，其思想十分简单：一次性读入输入文件，在内存中进行归并排序，期间需要多次访问工作文件，最后输出文件一次。这种做法使得程序需要频繁的访问磁盘工作文件，磁盘的存取速度大大的拖延了程序的运行时间，性能比较低下。
为了尽量减少磁盘的访问次数，出现了一种新的做法：根据内存大小大致将磁盘文件分成有限的n等份（分的时候需要确定数据范围，例如第一份包含0-999的任何存在的数字，第二份包含1000-1999的任何存在数字......），每次将一份数据读入内存进行排序，最后输出。在这种情况下，由于不再使用中间文件，程序只需要访问磁盘n+1次即可完成全部排序，在时间和空间上都比第一种有所优化。
那么以上问题引发了以下思考，是否存在一种方法，只需读取和输出磁盘文件各一次，就能完成全部排序？
位图法可以解决这个问题。
以上受限于内存空间大小，我们无法一次读入所有数据进行处理。但是如果我们把每一个位（bit）都表示一个数，这个问题就能得到大大缓解。
比如我们把一个连续空间的第8位置1表示文件中存在数字8，置0表示不存在数字8，那么100MB的空间就能存储100*（2^20）*8个数。
那么问题来了，当我输入一个数字i的时候，我们怎么把它存在第i位呢；当我知道第i为1的时候，我们怎么转化为数字i输出呢；这就要先明白什么是位向量。
位向量：由一些二进制位组成的向量，用来存储一个数
示例：
对于32位的int类型 a[0]表示第1-32个数：0-31
a[1]表示第33-64个数：32-63
例如：数据i=31 对应位向量： i/32=0 表示在a[0]单元上
i%32=31 表示在a[0]的第31位上.1<<(i%32
对应程序为：a[i/32]=a[i/32]|(1<<(i%32))
改用位运算：a[i>>5] |= (1<<(i & 0x1F))
这里是一个可运行实例：
这样，磁盘排序的性能就比前2种方法大大提升了。
水平所限，难免有错，欢迎交流。
网友评论