《编程珠玑》第一章第一题就相当的精彩，做个笔记。题目如下：
输入: 一个包含n个正整数的文件，每个正整数小于n,n等于10的7次方（一千万）。并且文件内的正整数没有重复和关联数据。
输出: 输入整数的升序排列
约束： 限制在1M左右内存，充足的磁盘空间
假设整数占32位，1M内存可以存储大概250000个整数，第一个方法就是采用基于磁盘的合并排序算法，第二个办法就是将0-9999999切割成40个区间，分40次扫描（10000000/250000)，每次读入250000个在一个区间的整数，并在内存中使用快速排序。书中提出的第三个解决办法是采用bitmap（或者称为bit vector）来表示所有数据集合（注意到条件，数据没有重复），这样就可以一次性将数据读入内存，减少了扫描次数。算法的伪代码如下：
阶段1：初始化一个空集合
for i=[0,n)
bit[i]=0;
阶段2：读入数据i，并设置bit[i]=1
for each i in the input file
bit[i]=1;
阶段3：输出排序的结果
for i=[0,n)
if bit[i]==1
write i on the output file
这个算法的时间复杂度在O(n)，用c语言写的版本可以在10秒内完成任务！c语言的源码在该书主页上有，这里给一个java的测试版，加上我的理解注释：
/**
* Created by IntelliJ IDEA.
* User: zhuangxd
* Date: 2008-1-7
* Time: 14:30:44
*/
public class BitSortTest {
private static final int BITSPERWORD = 32 ; // 整数位数
private static final int SHIFT = 5 ;
private static final int MASK = 0x1F ; // 5位遮蔽 0B11111
private static final int N = 10000000 ;
// 用int数组来模拟位数组，总计(1 + N / BITSPERWORD)*BITSPERWORD位，足以容纳N
private static int [] a = new int [( 1 + N / BITSPERWORD)];
public static void main(String[] args) {
bitsort( new int []{ 1 , 100 , 2 , 10000 , 9999 , 4567 , 78902 });
}
public static void bitsort( int [] array) {
for ( int i = 0 ; i < N; i ++ )
clr(i); // 位数组所有位清0
for ( int i = 0 ; i < array.length; i ++ )
set(array[i]); // 阶段2
for ( int i = 0 ; i < N; i ++ )
if (test(i))
System.out.println(i);
}
// 置a[i>>SHIFT]的第(i & MASK)位为1， 也就是位数组的第i位为1
public static void set( int i) {
a[i >> SHIFT] |= ( 1 << (i & MASK));
}
// 置a[i>>SHIFT]的第(i & MASK)位为0,也就是位数组的第i位为0
public static void clr( int i) {
a[i >> SHIFT] &= ~ ( 1 << (i & MASK));
}
// 测试位数组的第i位是否为1
public static boolean test( int i) {
return (a[i >> SHIFT] & ( 1 << (i & MASK))) == ( 1 << (i & MASK));
}
}
输入: 一个包含n个正整数的文件，每个正整数小于n,n等于10的7次方（一千万）。并且文件内的正整数没有重复和关联数据。
输出: 输入整数的升序排列
约束： 限制在1M左右内存，充足的磁盘空间
假设整数占32位，1M内存可以存储大概250000个整数，第一个方法就是采用基于磁盘的合并排序算法，第二个办法就是将0-9999999切割成40个区间，分40次扫描（10000000/250000)，每次读入250000个在一个区间的整数，并在内存中使用快速排序。书中提出的第三个解决办法是采用bitmap（或者称为bit vector）来表示所有数据集合（注意到条件，数据没有重复），这样就可以一次性将数据读入内存，减少了扫描次数。算法的伪代码如下：
阶段1：初始化一个空集合
for i=[0,n)
bit[i]=0;
阶段2：读入数据i，并设置bit[i]=1
for each i in the input file
bit[i]=1;
阶段3：输出排序的结果
for i=[0,n)
if bit[i]==1
write i on the output file
这个算法的时间复杂度在O(n)，用c语言写的版本可以在10秒内完成任务！c语言的源码在该书主页上有，这里给一个java的测试版，加上我的理解注释：
/**
* Created by IntelliJ IDEA.
* User: zhuangxd
* Date: 2008-1-7
* Time: 14:30:44
*/
public class BitSortTest {
private static final int BITSPERWORD = 32 ; // 整数位数
private static final int SHIFT = 5 ;
private static final int MASK = 0x1F ; // 5位遮蔽 0B11111
private static final int N = 10000000 ;
// 用int数组来模拟位数组，总计(1 + N / BITSPERWORD)*BITSPERWORD位，足以容纳N
private static int [] a = new int [( 1 + N / BITSPERWORD)];
public static void main(String[] args) {
bitsort( new int []{ 1 , 100 , 2 , 10000 , 9999 , 4567 , 78902 });
}
public static void bitsort( int [] array) {
for ( int i = 0 ; i < N; i ++ )
clr(i); // 位数组所有位清0
for ( int i = 0 ; i < array.length; i ++ )
set(array[i]); // 阶段2
for ( int i = 0 ; i < N; i ++ )
if (test(i))
System.out.println(i);
}
// 置a[i>>SHIFT]的第(i & MASK)位为1， 也就是位数组的第i位为1
public static void set( int i) {
a[i >> SHIFT] |= ( 1 << (i & MASK));
}
// 置a[i>>SHIFT]的第(i & MASK)位为0,也就是位数组的第i位为0
public static void clr( int i) {
a[i >> SHIFT] &= ~ ( 1 << (i & MASK));
}
// 测试位数组的第i位是否为1
public static boolean test( int i) {
return (a[i >> SHIFT] & ( 1 << (i & MASK))) == ( 1 << (i & MASK));
}
}
文章转自庄周梦蝶 ，原文发布时间2008-01-07
