講義說明教案講稿d

1、11.111.1 外存信息的存取外存信息的存取l外部排序：外部排序：指的是大文件的排序，即待指的是大文件的排序，即待排序的記錄存儲在外部存儲器上，在排排序的記錄存儲在外部存儲器上，在排序過程中需要多次進行內(nèi)、外存間的交序過程中需要多次進行內(nèi)、外存間的交換。換。l外部排序的機制是由外部排序的機制是由外部存儲器存取信外部存儲器存取信息息的特點決定。的特點決定。第 2 頁第 3 頁主存儲器和外存儲器主存儲器和外存儲器l主存儲器主存儲器 ( primary memory 或或 main memory，簡稱內(nèi)存簡稱內(nèi)存/主存主存) 隨機訪問存儲器隨機訪問存儲器( RAM )高速緩存高速緩存( cache

2、 )。 l外存儲器外存儲器 ( peripheral storage 或或 secondary storage，簡稱外存，簡稱外存) 硬盤硬盤 / 軟盤軟盤 / 磁帶磁帶 / U盤盤11.111.1 外存信息的存取外存信息的存取第 4 頁l磁盤的物理結構磁盤的物理結構11.111.1 外存信息的存取外存信息的存取11.111.1 外存信息的存取外存信息的存取第 5 頁第 6 頁l磁盤磁片的組織磁盤磁片的組織11.111.1 外存信息的存取外存信息的存取第 7 頁l磁盤的存取步驟磁盤的存取步驟:選定某個盤片組選定某個盤片組選定某個柱面選定某個柱面n這需要把磁頭移動到該柱面這需要把磁頭移動到該柱面

3、 ，這個移動這個移動過程稱為過程稱為尋道尋道( seek ) 確定磁道確定磁道 確定所要讀寫的數(shù)據(jù)在磁盤上的準確位置確定所要讀寫的數(shù)據(jù)在磁盤上的準確位置n這段時間一般稱為這段時間一般稱為旋轉延遲旋轉延遲( rotational delay ( rotational delay 或者或者rotational rotational latency )latency )真正進行讀寫真正進行讀寫11.111.1 外存信息的存取外存信息的存取第 8 頁l磁盤的存取時間磁盤的存取時間11.111.1 外存信息的存取外存信息的存取間間時時輸輸傳傳磁道磁道尋道尋道時間時間磁臂磁臂等等待待 時時間間數(shù)數(shù)據(jù)據(jù)信信

4、息息磁磁盤盤旋旋轉轉方方向向第 9 頁l扇區(qū)的組織（交錯法扇區(qū)的組織（交錯法 interleaving）11.111.1 外存信息的存取外存信息的存?。╝ a）沒有扇區(qū)交錯）沒有扇區(qū)交錯 （b b）以）以3 3為交錯因子為交錯因子第 10 頁l磁盤的存取時間磁盤的存取時間磁盤訪問時間主要由磁盤訪問時間主要由尋道時間尋道時間、旋轉延遲旋轉延遲時間時間和和數(shù)據(jù)傳輸時間數(shù)據(jù)傳輸時間組成。組成。 尋道時間（尋道時間（Seek time）t tseekseek：是：是移動磁盤移動磁盤臂，定位到正確磁道所需的時間。臂，定位到正確磁道所需的時間。旋轉延遲時間旋轉延遲時間t tlala：是：是等待被存取的扇區(qū)

5、出等待被存取的扇區(qū)出現(xiàn)在讀寫頭下所需的時間?，F(xiàn)在讀寫頭下所需的時間。傳輸時間傳輸時間t twmwm：是：是傳輸字符的時間。傳輸字符的時間。T TI/OI/O=t=tseek seek + t+ tlala + t + twmwm11.111.1 外存信息的存取外存信息的存取第 11 頁l磁帶運行示意磁帶運行示意11.111.1 外存信息的存取外存信息的存取 磁帶卷在一個卷盤上，運行時磁帶經(jīng)過讀磁帶卷在一個卷盤上，運行時磁帶經(jīng)過讀寫磁頭，把磁帶上的信息讀入計算機，或把計寫磁頭，把磁帶上的信息讀入計算機，或把計算機中的信息寫在磁帶上算機中的信息寫在磁帶上。第 12 頁l外存的特點外存的特點優(yōu)點：優(yōu)

6、點：永久存儲能力、便攜性永久存儲能力、便攜性 缺點：訪問時間長缺點：訪問時間長訪問磁盤中的數(shù)據(jù)比訪問內(nèi)存慢五六個數(shù)訪問磁盤中的數(shù)據(jù)比訪問內(nèi)存慢五六個數(shù)量級量級。 因此，在對外存的數(shù)據(jù)結構及其上的操作因此，在對外存的數(shù)據(jù)結構及其上的操作時，必須遵循的基本原則是：時，必須遵循的基本原則是：盡量減少訪外盡量減少訪外次數(shù)！次數(shù)！ 11.111.1 外存信息的存取外存信息的存取第 13 頁為什么需要文件管理和外部排序？為什么需要文件管理和外部排序？l文件結構（文件結構（file structure）：）：數(shù)據(jù)量太大不可能同時都放到內(nèi)存中，所數(shù)據(jù)量太大不可能同時都放到內(nèi)存中，所以需要把全部數(shù)據(jù)放到外部存儲

7、設備上。以需要把全部數(shù)據(jù)放到外部存儲設備上。對于在外存中存儲的數(shù)據(jù)，其數(shù)據(jù)結構就對于在外存中存儲的數(shù)據(jù)，其數(shù)據(jù)結構就稱為文件結構。稱為文件結構。l對文件的對文件的各種操作各種操作：外部排序是針對外存文件所進行的外部排序是針對外存文件所進行的排序操排序操作，是文件的作，是文件的基礎操作基礎操作；高效的外部排序；高效的外部排序可以可以提高文件存儲效率和其他操作的效率。提高文件存儲效率和其他操作的效率。11.111.1 外存信息的存取外存信息的存取第 14 頁l文件上的操作文件上的操作l檢索檢索：在文件中尋找滿足一定條件的記錄在文件中尋找滿足一定條件的記錄 l修改修改：對記錄中某些數(shù)據(jù)值進行修改。若

8、對：對記錄中某些數(shù)據(jù)值進行修改。若對關鍵字進行修改，就相當于刪除加插入。關鍵字進行修改，就相當于刪除加插入。l插入插入：向文件中增加一個新記錄。向文件中增加一個新記錄。 l刪除刪除：從文件中刪去一個記錄：從文件中刪去一個記錄 。l排序排序 ：對指定好的數(shù)據(jù)項，按其值的大小把對指定好的數(shù)據(jù)項，按其值的大小把文件中的記錄排成序列。常用的是按關鍵字文件中的記錄排成序列。常用的是按關鍵字的排序。的排序。 11.111.1 外存信息的存取外存信息的存取第 15 頁l外存文件的組織外存文件的組織 文件是一些記錄的集合，每個記錄可由文件是一些記錄的集合，每個記錄可由一個或多個數(shù)據(jù)項組成。一個或多個數(shù)據(jù)項組成

9、。 數(shù)據(jù)項也稱為字段，或屬性。數(shù)據(jù)項也稱為字段，或屬性。11.111.1 外存信息的存取外存信息的存取職工號職工號姓名姓名性別性別職務職務婚姻狀況婚姻狀況工資工資156張東張東男男程序員程序員未婚未婚7800860李珍李珍女女分析員分析員已婚已婚8900510趙莉趙莉女女程序員程序員未婚未婚6900950陳萍陳萍女女程序員程序員未婚未婚6200620周力周力男男分析員分析員已婚已婚10300第 16 頁l邏輯文件邏輯文件對高級程序語言的編程人員而言，磁盤中可以隨機對高級程序語言的編程人員而言，磁盤中可以隨機訪問的文件訪問的文件被當作一段連續(xù)的字節(jié)被當作一段連續(xù)的字節(jié)，且可將這些字，且可將這些字

10、節(jié)結合起來構成記錄，這種文件被稱為邏輯文件。節(jié)結合起來構成記錄，這種文件被稱為邏輯文件。l物理文件物理文件實際存儲在磁盤中的物理文件通常實際存儲在磁盤中的物理文件通常不是一段連續(xù)的不是一段連續(xù)的字節(jié)，而是字節(jié)，而是成塊地分布成塊地分布在整個磁盤中。在整個磁盤中。l文件管理文件管理是操作系統(tǒng)的一部分，當應用程序請求從邏輯文件是操作系統(tǒng)的一部分，當應用程序請求從邏輯文件中讀取數(shù)據(jù)時，它將這些中讀取數(shù)據(jù)時，它將這些邏輯位置映射為磁盤中具邏輯位置映射為磁盤中具體的物理位置體的物理位置。11.111.1 外存信息的存取外存信息的存取第 17 頁l文件的邏輯結構文件的邏輯結構文件是記錄的集合文件是記錄的集

11、合。當一個文件的各個記錄按照某種次序排列當一個文件的各個記錄按照某種次序排列起來時，各記錄間就自然地形成了一種線起來時，各記錄間就自然地形成了一種線性關系。性關系。 因而，文件可看成是一種線性結構。因而，文件可看成是一種線性結構。 11.111.1 外存信息的存取外存信息的存取l文件的物理結構文件的物理結構l順序結構順序結構順序文件順序文件 l計算尋址結構計算尋址結構散列文件散列文件 l帶索引的結構帶索引的結構帶索引文件帶索引文件 第 18 頁l文件的物理結構文件的物理結構p順序文件：記錄按照自然次序依次存儲順序文件：記錄按照自然次序依次存儲1.存取第存取第 i 個記錄之前，必須存取第個記錄之

12、前，必須存取第 i-1 個記錄個記錄2.新記錄只能插在文件尾部新記錄只能插在文件尾部3.更新文件中的數(shù)據(jù)必須將整個文件復制一遍更新文件中的數(shù)據(jù)必須將整個文件復制一遍p散列文件：利用散列文件：利用散列函數(shù)和沖突處理散列函數(shù)和沖突處理p索引文件：帶有按關鍵字數(shù)據(jù)項進行索引索引文件：帶有按關鍵字數(shù)據(jù)項進行索引的文件的文件n虛擬存儲存取方式虛擬存儲存取方式VSAM：索引順序文件用：索引順序文件用B+樹作為動態(tài)索引樹樹作為動態(tài)索引樹11.111.1 外存信息的存取外存信息的存取第 19 頁l外部排序外部排序( External Sort )產(chǎn)生的緣由產(chǎn)生的緣由：由于文件很大，無法把整個：由于文件很大，無

13、法把整個文件的所有記錄同時調(diào)入內(nèi)存中進行排序，文件的所有記錄同時調(diào)入內(nèi)存中進行排序，即即無法進行內(nèi)部排序無法進行內(nèi)部排序。對對外存設備上外存設備上（文件（文件）進行）進行的排序技術。的排序技術。 l外部排序算法的主要目標：外部排序算法的主要目標：盡量減少讀盡量減少讀寫磁盤的次數(shù)寫磁盤的次數(shù) 。11.211.2 外部排序的方法外部排序的方法第 20 頁l順串：順串：用某種有效的用某種有效的內(nèi)排序方法內(nèi)排序方法對組成對組成文件的各段文件的各段/ /子文件進行初始排序后重新子文件進行初始排序后重新寫回外存的段或子文件被稱為寫回外存的段或子文件被稱為歸并段歸并段或或順串順串(run) (run) 。l

14、外部排序的過程：外部排序的過程：把文件分成若干盡可能長的初始把文件分成若干盡可能長的初始順串順串。逐步歸并順串（或歸并段），最后形成一逐步歸并順串（或歸并段），最后形成一個已排序的文件。個已排序的文件。11.211.2 外部排序的方法外部排序的方法第 21 頁l外部排序的時間開銷：外部排序的時間開銷：總時間總時間 =內(nèi)部排序產(chǎn)生初始順段內(nèi)部排序產(chǎn)生初始順段 時間時間 +外存信息讀寫時間外存信息讀寫時間 +內(nèi)部歸并所需時間內(nèi)部歸并所需時間 = m* *tis + d* *tio + s* *utmg其中：其中：tis：得到一個初始歸并段進行內(nèi)部排序所需時間：得到一個初始歸并段進行內(nèi)部排序所需時間

15、m：經(jīng)過內(nèi)排序后得到的初始歸并段的數(shù)量：經(jīng)過內(nèi)排序后得到的初始歸并段的數(shù)量tio：進行一次外存讀寫的時間：進行一次外存讀寫的時間d：總的讀：總的讀/寫次數(shù)寫次數(shù)utmg：對：對 u 個記錄進行內(nèi)部歸并所需時間個記錄進行內(nèi)部歸并所需時間s：歸并的趟數(shù)：歸并的趟數(shù)11.211.2 外部排序的方法外部排序的方法第 22 頁p減少外存信息的讀寫次數(shù)減少外存信息的讀寫次數(shù)是提高外部排序效是提高外部排序效率的關鍵率的關鍵 ：l對同一個文件而言，進行外排序所需讀寫外對同一個文件而言，進行外排序所需讀寫外存的存的次數(shù)與歸并趟數(shù)成正比關系。次數(shù)與歸并趟數(shù)成正比關系。l假設有假設有m個初始順串，每次對個初始順串，

16、每次對k個順串進行歸個順串進行歸并，其歸并趟數(shù)為并，其歸并趟數(shù)為logkm。p為了減少歸并趟數(shù)，可以從兩個方面著手：為了減少歸并趟數(shù)，可以從兩個方面著手：減少初始順串的個數(shù)減少初始順串的個數(shù)m m增加歸并的順串數(shù)量增加歸并的順串數(shù)量k k11.211.2 外部排序的方法外部排序的方法第 23 頁p外部排序基本做法的描述：外部排序基本做法的描述：假定文件有假定文件有4500個記錄：個記錄：R1, R2, , R4500。磁。磁盤上盤上 1 塊（即塊（即1 個扇區(qū)）的尺寸是個扇區(qū)）的尺寸是250個記錄個記錄，該文件總共需用磁盤的，該文件總共需用磁盤的 18 個扇區(qū)。內(nèi)存可個扇區(qū)。內(nèi)存可供用于排序的

17、空間是供用于排序的空間是 750 個記錄大小。個記錄大小。p排序過程如下：排序過程如下： 每次從磁盤讀入每次從磁盤讀入 3 塊（塊（750個記錄）到內(nèi)存，利用內(nèi)排序算法將它們個記錄）到內(nèi)存，利用內(nèi)排序算法將它們排好序，然后寫回磁盤。這樣，磁盤上就得排好序，然后寫回磁盤。這樣，磁盤上就得到了到了6個初始有序段個初始有序段A1、A2、A6。 11.211.2 外部排序的方法外部排序的方法初始有序段初始有序段A11750有序段有序段A27511500有序段有序段A315012250有序段有序段A422513000有序段有序段A530013750有序段有序段A637514500第 24 頁把內(nèi)存按把內(nèi)

18、存按 250 個記錄的長度分成三部分：個記錄的長度分成三部分： 兩部分為輸入緩沖區(qū)，兩部分為輸入緩沖區(qū)， 一部分為輸出緩沖區(qū)。一部分為輸出緩沖區(qū)。先對先對 A1 和和 A2 進行歸并：進行歸并：先將每段的一塊（先將每段的一塊（250個有序記錄）讀到內(nèi)存的兩個輸入緩沖區(qū)個有序記錄）讀到內(nèi)存的兩個輸入緩沖區(qū)，用歸并排序算法實施排序。邊排序，邊把結，用歸并排序算法實施排序。邊排序，邊把結果寫到輸出緩沖區(qū)。果寫到輸出緩沖區(qū)。輸出緩沖區(qū)滿時，寫入磁盤；當一個輸入緩沖輸出緩沖區(qū)滿時，寫入磁盤；當一個輸入緩沖區(qū)的內(nèi)容歸并完騰空時，將該有序段的下一塊區(qū)的內(nèi)容歸并完騰空時，將該有序段的下一塊讀入該緩沖區(qū)繼續(xù)歸并

19、。讀入該緩沖區(qū)繼續(xù)歸并。這樣繼續(xù)，直到把這樣繼續(xù)，直到把 A1 和和 A2 全歸并完畢，磁全歸并完畢，磁盤里出現(xiàn)一個含盤里出現(xiàn)一個含1500個記錄的新有序段。個記錄的新有序段。11.211.2 外部排序的方法外部排序的方法第 25 頁 完成一次歸并后，對完成一次歸并后，對A3和和A4、A5和和A6實施相實施相同歸并。整個文件經(jīng)一趟歸并，在磁盤上得同歸并。整個文件經(jīng)一趟歸并，在磁盤上得到三個各含到三個各含1500記錄的有序段。記錄的有序段。11.211.2 外部排序的方法外部排序的方法初始有序段初始有序段A11750有序段有序段A27511500有序段有序段A315012250有序段有序段A42

20、2513000有序段有序段A530013750有序段有序段A6375145003000個記錄個記錄第第2趟歸并趟歸并1500個記錄個記錄1500個記錄個記錄1500個記錄個記錄第第1趟歸并趟歸并4500個記錄個記錄第第3趟歸并趟歸并繼續(xù)進行歸并：繼續(xù)進行歸并：第第 2 趟，第趟，第 3 趟。趟。第 26 頁l分析分析在一切相同的條件下，如果把例中的在一切相同的條件下，如果把例中的 2-路歸路歸并改變成并改變成 3-路或路或 6-路（當然，這時所需要的路（當然，這時所需要的內(nèi)存緩沖區(qū)個數(shù)將會變化），那么總的讀寫磁內(nèi)存緩沖區(qū)個數(shù)將會變化），那么總的讀寫磁盤次數(shù)就會下降。盤次數(shù)就會下降。11.211

21、.2 外部排序的方法外部排序的方法歸并路數(shù)歸并路數(shù) 總讀寫磁盤次數(shù)總讀寫磁盤次數(shù) 歸并趟數(shù)歸并趟數(shù) 2 132 3 3 108 2 6 72 1第 27 頁lk-路歸并路歸并k-路歸并時，在路歸并時，在 k 個關鍵字中選最小值。通常個關鍵字中選最小值。通?？刹捎弥苯舆x擇排序方法，對關鍵字做可采用直接選擇排序方法，對關鍵字做 k-1次次比較。比較。問題：問題：在直接選擇排序時許多關鍵字間進行在直接選擇排序時許多關鍵字間進行了不止一次的重復比較，導致時間的浪費。了不止一次的重復比較，導致時間的浪費。解決辦法：解決辦法：若在選擇最小者時，將比較結果若在選擇最小者時，將比較結果保留下來，后面需要時加以

22、利用，就可減少保留下來，后面需要時加以利用，就可減少比較次數(shù)，減少磁盤輸入比較次數(shù)，減少磁盤輸入/輸出所耗費的時間，輸出所耗費的時間，從而使排序的速度提高。從而使排序的速度提高。11.211.2 外部排序的方法外部排序的方法第 28 頁l選擇樹選擇樹選擇樹是一棵二叉樹，該樹中的分支結點是選擇樹是一棵二叉樹，該樹中的分支結點是該結點兩個孩子中的較小者，根結點是這棵該結點兩個孩子中的較小者，根結點是這棵樹各葉結點中的最小者。樹各葉結點中的最小者。11.211.2 外部排序的方法外部排序的方法10920689901769681768 為選擇次小者，可把該記錄原始位置（葉結點）設為選擇次小者，可把該記

23、錄原始位置（葉結點）設成一個大于所有關鍵字的值成一個大于所有關鍵字的值“+”。進行。進行輸出輸出-調(diào)整調(diào)整。最小值最小值+由下往由下往上調(diào)整上調(diào)整2098k=8時時第 29 頁l選擇樹選擇樹為選取下一個最小者，只需對根結點到該葉為選取下一個最小者，只需對根結點到該葉結點所經(jīng)路徑上的各結點與其左或右兄弟進結點所經(jīng)路徑上的各結點與其左或右兄弟進行比較和適當?shù)恼{(diào)整即可，其他結點保持原行比較和適當?shù)恼{(diào)整即可，其他結點保持原樣。樣。11.211.2 外部排序的方法外部排序的方法10920+899017892081798+9k=8時時輸出輸出8，并調(diào)整，并調(diào)整99輸出輸出9，并調(diào)整，并調(diào)整+10109輸出

24、輸出9，并調(diào)整，并調(diào)整+1710第 30 頁l勝者樹：結點記錄勝者信息勝者樹：結點記錄勝者信息利用選擇樹的思想，對有序段進行利用選擇樹的思想，對有序段進行k-路歸并。路歸并。樹的每個葉結點對應一個樹的每個葉結點對應一個輸入緩沖區(qū)輸入緩沖區(qū)，它總，它總是各有序段在歸并過程中的是各有序段在歸并過程中的當前關鍵字當前關鍵字，分，分支結點是它的兩個孩子結點中支結點是它的兩個孩子結點中鍵值較小鍵值較小的那的那個。個。根根結點是樹中結點是樹中鍵最小鍵最小的。的。輸出根結點后，用該記錄所在有序段的下一輸出根結點后，用該記錄所在有序段的下一個關鍵字填補它的位置，并作適當調(diào)整。這個關鍵字填補它的位置，并作適當調(diào)

25、整。這樣的調(diào)整不會涉及到整棵樹，而只需考慮從樣的調(diào)整不會涉及到整棵樹，而只需考慮從根結點到該位置的路徑上的各個結點。根結點到該位置的路徑上的各個結點。11.211.2 外部排序的方法外部排序的方法第 31 頁l勝者樹勝者樹當前當前8個待歸并有序段的前個待歸并有序段的前3個關鍵字值：個關鍵字值：10, 15, 19 9, 20, 38 20, 22, 34 6, 15, 258, 17, 50 18, 21, 44 90, 95, 108 24, 32, 6611.211.2 外部排序的方法外部排序的方法1092068189024696824681234567891011121314151519

26、.2038.2234.1525.1750.2144.95108.3266.第 32 頁l勝者樹勝者樹對對 8 個并有序段進行一次歸并。先輸出根結個并有序段進行一次歸并。先輸出根結點上關鍵字為點上關鍵字為 6 的記錄，它原位于最底層編的記錄，它原位于最底層編號為號為 11 的葉結點處，用的葉結點處，用15頂替。局部調(diào)整頂替。局部調(diào)整 。11.211.2 外部排序的方法外部排序的方法1092068189024696824681234567891011121314151519.2038.2234.1525.1750.2144.95108.3266.1525.1598第 33 頁l勝者樹勝者樹輸出原位

27、于編號為輸出原位于編號為12的記錄的記錄8，并用它后面值，并用它后面值為為“17”的關鍵字進行頂替。做適當調(diào)整的關鍵字進行頂替。做適當調(diào)整.11.211.2 外部排序的方法外部排序的方法1092068189024696824681234567891011121314151519.2038.2234.1525.1750.2144.95108.3266.1525.159850.171717938.20101010輸出輸出 9，再繼續(xù)進行調(diào)整，再繼續(xù)進行調(diào)整.第 34 頁l勝者樹勝者樹：實現(xiàn)：實現(xiàn)勝者樹是勝者樹是完全二叉樹完全二叉樹，算法實現(xiàn)時，采用，算法實現(xiàn)時，采用順順序存儲結構序存儲結構保存。保

28、存。非葉結點非葉結點保存的是保存的是“勝者勝者”在樹中對應結點的在樹中對應結點的下標下標（編號編號）。）。11.211.2 外部排序的方法外部排序的方法1092068189024696824681234567891011121314151519.2038.2234.1525.1750.2144.95108.3266.9111215111211保存：勝者保存：勝者對應葉結點對應葉結點的編號的編號第 35 頁l敗者樹：結點記錄敗者信息敗者樹：結點記錄敗者信息敗者樹是一棵有敗者樹是一棵有 k 個葉結點的二叉樹，分支個葉結點的二叉樹，分支結點存放該結點兩個孩子中的結點存放該結點兩個孩子中的較大者較大者

29、（敗敗者者），而讓較小者（勝者）參加上一層的比），而讓較小者（勝者）參加上一層的比較，即勝者較，即勝者“出線出線”參加下一輪比賽。每個參加下一輪比賽。每個敗者都停在自己失敗的賽場上。敗者都停在自己失敗的賽場上。根根結點里存放結點里存放最終的失敗者最終的失敗者。11.211.2 外部排序的方法外部排序的方法第 36 頁l敗者樹：結點記錄敗者信息敗者樹：結點記錄敗者信息根結點里仍存放最終的失敗者。根結點里仍存放最終的失敗者。11.211.2 外部排序的方法外部排序的方法81020189092412345678910111213141510920681890241519.2038.2234.1525

30、.1750.2144.95108.3266.60在根的上面附加一個結點，存放全局的優(yōu)勝在根的上面附加一個結點，存放全局的優(yōu)勝者者冠軍。冠軍。第 37 頁l敗者樹：結點記錄敗者信息敗者樹：結點記錄敗者信息輸出輸出“6”，之后進行調(diào)整。，之后進行調(diào)整。11.211.2 外部排序的方法外部排序的方法81020189092412345678910111213141510920681890241519.2038.2234.1525.1750.2144.95108.3266.601525.201598第 38 頁l敗者樹敗者樹：說明：說明 勝者樹在人工處理時比較勝者樹在人工處理時比較直觀直觀，但在程序實，

31、但在程序實現(xiàn)時，特別是在現(xiàn)時，特別是在重構重構比賽樹時尋找對手，不如比賽樹時尋找對手，不如敗者樹效率高。敗者樹效率高。 由于全勝者（最小元素）所在的由于全勝者（最小元素）所在的從葉到根從葉到根的的內(nèi)結點中，都記錄著內(nèi)結點中，都記錄著被全勝者所擊敗的對手被全勝者所擊敗的對手，所以輸出最小元素并由后繼者代替之后，所以輸出最小元素并由后繼者代替之后，重構重構選擇樹時，很容易找到要比較的選擇樹時，很容易找到要比較的“對手對手”，所，所以，實現(xiàn)替代選擇合并的算法也就簡單了。以，實現(xiàn)替代選擇合并的算法也就簡單了。11.211.2 外部排序的方法外部排序的方法第 39 頁l敗者樹敗者樹：實現(xiàn)：實現(xiàn)是是完全二

32、叉樹完全二叉樹，采用，采用順序存儲順序存儲。非葉結點非葉結點保保存的是敗者在樹中對應結點的存的是敗者在樹中對應結點的下標下標（編號編號）。）。11.211.2 外部排序的方法外部排序的方法81020189092412345678910111213141510920681890241519.2038.2234.1525.1750.2144.95108.3266.6081013149151211第 40 頁l算法描述（算法描述（P298算法算法11.1）typedef int LoserTreek; /采用順序存儲結構采用順序存儲結構typedef struct KeyType key; ExNo

33、de, External k+1 ; / 外結點，存待歸并關鍵字外結點，存待歸并關鍵字void K_Merge( LoserTree &ls, External &b ) / ls0.k-1：保存非葉結點：保存非葉結點 / b0bk-1：敗者樹的：敗者樹的 k 個葉結點，個葉結點，k個歸并段的個歸并段的當前關鍵字當前關鍵字11.211.2 外部排序的方法外部排序的方法第 41 頁l算法描述（算法描述（P298算法算法11.1）void K_Merge( LoserTree &ls, External &b ) 11.211.2 外部排序的方法外部排序的方法for

34、 ( i=0; i= 0 ) if ( bs.key b ls0 .key ) s ls t ; / s：新的勝者的下標：新的勝者的下標 t = t/2; ls 0 = s; / 保存全勝者下標保存全勝者下標第 43 頁l算法描述（算法描述（P299算法算法11.3）void CreateLoserTree( LoserTree &ls ) / b 0 . k-1：為完全二叉樹：為完全二叉樹 ls 的葉結點，保存鍵值的葉結點，保存鍵值 / 沿從葉結點到根的沿從葉結點到根的 k 條路徑將條路徑將 ls 調(diào)整為敗者樹調(diào)整為敗者樹11.211.2 外部排序的方法外部排序的方法b k = MI

35、NKEY; / 設為最小值設為最小值for ( i=0; i=0; -i ) Adjust( ls, i ); / 從從bk-1 到到 b0調(diào)整敗者調(diào)整敗者第 44 頁lk路歸并是每次將路歸并是每次將k個順串合并成一個排好序個順串合并成一個排好序的順串。一般情況下，對的順串。一般情況下，對m個初始順串進行個初始順串進行k路歸并時歸并趟數(shù)為路歸并時歸并趟數(shù)為logkm。增加每次歸并的。增加每次歸并的順串數(shù)量順串數(shù)量 k 可減少歸并趟數(shù)?？蓽p少歸并趟數(shù)。l選擇樹是完全二叉樹，有兩種類型：贏者樹選擇樹是完全二叉樹，有兩種類型：贏者樹和敗者樹。和敗者樹。 11.211.2 外部排序的方法外部排序的方法第 45 頁l多路歸并多路歸并11.211.2 外部排序的方法外部排序的方法三路歸并三路歸并第 46 頁l問題問題在合并階段，如果初始的順串不等長，應該在合并階段，如果初始的順串不等長，應該如何挑選合并對象，減少讀塊次數(shù)，以加快如何挑選合并對象，減少讀塊次數(shù)，以加快合并速度？合并速度？l實例實例初始有初始有9個順串，其長度（塊數(shù)）依次為：個順串，其長度（塊數(shù)）依次為：8, 23, 9, 15, 3, 12, 2, 6, 17。采用。采用3路合并。應該路合并。應該如何進行才能使讀盤次數(shù)最少？如何進行才能使讀盤次數(shù)最少？11.2