外部排序演算法

1. 外部排序演算法基本思想是什麼

外部排序的基本思路

假設有一個72KB的文件，其中存儲了18K個整數，磁碟中物理塊的大小為4KB，將文件分成18組，每組剛好4KB。

首先通過18次內部排序，把18組數據排好序，得到初始的18個歸並段R1~R18，每個歸並段有1024個整數。

然後對這18個歸並段使用4路平衡歸並排序：

第1次歸並：產生5個歸並段

R11 R12 R13 R14 R15

其中

R11是由{R1,R2,R3,R4}中的數據合並而來

R12是由{R5,R6,R7,R8}中的數據合並而來

R13是由{R9,R10,R11,R12}中的數據合並而來

R14是由{R13,R14,R15,R16}中的數據合並而來

R15是由{R17,R18}中的數據合並而來

把這5個歸並段的數據寫入5個文件：

foo_1.dat foo_2.dat foo_3.dat foo_4.dat foo_5.dat

第2次歸並：從第1次歸並產生的5個文件中讀取數據，合並，產生2個歸並段

R21 R22

其中R21是由{R11,R12,R13,R14}中的數據合並而來

其中R22是由{R15}中的數據合並而來

把這2個歸並段寫入2個文件

bar_1.dat bar_2.dat

第3次歸並：從第2次歸並產生的2個文件中讀取數據，合並，產生1個歸並段

R31

R31是由{R21,R22}中的數據合並而來

把這個文件寫入1個文件

foo_1.dat

此即為最終排序好的文件。

二 使用敗者樹加快合並排序

外部排序最耗時間的操作時磁碟讀寫，對於有m個初始歸並段，k路平衡的歸並排序，磁碟讀寫次數為

|logkm|，可見增大k的值可以減少磁碟讀寫的次數，但增大k的值也會帶來負面效應，即進行k路合並

的時候會增加演算法復雜度，來看一個例子。

把n個整數分成k組，每組整數都已排序好，現在要把k組數據合並成1組排好序的整數，求演算法復雜度