午夜拍键惊奇
子夜 编程 代码与我同在
posts - 48,comments - 118,trackbacks - 79
放假之前从图书馆借来《编程珠玑》,开篇便把我震住,作者以位图排序优雅地解决了一个现实问题:
有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 ^ 阅读(1476) 评论(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  回复  更多评论
  

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


网站导航: