问题分析
本题解答分成以下几个步骤：
1. 创建一个用来测试的数据文件（ 内含10000000个整数 ）
2. 编写位向量版的排序程序
3. 测试2中排序程序所用时间和本章第 1 题排序所用时间
第一步：创建一个用来测试的数据文件（ 内含10000000个整数 ）
这里我编写了一个小程序来创建这个数据文件，代码如下：
1 #include2 #include 3 #include 4 #include 5 6 using namespace std; 7 8 #define N 10000000 9 10 int main()11 {12 string filename;13 cout << "输入要创建的数据文件名: " << endl;14 cin >> filename;15 16 fstream io;17 io.open(filename.c_str(), fstream::out);18 if (!io) {19 cout << "打开文件失败！" << endl;20 return 1;21 }22 23 /*24 * 使用随机数函数产生随机数并存进文件25 */26 for (int i=0; i
编译运行后即可获得一个新的目标数据文件（ 数据文件文件名由用户指定 ）。
第二步：编写位向量版的排序
1 #include2 #include 3 #include 4 5 using namespace std; 6 7 // 每个整数的位数 8 #define BITSPERWORD 32 9 // 每次位移量10 #define SHIFT 511 // 取模掩码12 #define MASK 0x1F13 // 位向量的元素个数14 #define N 1000000015 16 // 模拟数组17 int a[1 + N/BITSPERWORD];18 19 /*20 * 函数功能：置位向量第i位为121 * 函数说明：" i>>SHIFT "等于" i/32 " 获取到位向量目标位对应的模拟数组元素的位置22 " i & MASK "等于" i%32 " 获取到位向量目标位在对应的模拟数组元素中的位置23 " 1<<(i & MASK) " 表示一个除了要设置的那位其他位都是0的整数24 */25 void set (int i) {26 a[i>>SHIFT] |= (1<<(i & MASK));27 }28 29 /*30 * 函数功能：置位向量第i位为031 * 函数说明：" i>>SHIFT "等于" i/32 " 获取到位向量目标位对应的模拟数组元素的位置32 " i & MASK "等于" i%32 " 获取到位向量目标位在对应的模拟数组元素中的位置33 " 1<<(i & MASK) " 表示一个除了要清空的那位其他位都是0的整数34 */35 void clr (int i) {36 a[i>>SHIFT] &= ~(1<<(i & MASK));37 }38 39 /*40 * 函数功能：获取位向量的第i位41 * 函数说明：" i>>SHIFT "等于" i/32 " 获取到位向量目标位对应的模拟数组元素的位置42 " i & MASK "等于" i%32 " 获取到位向量目标位在对应的模拟数组元素中的位置43 " 1<<(i & MASK) " 表示一个除了要获取的那位其他位都是0的整数44 */45 int tst (int i) {46 return a[i>>SHIFT] & (1<<(i & MASK));47 }48 49 50 int main()51 {52 /*53 * 清空位向量54 */55 for (int i=0; i < N; i++) {56 clr(i);57 }58 59 string filename;60 cout << "输入数据文件名( 当前目录下 )：";61 cin >> filename;62 63 fstream io;64 io.open(filename.c_str());65 if (!io) {66 cout << "打开文件失败" << endl;67 return 1;68 }69 70 /*71 * 根据数据文件记录给位向量赋值72 * 赋值完了以后其实已经" 完成排序了 "73 */74 int data;75 while (io >> data) {76 set(data);77 }78 79 io.close();80 io.clear();81 io.open(filename.c_str(), fstream::out | fstream::trunc);82 83 /*84 * 从位向量获取数据并写回数据文件85 */86 for (int i=0; i
运行测试参见下一步
第三步：测试2中排序所用时间和本章第 1 题排序所用时间
用第一步中的程序创建一个数据文件并拷贝一份，然后用上面的排序程序处理数据文件并获取运行时间，再用本章第一题的排序程序处理数据文件的拷贝并获取运行时间，比较之：
很显然，本书作者给出的排序效率很高，接近第一题中排序程序的两倍。
说明
不知道怎么测试程序运行时间的话