外部排序是指待排序記錄的數(shù)量很大，以致內(nèi)存一次不能容納全部記錄，在排序過程中尚需對外存進行訪問的排序過程。

外部排序的時間分析

一般情況下，外部排序所需總的時間 =
內(nèi)部排序（產(chǎn)生初始歸并段）所需的時間（m×t_IS）
+外存信息讀寫的時間（d×t_IO）
+內(nèi)部歸并所需的時間（s×ut_mg）

t_IS:得到一個初始歸并段進行內(nèi)部排序所需時間的均值
m:經(jīng)過內(nèi)部排序之后得到的初始歸并段的個數(shù)
t_IO:進行一次外存讀/寫時間的均值
d:總的讀/寫次數(shù)
ut_mg:對u個記錄進行內(nèi)部歸并排序所需時間
s:為歸并的趟數(shù)

多路歸并排序

外部排序最常用的算法是歸并排序，而多路歸并排序的流程與思想也比較簡單，在此不再贅言。
但值得注意的是其重要的子算法

1. 置換-選擇排序
   n個記錄分為m個規(guī)模較小的記錄段，如果被劃分的每個小記錄段規(guī)模不夠小，仍然無法完全讀入內(nèi)存，則無法用內(nèi)排序得到初始歸并段，因此需要一種適用于初始歸并段規(guī)模的，高效的且不受內(nèi)存空間限制的排序算法，即置換-選擇排序。
2. 最佳歸并樹
   將當前的m組（每組含有k個有序記錄段）記錄歸并為m個有序記錄段的過程稱為一趟歸并，可見每個記錄在每趟歸并中需要兩次I/O操作（讀寫操作各一次）。讀寫操作是非常耗時的，可見減少歸并次數(shù)可以提高效率。為了使得歸并次數(shù)最少，需用到最佳歸并樹。
3. 敗者樹
   歸并排序算法中有一個多次出現(xiàn)的步驟是從當前k個值中用某種算法選出最值，可見提高選最值的效率也是整個歸并排序算法效率提高的關(guān)鍵。這就需要用到敗者樹。

置換-選擇排序

/**
*置換-選擇排序的簡單描述
*/
typedef struct{
    RcdType    rec;     //記錄
    KeyType    key;    //從記錄中抽取的關(guān)鍵字
    int    rnum;    //所屬歸并段的段號
}RcdNode,  WorkArea[w];    //內(nèi)存工作區(qū)，容量為w

void  Replace_Selection(LoserTree  &ls,WorkArea  &wa,  FILE  *fi,  FILE  *fo){
    //  在敗者樹ls和內(nèi)存工作區(qū)wa上用置換-選擇排序求初始歸并段,fi為輸入文件
    //（只讀文件）指針,fo為輸出文件(只寫文件)指針，兩個文件均已打開
    Construct_Loser(ls,wa);    //初建敗者樹
    rc = rmax = 1;      //rc指示當前生產(chǎn)的初始歸并段的段號
                             //rmax指示wa中關(guān)鍵字所屬初始歸并段的最大段號
    while(rc <= rmax){    //"rc = rmax+1" 標志輸入文件的置換-選擇排序已完成
      get_run(ls,wa);    //求得一個初始歸并段
      fwrite(&RUNEND_SYMBOL,sizeof(struct RcdType),1,fo);  //將段結(jié)束標志輸入輸出文件
      rc = wa[ls[0]].rnum;    //設(shè)置下一段的段號
    }
}

void get_run (LoserTree &ls,WorkArea &wa){
    //求得一個初始歸并段，fi為輸入文件指針，fo為輸出文件指針
    while(wa[ls[0]].rnum == rc){    //選得的MINIMAX記錄屬當前段時
        q = ls[0];    //q知識MINIMAX記錄在wa中的位置
        minimax = wa[q].key;
    }
    fwrite(&wa[q].rec,sizeof(RcdType),1,fo);    //將剛選好的MINIMAX記錄寫入輸出文件
    if(feof(fi))    {wa[q].rnum = rmax +1; wa[q].key = MAXKEY;}
    //輸入文件結(jié)束，虛設(shè)記錄(屬"rmax+1"段)
    //輸入文件非空時
    else{
        fread(&wa[q].rec,sizeof(RcdType),1,fi);    //從輸入文件讀入下一記錄
        wa[q].key = wa[q].rec.key;      //提取關(guān)鍵字
        if(wa[q].key <minimax){     //新讀入的記錄屬下一段
            rmax = rc +1;
            wa[q].rnum = rmax;
        }
        else
            wa[q].rnum = rc;    //新讀入的記錄屬當前段
        }
          Select_MiniMax(ls,wa,q);    選擇新的MINIMAX記錄
    }
    
void Select_MiniMax(LoserTree &ls,WorkArea wa,int q){
        //從wa[q]起到敗者樹的根比較選擇MINIMAX記錄，并由q指示它所在的歸并段
        for(t = (w+q)/2,p = ls[t];t>0; t= t/2,p = ls[t]){
            if(wa[p].rnum <wa[q].rnum || wa[p].rnum == wa[q].rnum && wa[p].key <wa[q].key){
                q <-->ls[t]; //q指示新的勝利者
            }
        }
        ls[0] = q;
    }
}

void Construct_Loser(LoserTree &ls,WorkArea &wa){
    //輸入w個記錄到內(nèi)存工作區(qū)wa,建得敗者樹ls,選出關(guān)鍵字最小的記錄并由s指示
    //其在wa中的位置
    for(i = 0 ; i <w; ++i){
        wa[i].rnum = wa[i].key = ls[i] = 0;    //工作區(qū)初始化
    }
    for(i = w-1;i>=0; -- i){
        fread(&wa[i].rec,sizeof(RcdType),1,fi);    //輸入一個記錄
        wa[i].key = wa[i].rec.key;    // 提取關(guān)鍵字
        wa[i].rnum = 1;    //其段號為"1"
        Select_MiniMax(ls,wa,i);    //調(diào)整敗者
    }
}

掃雪機模型：若不計輸入，輸出時間，則對n個記錄的文件而言，生產(chǎn)所有初始歸并段所需時間為O(nlogw).

最佳歸并樹

歸并的過程可以用一棵樹來形象地描述，這棵樹稱為歸并樹，
為了優(yōu)化歸并樹的帶權(quán)路徑長度，可以運用哈弗曼樹。

敗者樹

為了突出如何利用敗者樹進行歸并，在算法中避開了外存信息存取的細節(jié)，可以認為歸并段已在內(nèi)存。

typedef int LoserTree[k];  //敗者樹是完全二叉樹且不含葉子，可采用順序存儲結(jié)構(gòu)
typedef struct{
    KeyType key;
}ExNode,External[k+1];    //外結(jié)點，只存放待歸并記錄的關(guān)鍵字

void K_Merge(LoserTree &ls,External &b){
      /*利用敗者樹ls將編號從0到k-1的k個輸入歸并段中的記錄歸并到輸出歸并段。
b[0]至b[k-1]為敗者樹上的k個葉子結(jié)點，分別存放k個輸入歸并段中當前記錄的關(guān)鍵字。
*/
    for(i = 0;i<k; ++ i) input(b[i].key);       //分別從k個輸入歸并段讀入該段當前第一個記錄的關(guān)鍵字到外結(jié)點
    CreateLoserTree(ls);    //建敗者樹ls，選得最小關(guān)鍵字為b[ls[0]].key
    while(b[ls[0]].key != MAXKEY){
      q = ls[0];    //q指示當前最小關(guān)鍵字所在歸并段
      output(q);  //將編號為q的歸并段中當前（關(guān)鍵字為b[q].key）的記錄寫至輸出歸  并段
      input(b[q].key,q);// 從編號為q的輸入歸并段中讀取下一個記錄的關(guān)鍵字
      Adjust(ls,q);    //調(diào)整敗者樹，選擇性的最小關(guān)鍵字
    }//while    
    output(ls[0]);    //將含最大關(guān)鍵字MAXKEY的記錄寫至輸出歸并段
}


void CreateLoserTree(LoserTree &ls){
      //已知b[0]到b[k-1]為完全二叉樹ls的葉子結(jié)點存在k個關(guān)鍵字
//，沿從葉子到根的k條路徑將ls調(diào)整為敗者樹
    
    b[k].key  = MINKEY;    //設(shè)MINKEY為關(guān)鍵字可能的最小值
    for(i = 0;i < k;++i){
          ls[i] = k;    //設(shè)置ls中"敗者"的初值
    }
    for(i = k-1; i>=0; - - i) Adjust(ls,i);   
 //依次從b[k-1],b[k-2],……,b[0]出發(fā)調(diào)整敗者
   
}

while Adjust(LoserTree &ls,int s){
    //沿從葉子結(jié)點b[s]到根結(jié)點ls[0]的路徑調(diào)整敗者樹
    t = (s+k)/2;
    while(t >0){
      if(b[s].key > b[ls[t]].key)  s<-->ls[t];    //s指示新的勝者
      t=t/2;
    }
    ls[0] = s;
}

由序號構(gòu)造結(jié)點的好處是,不僅可以找到記錄值，還可以找到其所在的歸并段，以便于下一個記錄讀入內(nèi)存取代剛選出的最值。

為什么得用敗者樹，而不是用堆？：

時間空間復(fù)雜度分析

外部排序的時間復(fù)雜度涉及很多方面，且分析較為復(fù)雜，一般考試不會讓考試分析整個流程中與時間復(fù)雜度相關(guān)的每一個細節(jié)，因此只需要注意以下幾點即可：

1. m個初始歸并段進行k路歸并，歸并的趟數(shù)為[log_km]
2. 每一次歸并，所有記錄都要進行兩次I/O操作。
3. 置換-選擇排序這一步中，所有記錄都要進行兩次I/O操作
4. 置換-選擇排序中，選最值那一步的時間復(fù)雜度要根據(jù)考試要求的選擇算法而定
5. k路歸并的敗者樹的高度為[log₂k]+1，因此利用敗者樹從k個記錄中選出最值需要進行[log₂k]此比較，即時間復(fù)雜度O(log₂k)
6. k路歸并的敗者樹的建樹時間復(fù)雜度為O(klog₂k)
   注意k路歸并敗者樹，不是k叉敗者樹，而是一顆二叉樹

空間復(fù)雜度
顯然所有步驟中的空間復(fù)雜度都是常量，因此是O(1)