位图（bitmap）排序 - 午夜拍键惊奇 - BlogJava

首页新随笔新文章联系聚合

posts - 48,comments - 118,trackbacks - 79

位图（bitmap）排序

放假之前从图书馆借来《编程珠玑》，开篇便把我震住，作者以位图排序优雅地解决了一个现实问题：
有3000万个没有重复的电话号码，1M内存，外存比较充裕，需要将这3000万个电话排序
借此作者引出了位图排序：
位图排序是指以一个N位长的串，每位上以“1”或“0”表示需要排序的集合（后简称“集合”）中的数。比如集合为{2,7,4,9,1,10}，则生成一个10位的串，将第2、7、4、9、1、10位置为“1”，其余位置为“0”，这样当把串中所有位都置完后，排序也自动完成了（因为串的下标是有序的）：1101001011
位图排序的代码如下：

public void bitmapSort(int[] set){

int max=max(set);

int[] array=new int[max];

for(int i=0;i<array.length;i++)

array[i]=0;

for(int i=0;i<set.length;i++)

array[set[i]]=1;

for(int i=0;i<array.length;i++){

if(array[i]==1)

System.out.println(i+” ”);

}

}

private int max(int[] set){

// return the maxium integer of the set

}

可以看出，位图排序的时间复杂度是O(n)的，比一般的排序都快，但它是以空间换时间（需要一个N位的串），而且有一些限制，比如排序前集合大小最好已知，而且集合中元素的最大重复次数必须已知，最好是稠集数据（不然空间浪费很大）。

posted on 2005-02-13 22:17 ^ Mustang ^ 阅读(1480) 评论(4) 编辑收藏所属分类: 基础理论

FeedBack:

# re: 位图（bitmap）排序

2005-12-16 13:44 | 我的万花@

绝！不知道谁发明的回复更多评论

# re: 位图（bitmap）排序

2005-12-16 13:45 | 我的万花@

不过看你写的文字看不懂，还是要看代码，嘿嘿
回复更多评论

# re: 位图（bitmap）排序

2008-10-04 12:14 | haibo

这段代码是错的，不能用integer array, 只能用BitArray, 否则，在内存受限的情况下，你是不能把所有的的数装下的。所谓的位图排序也是这个意思回复更多评论

# re: 位图（bitmap）排序

2009-08-27 12:51 | zhangdp

为了更节省时间应该用 BitArray 回复更多评论

新用户注册刷新评论列表


只有注册用户登录后才能发表评论。




网站导航: 博客园 IT新闻知识库 C++博客博问管理