放假之前從圖書館借來《編程珠璣》，開篇便把我震住，作者以位圖排序優(yōu)雅地解決了一個(gè)現(xiàn)實(shí)問題：
有3000萬個(gè)沒有重復(fù)的電話號(hào)碼，1M內(nèi)存，外存比較充裕，需要將這3000萬個(gè)電話排序
借此作者引出了位圖排序：
位圖排序是指以一個(gè)N位長(zhǎng)的串，每位上以“1”或“0”表示需要排序的集合（后簡(jiǎn)稱“集合”）中的數(shù)。比如集合為{2,7,4,9,1,10}，則生成一個(gè)10位的串，將第2、7、4、9、1、10位置為“1”，其余位置為“0”，這樣當(dāng)把串中所有位都置完后，排序也自動(dòng)完成了（因?yàn)榇南聵?biāo)是有序的）：1101001011
位圖排序的代碼如下：


可以看出，位圖排序的時(shí)間復(fù)雜度是O(n)的，比一般的排序都快，但它是以空間換時(shí)間（需要一個(gè)N位的串），而且有一些限制，比如排序前集合大小最好已知，而且集合中元素的最大重復(fù)次數(shù)必須已知，最好是稠集數(shù)據(jù)（不然空間浪費(fèi)很大）。