(本章設計內容后續會具體講解)
外排序是指數據存放在外存中，數據排序時涉及內、外存數據交換的排序方法。
存儲在外存上的數據以文件為基本單位，由文件系統進行讀寫操作，讀寫操作的基本單位為物理塊
磁盤和磁帶都屬于計算機的、一、生成若干初始歸并段（順串）：這一過程也稱為文件預處理。一種常規的方法如下：
產生m=[n/w]個初始歸并段。
此時產生的若干子文件稱為順串
二、多路歸并：
（所謂多路歸并，具體使用幾路歸并是看計算機內存大小的，如計算機內存為2則只能使用2路歸并）
??對這些初始歸并段進行多遍歸并，使得有序的歸并段逐漸擴大，最后在外存上形成整個文件的單一歸并段，也就完成了這個文件的外排序。
磁盤和磁帶是什么存儲器、
??因為該數字打上了隊列編號，所以方便我們通知對應的編號隊列繼續出數字進入中轉站隊列（保證從中轉站中取出的數據是所有文件中最小的），可以看出中轉站一直保存了M個記錄，當中轉站中的所有數字都出隊完畢，則本次歸并結束。
因為每個小文件都是有序的順串，所以當內存取出所有小文件第一個數據處理后，將從輸出的那個數據所屬小文件中再次拿出一個數據，保證了內存中的數據都是各個小文件中最小的那一個
多次使用歸并算法，直到所有小文件都被處理完（以二路歸并為例）：
u個記錄需要進行u-1次操作（對各個順串中數據進行比較）（不考慮∞ （文件中數據讀取完再取的話設為∞））
k路歸并每次操作需要k-1次關鍵字比較
磁帶比磁盤更能儲存信息。總的關鍵字比較次數為：(u-1)(k-1)
影響歸并過程性能因素：
記錄讀寫次數。
內存中歸并時需要關鍵字比較次數。
外排序方法與各種外存設備的特征有關。
影響內排序的數據位置交換，在外排序中變成了記錄讀寫次數，所以此時影響外排序方法性能的主要原因為外存存取數據所花費的時間，即外排序方法與各種外存設備的特征有關
磁盤調度算法有關例題。外存設備大體上可以分為兩類
1.順序存取設備（磁帶）
2.直接存取設備（磁盤）
文件存儲在外存上，因此外排序方法與各種外存設備的特征有關
外存設備大體上可以分為兩類
磁帶是一種典型順序存取設備，通過讀寫頭讀寫數據，對于檢索和修改操作十分不便，主要用于處理很少需要修改的并且進行順序存區的信息，特別用作備份數據的設備
磁帶按用途可大致分成錄音帶、錄像帶、計算機帶和儀表磁帶四種。
快速排序用什么存儲結構，??磁盤是一種直接存取的外存設備，磁盤不僅能夠進行順序存取，而且能直接存取任何記錄，他的存取速度比磁盤快得多
??磁盤分為硬盤和軟盤兩種，硬盤的容量比軟盤大得多，而且存取速度也比軟盤快得多
硬盤結構包括：盤片、磁頭、盤片主軸、控制電機、磁頭控制器、數據轉換器、接口、緩存等幾個部份。
??整個磁盤由多個盤面組成，固定在同一軸上，沿一個固定方向高速旋轉，每個盤面包括上、下兩個盤面，每個盤面用于存儲信息，每個盤面有一個讀寫頭，所有讀寫頭都是固定在一起，同時同步移動的再一個盤面上讀寫頭的軌跡，稱為磁道，磁道就是磁面上的圓環，各個磁面上半徑相同的詞到總合成為一個柱面，每個磁道都別切分成很多扇形區域稱為扇區
磁盤的容量：磁頭數 × 磁道(柱面)數 × 每道扇區數 × 每扇區字節數。
磁頭(head)數：每個盤片一般有上下兩面，分別對應1個磁頭，共2個磁頭
早期的磁盤調度算法，磁道(track)數：磁道是從盤片外圈往內圈編號0磁道，1磁道…，靠近主軸的同心圓用于停靠磁頭，不存儲數據
柱面(cylinder)數：所有盤面上同半徑的磁道數量
扇區(sector)數：每個磁道都別切分成很多扇形區域，每道的扇區數量相同
圓盤(platter)數：就是盤片的數量
扇區（sector）:
??硬件（磁盤）上的最小的操作單位,是操作系統和塊設備（硬件、磁盤）之間傳送數據的單位。
物理塊（ block）
??block由一個或多個sector組成，是軟件（OS、文件系統）中最小的操作單位；
塊是上層軟件中（操作文件時）使用的最小的操作單元，就是（操作文件時）一個塊一個塊進行操作（塊的大小格式化時可以設置【如linux、fatfs等等】）
硬盤光盤磁帶的特點。OS的虛擬文件系統從硬件設備上讀取一個block，實際為從硬件設備讀取一個或多個sector。
物理塊是數據在磁盤上的存取單位，也就是每進行一次I/O操作，最小傳輸的數據大小。
邏輯塊
??具體文件系統管理的是一個邏輯空間，這個邏輯空間就象一個大的數組，數組的每個元素就是文件系統操作的基本單位邏輯塊
??邏輯塊是從0開始編號的，而且，邏輯塊是連續的，與物理塊相對應
??每個扇區可存儲128×2的N次方(N=0.1.2.3)字節的數據(一般為512B)，扇區為數據存儲的最小單元，外圈的扇區面積比內圈大，為何存儲的數據量相同，這是因為內外圈使用的磁物質密度不同，但現在的硬盤已經采用內外圈同密度物質來存儲數據了，以減少類似“大面積小數據”的浪費情況。
CHS模式：
??有了扇區(sector)，有了柱面(cylinder)，有了磁頭(head)，顯然可以定位數據了，這就是數據定位(尋址)方式之一，CHS(也稱3D)，對早期的磁盤(上圖所示)非常有效，知道用哪個磁頭，讀取哪個柱面上的第幾扇區就OK了。
磁盤和磁帶存取方式？??CHS模式支持的硬盤容量有限，用8bit來存儲磁頭地址，用10bit來存儲柱面地址，用6bit來存儲扇區地址，而一個扇區共有512Byte，這樣使用CHS尋址一塊硬盤最大容量為256 * 1024 * 63 * 512B = 8064 MB(1MB = 1048576B)(若按1MB=1000000B來算就是8.4GB)
LBA編址方式：
??但現在很多硬盤采用同密度盤片，意味著內外磁道上的扇區數量不同，扇區數量增加，容量增加，3D很難定位尋址
新的尋址模式：LBA(Logical Block Addressing)。在LBA地址中，地址不再表示實際硬盤的實際物理地址(柱面、磁頭和扇區)。
??LBA編址方式將CHS這種三維尋址方式轉變為一維的線性尋址，它把硬盤所有的物理扇區的C/H/S編號通過一定的規則轉變為一線性的編號，系統效率得到大大提高，避免了煩瑣的磁頭/柱面/扇區的尋址方式。
在訪問硬盤時，由硬盤控制器再將這種邏輯地址轉換為實際硬盤的物理地址。LBA下的編號，扇區編號是從0開始。
邏輯扇區號LBA的公式：
??LBA(邏輯扇區號)=磁頭數 × 每磁道扇區數 × 當前所在柱面號 + 每磁道扇區數 × 當前所在磁頭號 + 當前所在扇區號 – 1。
??磁盤是直接存取設備，讀取一個數據塊的時間與當前讀寫頭所處位置關系不大，所以可以通過讀寫數據塊的次數來衡量存取時間
磁盤scan算法、??對存放在磁盤中的文件進行排序屬于典型的外排序，稱為磁盤排序（disk sort），其磁盤排序過程與外排序所用歸并排序過程基本相同
??磁盤中的Fin文件存儲著待排序的數據，通過計算講Fin文件中的記錄一部分一部分的調入內存處理，產生若干個文件F1…Fm，他們經過處理后都是有序的，稱為順串，然后再次將F1…Fm依次調入內存，通過相關歸并算法生成Fout文件
實際上文件系統在讀取時每次讀取一個物理塊，而一個物理塊中可能有多個記錄（數據），但為了方便起見以下每個記錄占用一個物理塊（讀寫記錄只需要進行一次讀寫操作）
??按照內存大小將初始文件分為若干份（ 我們假設需要排序的int數有12個，內存一次只能裝下3個int數，就把12個數據分成4份（12/3=4），然后通過內排序處理成有序子串）
??置換－選擇排序方法生成初始歸并段，該方法可以減少生成的初始歸并段個數（初始歸并段個數越少，則越接近最后排序結果，可以減少歸并次數）
總結：
在內部排序中、共有n個記錄，內存工作區WA的容量為w：
若在w個記錄中選取最小關鍵字的采用簡單比較方法，每次需要w-1次比較。
使用敗者樹可以提高比較效率
讀出和寫入均為n
什么是k路平衡歸并:
??根據內存大小可以劃分為不同的多路歸并方案
??2路平衡歸并：每一趟從m個歸并段得到[m/2]個歸并段。
處理時把兩個小的有序子串合并成一個大的有序子串（二路歸并）
多次使用歸并算法，直到所有小文件都被處理完
排序時不穩定的有，總結:
每歸并一次，參與歸并的每個記錄都要讀一次和寫一次。
總的讀記錄數（寫記錄數與之相同）：
(F1+F2+F3+F4的記錄數)×2=24=對起始12條記錄讀（寫）了2遍=log2m
該數越大，效率越差
當m不滿足2的i次方時，增加兩個長度為0的虛段
關于拓撲排序。總的讀記錄數等同于哈夫曼樹WPL（帶權路徑長度）：
影響k路平衡歸并的因素
敗者樹
??敗者樹是一棵有k個葉子節點的完全二叉樹（可以將大根堆看成勝者樹，小根堆看成敗者樹），其中葉子節點存儲參與歸并的記錄，分支節點存放關鍵字對應的段號。
??所謂敗者是兩個記錄比較時關鍵字較大者，勝者是兩個記錄比較時關鍵字較小者
??敗者樹用于在k個記錄中選取最小關鍵字的記錄。敗者樹類似于堆排序中的小根堆。
利用敗者數實現k路平衡歸并的過程，是先建立敗者樹，然后對k個輸入有序段進行k路平衡歸并
下列說法正確的是？一、先建立敗者樹
??建立敗者數是采用類似于小根堆調整的方法實現的，初始時令所有的分支結點指向一個含最小關鍵字的葉子節點，然后從葉子結點出發，調整分支節點為新的敗者（比較時關鍵字較大者）即可
例子，k=5：
首先構造非葉子節點n2=n0-1=k-1=4
每個葉子結點對應一個歸并段，段號為0～4。
初始時每個分支結點取值“5(-∞)”，5表示段號（此時為虛擬段號，實際段號為0～4），- ∞表示最小關鍵字。
例如，某結點取值為“4(15)”，表示結點值來自4號段的關鍵字15對應的記錄。
調整產生冠軍（最小者）的過程
堆排序快速排序歸并排序的關系？??從F4=>F0重復操作：將當前結點的關鍵字與父結點比較，將大的（敗者）放在父結點中，小者（勝者）繼續進行，直到根結點。最后將勝者放在冠軍結點中。
二、用敗者樹進行歸并
取每個輸入有序段的第一個記錄，作為敗者樹的葉子節點，建立初始敗者數
兩兩葉子節點進行比較，在雙親節點中存放比較的敗者（關鍵字較大者），而讓勝者去參加更高一層的比賽，如此在根節點之上勝出的冠軍是所有關鍵字最小者
將勝出的記錄（冠軍）寫至輸出歸并段，在對應的葉子節點處補充其輸入有序段的下一個記錄，若該有序段變空，則補充一個大關鍵字（比所有關鍵字都大，設為∞）的虛記錄 ∞
調整敗者樹，選擇新的冠軍（最小的記錄）
從補充記錄的葉子節點向上和雙親結點的關鍵字比較敗者留在該雙親節點，勝者繼續向上，直到樹的根結點，最后將勝者放在根節點的雙親節點中 作為冠軍
路徑排序算法，若勝出的記錄關鍵字等于∞則歸并結束，否則重復（2）
例子，歸并過程：
??取出的冠軍為1(5)，從1號段中取下一個記錄，沿著個分支向上操作，產生次小的記錄。重復操作直到冠軍為∞
總結
利用敗者樹實現k路平衡歸并時，總共需要的關鍵字比較次數為：
關鍵字比較次數與k無關 ， 總的內部歸并時間不會隨k的增大而增大。
只要內存空間允許，盡可能增大歸并路數k。
采用敗者樹，置換-選擇排序中關鍵字比較次數分析
共有n個記錄，內存工作區WA的容量為w：若在w個記錄中選取最小關鍵字的采用敗者樹方法，每次需要log2w次比較。總的時間復雜度為O(nlog2w)。
??使用常規方法生成的初始歸并段記錄數是相同的，使用置換-選擇排序方法生成的順串可能會導致順串與順串中記錄個數不同
??k路平衡歸并適合初始歸并段中的記錄個數相同的情況，當初始歸并段中的記錄個數不同時哪些初始歸并段先歸并，哪些后歸并都會影響算法的性能
若記錄數多的先歸并記錄數少的歸并段后歸并，會導致該歸并段參與的歸并次數比記錄少的歸并段歸并次數多，而讀寫次數計算和哈夫曼樹WPL相同，從根結點到各個葉結點的路徑長度與相應結點權值的乘積的和，可知算法效率顯然不高
（假設k=3）
解決的方法是加虛段（長度為0的段），每次恰好k個段進行歸并
應加(k-1)-(m-1) Mod（%） (k-1)個虛段
??構建最佳歸并樹（m個初始歸并段）就是構建帶權路徑長度最短的k叉（階）哈夫曼樹
一、計算是否需要增加虛短
??若x=(m-1) Mod (k-1)≠0，則需附加(k-1)-x個虛段，以使每次歸并都可以對應k個段。
例子
二、按照哈夫曼樹的構造原則（權值越小的結點離根結點越遠）構造最佳歸并樹。
（1）給定的n個權值[例：W1.W2.。。]（這里的權值是歸并段中的記錄個數）構造n棵只有一個葉結點的叉樹，從而得到一個二叉樹的集合F-{T1… Ti.cum.}
（2）將二叉樹集合F排序
（3）在F中選取四個長度最小的歸并段，將作為葉子節點，其值累加和為其父節點值
（4）在森林F中再次選取3個歸并段與葉子節點的父節點累加構造出一個父節點
（5）重復4直到只剩下F一棵樹為止，這棵樹就是最佳歸并樹
總結：
在滿足k路平衡歸并的前提，平衡歸并樹 ≡ 最佳歸并樹
兩者之間的區別不過是歸并方案不同
由此選擇歸并方法時
磁帶:屬順序存取設備。
磁帶排序主要解決多個磁帶交替使用的問題。
磁帶排序也是外排序的一種，也使用多路歸并排序
??磁帶多路平衡歸并排序過程與磁盤的多路平衡歸并排序過程基本上相同。
磁帶排序和磁盤排序的主要不同之處在于磁帶排序需要充分考慮歸并段的分布狀況。
磁帶是順序存取的，所以各歸并段分布在不同磁帶和同一磁帶的不同位置對排序效率影響極大。
??多階段歸并排序 屬于多路非平衡歸并排序，即各條帶上的歸并段不再保持平衡分布。
??使用磁帶多階段歸并排序 是因為在進行磁帶多路平衡歸并排序時，重新分布有序段的問題需要使用的磁帶數量是比較多的（k路歸并時，需要使用2k個磁帶，k個磁帶做輸入帶，k個磁帶做輸出帶）
??在k路多階段歸并中僅使用k+1條磁帶，就可避免在多路平衡歸并排序法中遇到的重新分布有序段的問題。
多階段歸并排序過程：
開始時，初始歸并段不平衡地分配在前k條磁帶上（輸入帶），第k+1條磁帶作為輸出帶，開始為空。
假設有17個初始歸并段為（S1,S2,…,S17），用4臺磁帶機Tl、T2、T3和T4做三路的多階段歸并排序，其初始歸并段的分布情況及排序過程中各磁帶數據的變化情況。
每一步歸并只是部分記錄參加，歸并段最少的帶在本步歸并完成后便成為空帶，作為下一步歸并的輸出帶。
這樣，k+1條磁帶將輪流成為輸出帶，直到整個文件為一個排序文件為止。
總結
為了使歸并的趟數達到最少，必須合理地分配各磁帶上初始歸并段的段數，歸并段的總數以及在各帶上的分布情況與k階廣義Fibonacci（斐波那契）序列有對應關系。
初始歸并段在各帶上分布的段數應為：
k階Fibonacci數列可用下面的遞推公式導出：
版权声明：本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间：8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态
