資源描述：
《數(shù)據(jù)結(jié)構(gòu) C語(yǔ)言版 教學(xué)課件 作者 李云清 第11章_外排序.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。
1、數(shù)據(jù)結(jié)構(gòu)李云清楊慶紅揭安全第11章外排序在排序操作中，當(dāng)待排序數(shù)據(jù)量很大而內(nèi)存中無(wú)法存儲(chǔ)所有的數(shù)據(jù)時(shí)，僅僅使用內(nèi)排序是無(wú)法完成排序任務(wù)的，此時(shí)需要使用外存儲(chǔ)器進(jìn)行外排序。11.1外存儲(chǔ)器簡(jiǎn)介11.1.1磁盤存儲(chǔ)器11.1.2磁帶存儲(chǔ)器11.2文件簡(jiǎn)介11.2.1文件的邏輯結(jié)構(gòu)11.2.2文件的存儲(chǔ)結(jié)構(gòu)11.3外排序------磁盤排序11.3外排序------磁盤排序外排序中的主要方法是歸并排序法。這種排序方法主要由兩大步驟構(gòu)成。第一步，根據(jù)內(nèi)存可用空間的大小將待排序文件分成若干個(gè)子文件逐個(gè)調(diào)入內(nèi)存，
2、保證每個(gè)子文件都能利用選定的內(nèi)排序算法進(jìn)行排序，并將排序后的所有有序子文件再依次寫入外存。這些已排序的子文件稱為初始有序串。第二步，對(duì)這些有序串進(jìn)行逐趟歸并，使有序串的長(zhǎng)度不斷增大，而有序串的個(gè)數(shù)不斷減少。反復(fù)執(zhí)行第二步，直至得到整個(gè)有序文件為止。第一步的實(shí)質(zhì)是內(nèi)排序，第二步是外排序的主要內(nèi)容。11.3.1磁盤排序外排序中使用的外存是磁盤存儲(chǔ)器稱為磁盤排序。磁盤排序的思想用一個(gè)實(shí)例說(shuō)明。設(shè)有一個(gè)待排序文件含有54000個(gè)記錄：R1，R2，……，R54000。計(jì)算機(jī)系統(tǒng)中現(xiàn)有可用內(nèi)存空間可以對(duì)9000個(gè)
3、記錄進(jìn)行排序。待排序文件存放在磁盤上，設(shè)盤上每個(gè)塊可存放300個(gè)記錄，排序過(guò)程如下所述。首先，從磁盤上讀入30個(gè)塊共9000個(gè)記錄放入內(nèi)存，在內(nèi)存中進(jìn)行內(nèi)排序，得到一個(gè)有序串，反復(fù)進(jìn)行，整個(gè)文件每9000個(gè)記錄作一次內(nèi)排序，可以得到6個(gè)有序串S1,S2,S3,S4,S5,S6。每個(gè)初始有序串有30個(gè)塊組成，其中每個(gè)初始有序串在圖示中用3個(gè)小方框表示，每個(gè)小方框代表10個(gè)塊。其次，取3個(gè)內(nèi)存塊，每塊可放300個(gè)記錄。用其中兩塊作為輸入緩沖區(qū)，另一塊作為輸出緩沖區(qū)。先對(duì)有序串S1和S2進(jìn)行歸并，為此，可把
4、這兩個(gè)有序串中各自的第一個(gè)塊讀入分別寫入兩個(gè)輸入緩沖區(qū)，這兩個(gè)輸入緩沖區(qū)的記錄分別是有序的。利用上一章講述的歸并排序方法的思路，對(duì)兩個(gè)輸入緩沖區(qū)的記錄進(jìn)行歸并，將歸并結(jié)果寫入輸出緩沖區(qū)。歸并過(guò)程中，當(dāng)輸出緩沖區(qū)滿時(shí)，就將輸出緩沖區(qū)中的內(nèi)容寫入磁盤；當(dāng)一個(gè)輸入緩沖區(qū)騰空時(shí)，便把同一有序串的一下塊讀入，這樣不斷進(jìn)行，直到有序串S1和有序串S2的歸并完成。用同樣的方法將S3和S4、S5和S6分別歸并。這樣整個(gè)文件經(jīng)這一趟歸并后可以得到3個(gè)有序串。這趟歸并需要對(duì)整個(gè)文件中的所有記錄讀寫一次（即從磁盤上讀入內(nèi)存
5、一次，并從內(nèi)存寫到磁盤一次），并在內(nèi)存中參加一次歸并。反復(fù)對(duì)每?jī)蓚€(gè)有序串進(jìn)行歸并，最后得到一個(gè)有序串，即為排序結(jié)果。歸并過(guò)程見圖11.3.2多路歸并(略)
