目錄
- 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