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


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