位图排序

《编程珠玑》第一章第一题就相当的精彩，做个笔记。题目如下：
输入: 一个包含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));
    }
}

 

 

 

评论

4 楼 j_bird 2012-05-21  

你好，看了上面的代码个人有些疑问，想求教一下，主要疑问如下：
   
   1、a[i >> SHIFT] &= ~(1 << (i & MASK));  为什么要调用这段代码呢，申 明的整型数组默认值不都是0吗？
  2、i & MASK 为什么要做这步呢，直接用~(1 << i);是否可以呢？
  
  3、a[i >> SHIFT] &= ~(1 << (i & MASK)); 这样一位一位的清零快些还是以对数组的每个整型变量直接赋值0快些呢？
   还请赐教

3 楼 liuxuejin 2011-03-17  

不知道跟C的比起来，性能如何！

2 楼 fhtdy2004 2009-10-20  

//用int数组来模拟位数组，总计(1 + N / BITSPERWORD)*BITSPERWORD位，足以容纳N  
    private static int[] a = new int[(1 + N / BITSPERWORD)];  
请教一下，你开了一个312500个整数的数组，而1M只能存储250000个整数，这不是超过了内存的限制？

1 楼 txzyhm521 2008-03-26  

/** 
* Created by IntelliJ IDEA.
*/
破解的吧，告诉我版本和注册号