"程式設計珠玑" 第一章 磁盤檔案排序問題

問題描述:

輸入: 一個最多包含n個正整數的檔案,每個數都小于n,其中 n = 10^7.如果在輸入檔案中

有任何整數重複出現就是緻命錯誤.沒有其他資料與該整數相關聯.

輸出: 按升序排列的輸入整數的清單

限制: 最多有(大約) 1MB 的記憶體空間可以使用,有充足的磁盤空間可以使用,運作時間最多

幾分鐘,運作時間最多為10s就不需要進一步優化了

問題分析:

顯而易見 說到排序大家第一個必然想到 快速排序, 

方案一: 快速排序 

那不妨讓我們先計算下快速排序整個文

件所需要的空間大小,假設資料以 32位int型存放

((10^7) * 32) /(8*1024*1024) = 38.14MB

38.14 / 1 = 39 次

是的 我們至少需要 (39 + 1) 次快速排序,需要将資料分40次讀入記憶體.那麼時間複雜度可想

而知.

方案二: 歸并排序

有興趣可以去查一下

方案三: 我了解為 基于hash的排序 下面我詳述一下

算法思想:

1 用 "位圖"(bitmap) 這種資料結構來進行存儲資料.

位圖: 該資料結構描述了一個有限定義域内的稠密集合,其中的每一個元素至多出現一次

并且沒有其他任何資料與該元素相關聯.即使這些條件沒有完全滿足,也可以用有限定義域

内的鍵作為一個表項更複雜的表格索引.

2 類似于hash排序的思想,用位圖存放所需要的記憶體大小為

(10^7)/(8*1024*1024) = 1.19MB

将記憶體空間的需求瞬間縮小到 1.19MB 使一次性讀入成為可能

算法代碼:

以下代碼僅作思想展現,實際意義并不大

#include <iostream>
#include <cmath>
#define MAX 4

using namespace std;

// 初始化字典數組
int Dic[32] = {0};

void InItDic(){
    for(int i = 0;i<32;i++)
        Dic[i] = pow(2,i);

}

int main(){
	// 申請大小為 312500的數組,當然直接申請這麼大的很容易崩潰,不推薦
    int array[312500] = {0};
    int i;
    int Wait[MAX] = {0};

    InItDic();

	// 生成待排序資料 也可以從硬碟中讀取
	
	for(i=0;i<MAX;i++){
        Wait[i] = MAX - i - 1;
    }

	// 進行排序
	/*
		具體解析:
			一個int有32位,即 312500 * 32 = 10^7
			将 待排序數/32 計算出應該存儲這個位的數字編号
			将 待排序數%32 計算出存儲在這個數的哪一二進制位
			然後将這一位置為1,我在此采用置1的方法是,将表示該位的數
			與原數做 按位或 運算
			
			最後按位周遊 得到的就是升序序列
	*/
    for(i=0;i<MAX;i++)
        array[Wait[i]/32] |= Dic[Wait[i]%32];

    cout << array[0];
}


// 個人見解 歡迎指正 不勝感激