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