《程式設計珠玑》讀書筆記第一章

解決一個排序問題

描述

輸入：

一個最多包含n個正整數的檔案，每個數都小于n，n=10^7，沒有重複資料，資料之間互不關聯。

輸出：

按升序排列的整數清單。

限制：

最多有1MB記憶體空間可用，運作時間最多幾分鐘。

解決問題

條件：

• 輸入資料限制在較小的範圍内
• 沒有重複資料
• 每條資料互補關聯

限制：

空間有限，需要用特殊方法表示資料集合

方法：

1. 普通歸并排序（讀入一次，工作檔案多次讀寫排序）

2. 利用條件特殊性，周遊檔案40遍，每一次周遊取從小到大的250000個資料，進行排序後輸出（讀取40次，輸出一次，不使用中間檔案）

3. 結合1,2，讀入一次，且不使用中間檔案

需要解決的問題轉化為：是否能用800W可用位來标示最多1000W個互異的整數，考慮合适的表示方式。

用位圖方法表示集合：

輸入資料為7位數，是以都小于1000W，使用一個1000W位長的字元串，當整數i在集合中時，第i位為1，否則為0.

實作步驟

1. 将所有位置為0，初始化集合
2. 讀入檔案中的資料，将相應位置的資料置為1
3. 檢驗字元串中每一位，若為1，就輸出該檔案。