weidagang2046的專欄

物格而后知致

隨筆 - 8, 文章 - 409, 評論 - 101, 引用 - 0

數據加載中……

位圖（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-10-28 15:25 weidagang2046 閱讀(641) 評論(0) 編輯收藏所屬分類: Others

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關文章: 開機自動打開"我的文檔"解決辦法自動彈出記事本名企面試試題——廣東北電幾家最好的IT公司面試全揭秘電腦高手最常用的六個組合鍵人民幣大寫 google面試題想進Google，先來做做Google招聘題(ZZ) 微軟筆試題max subsequence sum 問個昨天的MSN面試題

weidagang2046的專欄

位圖（bitmap）排序

導航

常用鏈接

留言簿(12)

隨筆檔案(8)

文章分類(421)

文章檔案(409)

相冊

Link

搜索

最新評論

閱讀排行榜

評論排行榜