目錄
- 1.大型結(jié)構(gòu)的排序
- 2.外部排序
2.1 基于磁盤的歸并排序
2.2 編程珠璣上的排序問題（沒有重復(fù)的數(shù)據(jù)）
1.大型結(jié)構(gòu)的排序
在對(duì)大型結(jié)構(gòu)進(jìn)行排序時(shí)暴区，可以通過讓輸入數(shù)組包含指向結(jié)構(gòu)的指針實(shí)現(xiàn)射亏。
通過比較指針指向的關(guān)鍵字朴恳，并在必要時(shí)交換指針來進(jìn)行排序灸叼。
2.外部排序
外部排序指的是遵馆，存在一些應(yīng)用蜡塌，輸入的數(shù)據(jù)量太大不能裝進(jìn)內(nèi)存蜜另。
2.1 基于磁盤的歸并排序
假設(shè)文件中整數(shù)個(gè)數(shù)為N(N是億級(jí)的)适室，整數(shù)之間用空格分開。首先分多次從該文件中讀取M（十萬級(jí)）個(gè)整數(shù)举瑰，每次將M個(gè)整數(shù)在內(nèi)存中使用快速排序之后存入臨時(shí)文件捣辆，然后使用多路歸并將各個(gè)臨時(shí)文件中的數(shù)據(jù)再次整體排好序后存入輸出文件。顯然此迅，該排序算法需要對(duì)每個(gè)整數(shù)做2次磁盤讀和2次磁盤寫汽畴。
這里是不是可以充分利用緩存、內(nèi)存耸序，一次性從每個(gè)文件讀入M/D忍些，其中M為內(nèi)存總數(shù)，D為多路結(jié)果的個(gè)數(shù)坎怪。
將每個(gè)文件最開始的數(shù)讀入(由于有序罢坝，所以為該文件最小數(shù))，存放在一個(gè)大小為40的first_data數(shù)組中搅窿；
選擇first_data數(shù)組中最小的數(shù)min_data嘁酿，及其對(duì)應(yīng)的文件索引index隙券；
將first_data數(shù)組中最小的數(shù)寫入文件result，然后更新數(shù)組first_data(根據(jù)index讀取該文件下一個(gè)數(shù)代替min_data)闹司；
判斷是否所有數(shù)據(jù)都讀取完畢娱仔，否則返回2。
2.2 編程珠璣上的排序問題（沒有重復(fù)的數(shù)據(jù)）
解法的偽代碼：
1）使用位邏輯運(yùn)算實(shí)現(xiàn)位向量
2）實(shí)現(xiàn)位圖排序
3）怎樣限制內(nèi)存使用量
參考《編程珠璣》
參考：http://blog.csdn.net/v_JULY_v/article/details/6451990
參考：http://blog.csdn.net/v_JULY_v/article/details/6279498
