外部排序

外部排序是指待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。

外部排序的时间分析

一般情况下，外部排序所需总的时间 =
内部排序（产生初始归并段）所需的时间（m×t_IS）
+外存信息读写的时间（d×t_IO）
+内部归并所需的时间（s×ut_mg）

t_IS:得到一个初始归并段进行内部排序所需时间的均值
m:经过内部排序之后得到的初始归并段的个数
t_IO:进行一次外存读/写时间的均值
d:总的读/写次数
ut_mg:对u个记录进行内部归并排序所需时间
s:为归并的趟数

多路归并排序

外部排序最常用的算法是归并排序，而多路归并排序的流程与思想也比较简单，在此不再赘言。
但值得注意的是其重要的子算法

1. 置换-选择排序
   n个记录分为m个规模较小的记录段，如果被划分的每个小记录段规模不够小，仍然无法完全读入内存，则无法用内排序得到初始归并段，因此需要一种适用于初始归并段规模的，高效的且不受内存空间限制的排序算法，即置换-选择排序。
2. 最佳归并树
   将当前的m组（每组含有k个有序记录段）记录归并为m个有序记录段的过程称为一趟归并，可见每个记录在每趟归并中需要两次I/O操作（读写操作各一次）。读写操作是非常耗时的，可见减少归并次数可以提高效率。为了使得归并次数最少，需用到最佳归并树。
3. 败者树
   归并排序算法中有一个多次出现的步骤是从当前k个值中用某种算法选出最值，可见提高选最值的效率也是整个归并排序算法效率提高的关键。这就需要用到败者树。

置换-选择排序

/**
*置换-选择排序的简单描述
*/
typedef struct{
    RcdType    rec;     //记录
    KeyType    key;    //从记录中抽取的关键字
    int    rnum;    //所属归并段的段号
}RcdNode,  WorkArea[w];    //内存工作区，容量为w

void  Replace_Selection(LoserTree  &ls,WorkArea  &wa,  FILE  *fi,  FILE  *fo){
    //  在败者树ls和内存工作区wa上用置换-选择排序求初始归并段,fi为输入文件
    //（只读文件）指针,fo为输出文件(只写文件)指针，两个文件均已打开
    Construct_Loser(ls,wa);    //初建败者树
    rc = rmax = 1;      //rc指示当前生产的初始归并段的段号
                             //rmax指示wa中关键字所属初始归并段的最大段号
    while(rc <= rmax){    //"rc = rmax+1" 标志输入文件的置换-选择排序已完成
      get_run(ls,wa);    //求得一个初始归并段
      fwrite(&RUNEND_SYMBOL,sizeof(struct RcdType),1,fo);  //将段结束标志输入输出文件
      rc = wa[ls[0]].rnum;    //设置下一段的段号
    }
}

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;}
    //输入文件结束，虚设记录(属"rmax+1"段)
    //输入文件非空时
    else{
        fread(&wa[q].rec,sizeof(RcdType),1,fi);    //从输入文件读入下一记录
        wa[q].key = wa[q].rec.key;      //提取关键字
        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个记录到内存工作区wa,建得败者树ls,选出关键字最小的记录并由s指示
    //其在wa中的位置
    for(i = 0 ; i <w; ++i){
        wa[i].rnum = wa[i].key = ls[i] = 0;    //工作区初始化
    }
    for(i = w-1;i>=0; -- i){
        fread(&wa[i].rec,sizeof(RcdType),1,fi);    //输入一个记录
        wa[i].key = wa[i].rec.key;    // 提取关键字
        wa[i].rnum = 1;    //其段号为"1"
        Select_MiniMax(ls,wa,i);    //调整败者
    }
}

扫雪机模型：若不计输入，输出时间，则对n个记录的文件而言，生产所有初始归并段所需时间为O(nlogw).

最佳归并树

归并的过程可以用一棵树来形象地描述，这棵树称为归并树，
为了优化归并树的带权路径长度，可以运用哈弗曼树。

败者树

为了突出如何利用败者树进行归并，在算法中避开了外存信息存取的细节，可以认为归并段已在内存。

typedef int LoserTree[k];  //败者树是完全二叉树且不含叶子，可采用顺序存储结构
typedef struct{
    KeyType key;
}ExNode,External[k+1];    //外结点，只存放待归并记录的关键字

void K_Merge(LoserTree &ls,External &b){
      /*利用败者树ls将编号从0到k-1的k个输入归并段中的记录归并到输出归并段。
b[0]至b[k-1]为败者树上的k个叶子结点，分别存放k个输入归并段中当前记录的关键字。
*/
    for(i = 0;i<k; ++ i) input(b[i].key);       //分别从k个输入归并段读入该段当前第一个记录的关键字到外结点
    CreateLoserTree(ls);    //建败者树ls，选得最小关键字为b[ls[0]].key
    while(b[ls[0]].key != MAXKEY){
      q = ls[0];    //q指示当前最小关键字所在归并段
      output(q);  //将编号为q的归并段中当前（关键字为b[q].key）的记录写至输出归  并段
      input(b[q].key,q);// 从编号为q的输入归并段中读取下一个记录的关键字
      Adjust(ls,q);    //调整败者树，选择性的最小关键字
    }//while    
    output(ls[0]);    //将含最大关键字MAXKEY的记录写至输出归并段
}


void CreateLoserTree(LoserTree &ls){
      //已知b[0]到b[k-1]为完全二叉树ls的叶子结点存在k个关键字
//，沿从叶子到根的k条路径将ls调整为败者树
    
    b[k].key  = MINKEY;    //设MINKEY为关键字可能的最小值
    for(i = 0;i < k;++i){
          ls[i] = k;    //设置ls中"败者"的初值
    }
    for(i = k-1; i>=0; - - i) Adjust(ls,i);   
 //依次从b[k-1],b[k-2],……,b[0]出发调整败者
   
}

while Adjust(LoserTree &ls,int s){
    //沿从叶子结点b[s]到根结点ls[0]的路径调整败者树
    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;
}

由序号构造结点的好处是,不仅可以找到记录值，还可以找到其所在的归并段，以便于下一个记录读入内存取代刚选出的最值。

为什么得用败者树，而不是用堆？：

时间空间复杂度分析

外部排序的时间复杂度涉及很多方面，且分析较为复杂，一般考试不会让考试分析整个流程中与时间复杂度相关的每一个细节，因此只需要注意以下几点即可：

1. m个初始归并段进行k路归并，归并的趟数为[log_km]
2. 每一次归并，所有记录都要进行两次I/O操作。
3. 置换-选择排序这一步中，所有记录都要进行两次I/O操作
4. 置换-选择排序中，选最值那一步的时间复杂度要根据考试要求的选择算法而定
5. k路归并的败者树的高度为[log₂k]+1，因此利用败者树从k个记录中选出最值需要进行[log₂k]此比较，即时间复杂度O(log₂k)
6. k路归并的败者树的建树时间复杂度为O(klog₂k)
   注意k路归并败者树，不是k叉败者树，而是一颗二叉树

空间复杂度
显然所有步骤中的空间复杂度都是常量，因此是O(1)