版权声明：本文为 DouMiaoO_Oo 原创文章，未经允许不得转载！

第一章

介绍

本章提出一个问题，电话号码有10位，前3位是固定区号800 ，后面还有7位数字，需要对这些电话号码进行排序。即：

输入： 一个最多包含n个正整数的文件，每个数都小于 $ n $ ，其中 $n =10^7 $。如果在输入文件中有任何整数重复出现就是致命错误。没有其他数据与该整数相关联。

输出：按升序排列的输入整数的列表

约束：最多有（大约）1 MB的内存空间可用，有充足的磁盘存储空间可用。运行时间最多几分钟，运行时间为10秒就不需要进一步优化了。

从这里我们可出，记录中只有正整数。约束条件是业务需求导致的。这里作者一步步提出了三种方法：

归并排序，即磁盘中的外部排序，读取一遍输入文件，但是需要多次读写工作文件（中间文件）多趟排序，因为1MB能保存 $25K$ 个数据，所以 $10^7$ 个 $\in [0,10^7]$ 的数可以划分为40个区间，可以通过多次读取输入文件来排序。对于第 $i$ 趟读取输入文件，我们可以排序大小在 $[25K\ast (i-1),25K\ast i)$ 区间内的数。位图或者位向量(bit vector/bit map) 来做。

在我目前看来，我觉得位向量和 桶排序（bucket sort）很类似，这里先记录一下。位向量就是一组bit构成的基本数据结构。 我们把可以用的1MB的内存利用二进制展开，这样能够得到的bit数目有 1024*1024*8 = 8,388,608。位向量就是指，从左往右看对于第i 个比特，如果这一位是1，则代表存在i这个数。举例来说：

给定一个byte，也就是8个bit。如果某组整数可以通过位图表示为 01010000，此时从左往右第5个和7个bit是1，所以这个位向量代表就是{5, 7} 这样一个集合。

书中通过额外提供了部分内存，得到 $10^7$ 个bit的内存（大约1.25MB），所以此时利用位向量可以在内存中保存全部的输入数据。

课后习题

2. 使用位运算实现位向量

const int BIT_PER_WORD = 32; //bits of int, depends on machine const int SHIFT = 5; // 2^5 = 32 const int MASK = 0x1F; // b'11111 = 10'32 class BitVector{ public: BitVector(int ElementNumber){ this->N = ElementNumber; this->intNumber = (N-1)/BIT_PER_WORD + 1; this->bit_vec = new int[intNumber]; } ~BitVector(){ delete [] this->bit_vec; } void clear(){ for(int i = 0; i < this->intNumber; ++i){ this->bit_vec[i] = 0; } } bool set(int i){ /* 1. 如果要set为1的bit位已经是1的话，返回 false。 因为任务中默认不会有重复，所以没有检测重复的情况。 2. i/BIT_PER_WORD = i>>SHIFT = j 代表set操作发生在第j个int上，即this->bit_vec[j] 3. i%BIT_PER_WORD = i&MASK = j 代表set操作会修改某个int的第j个bit */ this->bit_vec[i>>SHIFT] |= 1<<(i&MASK); return true; } bool contain(int i){ /* 判断i是否存在 */ return (this->bit_vec[i>>SHIFT]) & (1<<(i&MASK)); } private: int * bit_vec = NULL; // allocate space for bit vector int N; // element number int intNumber; // total int number allocate for bit vector };

版权声明：本文为 DouMiaoO_Oo 原创文章，未经博主允许不得转载！

参考文献

编程珠玑 第二版 修订版