一 對一個外部文件的排序問題的巧妙解決
1 問題的描述
輸入：
所輸入的是一個文件，至多包含n個正整數，每個正整數都要小于n，如果一個正整數出現了一次以上，那么說明出錯。
輸出：
以增序的方式輸出的整數數列。
約束 ：
至多只有1M的內存空間，但是可用磁盤空間非常大，運行時間至多只允許幾分鐘。
二 解決方案
輸入文件 -------------精彩排序------------------輸出文件
將數據一次性的全部倒入內存，我們才能獲得最快的速度。
實現細節：
用一個1000 萬位的位圖序列，來存儲這些整數，在位序列中 第i為若為1 ，表示整數集中含有整數 i 。
若為0則表示整數集中不包含 i 。定義該位圖序列之后，我們將編碼分為下面幾個部分。
(1) 首先清空該位圖序列
for(int i = 0 ; i < n ;i++)
bitmap[i] = 0 ;
(2) 從input 文件中讀取每一個整數，將對應的在位圖序列中的位置為1
while(i = read(file))
{
bitmap[i] = 1 ;
}
(3) 輸出位圖序列階段
for(int i = 0 ; i < n ; i++)
{
if(bitmap[i])
printf("&d" , i) ;
}
輸出序列即為最后的排序結果，很巧妙。 綜上問題解決。
三 感悟
1 問題精確地藐視 。
2 位圖數結構(在系統編程中常用，以后在編碼中應該熟練使用) ，java和c++中都有 BitSet類。
3 簡單的設計，完美地解決了上面的問題。