王道-数据结构-ch8-排序

王道

排序

p306

【考纲内容】

(一）排序的基本概念

(二）插入排序
直接插入排序;折半插入排序;希尔排序（shell sort)

(三）交换排序
冒泡排序（ bubble sort);快速排序

(四）选择排序
简单选择排序;堆排序

(五)2路归并排序（merge sort)

(六）基数排序

(七）外部排序

(八）各种排序算法的比较

(九）排序算法的应用

【知识框架】

• 基本概念
  • 稳定性
  • 衡量标准:时、空复杂度
• 内部排序
  • 插入排序
    • 直接插入排序
    • 折半插入排序
    • 希尔排序
  • 交换排序
    • 冒泡排序
    • 快速排序
  • 选择排序
    • 简单选择排序
    • 堆排序
  • 归并排序
  • 基数排序
• 外部排序——多路归并排序

【复习提示】

堆排序、快速排序和归并排序是本章的重难点。读者应深入掌握各种排序算法的思想、排序过程（能动手模拟）和特征（初态的影响、复杂度、稳足性、道用性等)，避吊以远开越的1八考查不同算法之间的对比。此外，对于一些常用排序算法的天键代码，要达到热练绸与的住度;看到某特定序列，读者应具有选择最优排序算法（根据排序算法特征）的能力。

单词	含义
LSD,Least Significant Digit first	最低位优先
MSD,Most Significant Digit first	最高位优先

$\color{red}{\text{Q}}$：总结每种排序算法的特点

排序的基本概念

排序的定义

排序，就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。为了查找方便，通常希望计算机中的表是按关键字有序的。排序的确切定义如下:

输入:$n$个记录$R_1, R_2, R_n，$对应的关键字为$k_1, k_2,\cdots, k_n$。

输出:输入序列的一个重排$R_1’，R_2’,\cdots,R_n’$，使得$k_1’ \leq k_2’ \leq \cdots \leq k_n’$(其中“$\leq$”可以换成其他的比较大小的符号)。

算法的稳定性。若待排序表中有两个元素$R_i$和$R_j$，其对应的关键字相同即$key_i= key_j$，且在排序前$R_i$,在$R_j$的前面，若使用某一排序算法排序后，$R_i$仍然在$R_j$的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。需要注意的是，算法是否具有稳定性并不能衡量一个算法的优劣，它主要是对算法的性质进行描述。如果待排序表中的关键字不允许重复，则排序结果是唯一的，那么选择排序算法时的稳定与否就无关紧要。

注意:对于不稳定的排序算法，只需举出一组关键字的实例，说明它的不稳定性即可。

在排序过程中，根据数据元素是否完全在内存中，可将排序算法分为两类:①内部排序，是指在排序期间元素全部存放在内存中的排序;②外部排序，是指在排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动的排序。

一般情况下，内部排序算法在执行过程中都要进行两种操作:比较和移动。通过比较两个关键字的大小，确定对应元素的前后关系，然后通过移动元素以达到有序。当然，并非所有的内部排序算法都要基于比较操作，事实上，基数排序就不基于比较。

每种排序算法都有各自的优缺点，适合在不同的环境下使用，就其全面性能而言，很难提出一种被认为是最好的算法。通常可以将排序算法分为插入排序、交换排序、选择排序、归并排序和基数排序五大类，后面几节会分别进行详细介绍。内部排序算法的性能取决于算法的时间复杂度和空间复杂度，而时间复杂度一般是由比较和移动的次数决定的。

插入排序

插入排序是一种简单直观的排序方法，其基本思想是每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列，直到全部记录插入完成。由插入排序的思想可以引申出三个重要的排序算法:直接插入排序、折半插入排序和希尔排序。

直接插入排序

根据上面的插入排序思想，不难得出一种最简单也最直观的直接插入排序算法。假设在排序过程中，待排序表$L \lbrack 1\cdots n \rbrack$在某次排序过程中的某一时刻状态如下:

要将元素L(i)插入己有序的子序列$L\lbrack 1\cdots i-1 \rbrack$，需要执行以下操作（为避免混淆，下面用$L\lbrack \rbrack$表示一个表，而用L()表示一个元素):

1)查找出L(i)在$L \lbrack 1\cdots i-1 \rbrack$中的插入位置k。

2）将$L \lbrack k\cdots i-1 \rbrack$中的所有元素依次后移一个位置。

3）将L(i)复制到L(k)。

为了实现对$L\lbrack 1\cdots n \rbrack$的排序,可以将L(2)~L(n)依次插入前面已排好序的子序列,初始$L\lbrack 1 \rbrack$可以视为是一个已排好序的子序列。上述操作执行n -1次就能得到一个有序的表。插入排序在实现上通常采用就地排序（空间复杂度为O(1))，因而在从后向前的比较过程中，需要反复把已排序元素逐步向后挪位，为新元素提供插入空间。

下面是直接插入排序的代码，其中再次用到了我们前面提到的“哨兵”(作用相同)。

王道书中关于直接插入排序的代码

 // 王道辅导书的代码
void InsertSort(ElemType A[], int n){
  int i,j;
  for(i=2;i<n;i++)//依次将A[2]～A[n]插入前面已排序序列
  if(A[i]<A[i-1])(  //若A[i]关键码小于其前驱,将A[i]插入有序表
    A[0] = A[i];//复制为哨兵，A[0]不存放元素
    for(j=i-1;A[0]<A[j];--j)//从后往前查找待插入位置 
      A[j+1]=A[j];//向后挪位
    A[j+1]=A[0];//复制到插入位置
}

严书中关于直接插入排序的代码

void InsertSort(SqList &L){
  // 对顺序表L作直接插入排序
  for(i=2; i <= L.length; ++i)
    if(LT(L.r[i].key, L.r[i-1].key)){  // "<",需将L.r[i]插入有序子表
      L.r[0] = L.r[i];  // 复制为哨兵
      L.r[i] = L.r[i-1];
      for(j=i-2; LT(L.r[0].key, L.r[j].key); --j)
        L.r[j+1] = L.r[j];  // 记录后移
      L.r[j+1] = L.r[0]; // 插入到正确的位置
    }
} // InsertSort

哨兵：有和没有都是常熟个辅助单元啊
这个算法非常的魔怔
更魔怔的是，王道，严，天勤上写的都不一样，版本乱天飞,严的代码也很魔怔，if(LT(L.r[i].key, L.r[i-1].key)){ // "<",需将L.r[i]插入有序子表为什么要省花括号呢？？第7行写成j=i-1就没有第6行的事了，真的绝了；
再次更新，第六行还是有作用的，第六行可以减少一次比较！

直接插入排序算法的性能分析如下:

空间效率:仅使用了常数个辅助单元，因而空间复杂度为O(1)。

时间效率:在排序过程中，向有序子表中逐个地插入元素的操作进行了n-1趟,每趟都分为比较关键字和移动元素，而比较次数和移动次数取决于待排序表的初始状态。

在最好情况下，表中元素已经有序，此时每插入一个元素，都只需比较一次而不用移动元素，因而时间复杂度为O(n)。

在最坏情况下，表中元素顺序刚好与排序结果中的元素顺序相反（逆序)，总的比较次数达到最大，为$\displaystyle \sum{i=2}^n i$，总的移动次数也达到最大，为$\displaystyle \sum{i=2}^n (i+1)$

$\color{red}{\text{Q}}$：为什么最坏的情况，比较次数不是1次？

平均情况下，考虑待排序表中元素是随机的，此时可以取上述最好与最坏情况的平均值作为平均情况下的时间复杂度，总的比较次数与总的移动次数均约为$n^2/4$。

因此，直接插入排序算法的时间复杂度为O($n^2$)。

稳定性:由于每次插入元素时总是从后向前先比较再移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。

适用性:直接插入排序算法适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。

注意:大部分排序算法都仅适用于顺序存储的线性表。

折半插入排序

从直接插入排序算法中，不难看出每趟插入的过程中都进行了两项工作: ${\textstyle\unicode{x2460}}$ 从前面的有序子表中查找出待插入元素应该被插入的位置; ${\textstyle\unicode{x2461}}$ 给抽入位置腾出空间，将待插入元素复制到表中的插入位置。注意到在该算法中，总是边比较边移动元素。下面将比较和移动操作分离，即先折半查找出元素的待插入位置，然后统一地移动待插入位置之后的所有元素。当排序表为顺序表时，可以对直接插入排序算法做如下改进:由于是顺序存储的线性表，所以查找有序子表时可以用折半查找来实现。确定待插入位置后，就可统一地向后移动元素。算法代码如下:

void InsertSort (ElemType A[] ,int n){
  int i,j,low, high, mid;
  for (i=2;i<=n;i++){ //依次将A[2]～A[n]插入前面的已排序序列
  A[0]=A[i];//将A[i]暂存到A[0]
  low=1;high=i-1;//设置折半查找的范围
  while(low<=high){//折半查找(默认递增有序)
    mid=(low+high) /2;//取中间点
  if(A[mid] >A[0]) high-mid-1;//查找左半子表
    else low=mid+1;//查找右半子表
  }
  for(j-i-1;j>=high+1;--j)
    A[j+1]=A[j];//统一后移元素,空出插入位置
  A[high+1]=A[0]; //插入操作
}

严书关于折半插入排序的代码

从上述算法中，不难看出折半插入排序仅减少了比较元素的次数，约为$O(nlog_2n)$，该比较次数与待排序表的初始状态无关，仅取决于表中的元素个数$n$;而元素的移动次数并未改变，它依赖于待排序表的初始状态。因此，折半插入排序的时间复杂度仍为$O(n^2)$，但对于数据量不很大的排序表，折半插入排序往往能表现出很好的性能。折半插入排序是一种稳定的排序方法。

希尔排序

从前面的分析可知，直接插入排序算法的时间复杂度为$O(n^2)$，但若待排序列为“正序”时，其时间复杂度可提高至$O(n)$，由此可见它更适用于基本有序的排序表和数据量不大的排序表。希尔排序正是基于这两点分析对直接插入排序进行改进而得来的，又称缩小增量排序。

所谓增量就是增加的量，所以算的时候,比如$\color{green}{\text{1}}$,2,$\color{green}{\text{3}}$，1，3被分到了一组，那么增量就是2，下划线的长度为2

希尔排序的基本思想是:先将待排序表分割成若干形如$L\lbrack i, i + d, i+ 2d,\cdots, i + kd \rbrack$的“特殊”子表，即把相隔某个“增量”的记录组成一个子表，对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。

希尔排序的过程如下:先取一个小于$n$的步长$d_1$，把表中的全部记录分成$d_1$ 组，所有距离为$d_1$的倍数的记录放在同一组，在各组内进行直接插入排序;然后取第二个步长$d_2 < d_1$过程，直到所取到的$d_t = 1$，即所有记录已放在同一组中，再进行直接插入排序，由于此已经具有较好的局部有序性，故可以很快得到最终结果。到目前为止，尚未求得一个最好的增量序列,

希尔提出的方法是$d1=n/2，d{i+1} = \lfloor d_i /2 \rfloor$，并且最后一个增量等于1。仍以8.2.1节的关键字为例，

第一趟取增量$d_1 = 5$，将该序列分成5个子序列，即图中第2行至第6行，分别对各子序列进行直接插入排序，结果如第7行所示;第二趟取增量$d_2=3$，分别对3个子序列进行直接插入排序，结果如第11行所示;最后对整个序列进行一趟直接插入排序，整个排序过程如图8.2所示。

希尔排序算法的代码如下:

void ShellSort(El emType A[I],int n){
//A[0]只是暂存单元，不是哨兵,当j<=0时，插入位置已到
for (dk=n /2;dk>=1;dk=dk /2)//步长变化
  for(i-dk+1;i<-n;++i)
  if(A[i]<A[i-dk]){//需将A[i]插入有序增量子表
    A [O]=A[i];//暂存在A[0]
    for(j-i-dk;j>0&&A[O]<A[j];j--dk)
      A[j+dk]=A[j]; //记录后移,查找插入的位置
    A[j+dk]=A[0];//插入
  }//if
}

严书希尔排序的过程

图片详情

$\color{red}{\text{Q}}$:暂存元素和哨兵的区别

希尔排序算法的性能分析如下:

空间效率:仅使用了常数个辅助单元，因而空间复杂度为O(1)。

时间效率:由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题,所以其时间复杂度分析比较困难。当n在某个特定范围时,希尔排序的时间复杂度约为$O(n^{1.3}$。在最坏情况下希尔排序的时间复杂度为$O(n^2)$。

跟增量的选取有关，某个特定的增量的时间复杂度为$O(n^{3/2})$

稳定性:当相同关键字的记录被划分到不同的子表时，可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。例如，图8.2中49与$\bar{49}$的相对次序已发生了变化

适用性:希尔排序算法仅适用于线性表为$\color{red}{\text{顺序存储}}$的情况。

交换排序

所谓交换，是指根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。基于交换的排序算法很多，本书主要介绍冒泡排序和快速排序，其中冒泡排序算法比较简单，一般不会单独考查，通常会重点考查快速排序算法的相关内容。

冒泡排序

严书冒泡排序的描述

冒泡排序的基本思想是:从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即$A[i-1]>A[i]$)，则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序列的最后一个位置)，关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”(或关键字最大的元素如石头一般下沉至水底)。下一趟冒泡时，前一趟确定的最小元素不再参与比较,每趟冒泡的结果是把序列中的最小元素(或最大元素）放到了序列的最终位置……这样最多做$n-1$趟冒泡就能把所有元素排好序。

图8.3所示为冒泡排序的过程，第一趟冒泡时:27<$\bar{49}$，不交换;13<27，不交换;76>13，交换;97>13，交换;65>13，交换;38>13，交换;49>13，交换。通过第一趟冒泡后，最小元素已交换到第一个位置，也是它的最终位置。第二趟冒泡时对剩余子序列采用同样方法进行排序，以此类推，到第五趟结束后没有发生交换，说明表已有序，冒泡排序结束。

冒泡排序算法的代码如下:

void Bubblesort (ElemType A[], int n){
  for(i-0;i<n-1;i++){
    flag=false;//表示本趟冒泡是否发生交换的标志
    for(j=n-1;j>i;j--)//一趟冒泡过程
    if(A[j-1]>A[j]){//若为逆序
      swap(A[j-1],A[j]);//交换
      flag=true;
    }
    if(flag==false)
    return;
    //本趟遍历后没有发生交换，说明表已经有序
  } 
}

冒泡排序的性能分析如下:

空间效率:仅使用了常数个辅助单元，因而空间复杂度为O(1)。

时间效率:当初始序列有序时，显然第一趟冒泡后flag依然为false(本趟冒泡没有元素交换)，从而直接跳出循环，比较次数为n-1，移动次数为0，从而最好情况下的时间复杂度为$O(n)$;当初始序列为逆序时，需要进行n-1趟排序，第i趟排序要进行n-i次关键字的比较，而且每次比较后都必须移动元素三次来交换元素位置，这种情况下，

比较次数=$\displaystyle \sum{i=1}^{n-1}=\dfrac{n(n-1)}{2}$,移动次数=$\displaystyle \sum{i=1}^{n-1}3(n-i)=\dfrac{3n(n-1)}{2}$

从而，最坏情况下的时间复杂度为$O(n^2)$,其平均时间复杂度也为$O(n^2)$

稳定性:由于i>j且$A\lbrack i \rbrack = A\lbrack j \rbrack$时，不会发生交换，因此冒泡排序是一种稳定的排序方法。

注意:冒泡排序中所产生的有序子序列一定是全局有序的.(不同于直接插入排序)，也就是说，有序子序列中的所有元素的关键字一定小于或大于无序子序列中所有元素的关键字，这样每趟排序都会将一个元素放置到其最终的位置上。
为什么要强调这个

快速排序

严书快速排序的代码pp.286

严书快速排序的代码pp.287

快速排序之所以叫快速排序就是因为他是最快的算法（笑

快速排序的基本思想是基于分治法的:在待排序表$L \lbrack 1\cdots n \rbrack$中任取一个元素 pivot 作为枢轴（或基准，通常取首元素)，通过一趟排序将待排序表划分为独立的两部分 L[ 1…k-1]和[ k+1…n]，使得L[ 1…k-1]中的所有元素小于 pivot，L[ k+1..n ]中的所有元素大于等于pivot，则 pivot放在了其最终位置L(k)上，这个过程称为一趟快速排序（或一次划分)。然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。

一趟快速排序的过程是一个交替搜索和交换的过程，下面通过实例来介绍，附设两个指针i和j，初值分别为low和 high，取第一个元素49为枢轴赋值到变量pivot。

对算法的最好理解方式是手动地模拟一遍这些算法。

假设划分算法已知，记为Partition ( )，返回的是上述的k，注意到工(k)已在最终的位置，因此可以先对表进行划分，而后对两个表调用同样的排序操作。因此可以递归地调用快速排序算法进行排序，具体的程序结构如下:

void QuickSort (ElemType A[],int low,int high) l
  if (low<high){//递归跳出的条件
  //Partition()就是划分操作，将表A[low…high]划分为满足上述条件的两个子表
    int pivotpos-Partition (A,low, high);//划分
    QuickSort (A, low, pivotpos-1);//依次对两个子表进行递归排序
    Quicksort (A, pivotpos+1, high);
  }

从上面的代码不难看出快速排序算法的关键在于划分操作，同时快速排序算法的性能也主要取决于划分操作的好坏。从快速排序算法提出至今，巴有叶多个P的刘万你1I以队半丰中第一个查的快速排序的划分操作基本以严蔚敏的教材《数据结构》为土。假仅母队芯以表衣动元素作为枢轴来对表进行划分，则将表中比枢轴大的元素向右移动,将比枢轴小的元素向左移动,使得一趟Partition ()操作后，表中的元素被枢轴值一分为二。代码如下:

int Partition (ElemType A[], int low,int high)(//一趟划分
ElemType pivot=A[low];//将当前表中第一个元素设为枢轴,对表进行划分
  while(low<high){
    //循环跳出条件
    while( low<high& &A [high] >=pivot) --high;
    A[low]=A [high];//将比枢轴小的元素移动到左端
    while(low<high && A[low]<=pivot) ++low;
    A[high] =A[low];//将比枢轴大的元素移动到右端
  }
  A[low]=pivot;//枢轴元素存放到最终位置
  return 1ow;//返回存放枢轴的最终位置
}

快速排序算法的性能分析如下:

空间效率:由于快速排序是递归的，需要借助一个递归工作栈来保存每层递归调用的必要信息，其容量应与递归调用的最大深度一致。$\color{green}{\text{最好情况}}$下为$O(log_2n)$;$\color{green}{\text{最坏情况}}$下，因为要进行$n—1$次递归调用，所以栈的深度为O(n);平均情况下，栈的深度为$O(log_2n)$。

时间效率:快速排序的运行时间与划分是否对称有关，快速排序的最坏情况发生在两个区域分别包含$n-1$个元素和0个元素时，这种最大限度的不对称性若发生在每层递归上，即对应于初始排序表基本有序或基本逆序时，就得到最坏情况下的时间复杂度为$O(n^2)$。

Q：为什么有序不是$O(0)$,不会发生交换啊，虽然这时候比较的次数是$O(n^2)$:第一个工作栈第一个while执行了n次，第二个while不执行，第一个工作栈第一个while执行了n-1次，第二个while不执行….
A：每次递归栈都是n次比较，但是枢纽越中心，递归栈越短，总的比较次数越小
参考文献

有很多方法可以提高算法的效率:-一种方法是尽量选取一个可以将数据中分的枢轴元素，如从序列的头尾及中间选取三个元素，再取这三个元素的中间值作为最终的枢轴元素;或者随机地从当前表中选取枢轴元素，这样做可使得最坏情况在实际排序中几乎不会发生。

在最理想的状态下，即 Partition ()可能做到最平衡的划分，得到的两个子问题的大小都不可能大于n/2,在这种情况下，快速排序的运行速度将大大提升，此时，时间复杂度为$O(nlog_2n)$。好在快速排序平均情况下的运行时间与其最佳情况下的运行时间很接近，而不是接近其最坏情况下的运行时间。快速排序是所有内部排序算法中平均性能最优的排序算法。

快排最优

稳定性:在划分算法中，若右端区间有两个关键字相同，且均小于基准值的记录则在交到左端区间后，它们的相对位置会发生变化，即快速排序是一种不稳定的排序方法。{3,2,2}，经过一趟排序后L={2,2,3}，最终排序序列也是L={2,2,3}，显然，2与2的相对次序已发生了变化。

注意:在快速排序算法中，并不产生有序子序列，但每趟排序后会将枢轴（基准)元素放到其最终的位置上。

选择排序

p313

选择排序的基本思想是:每一趟（如第i趟）在后$n-i+1(i=1, 2,\cdots,n-1)$个待排序元素中选取关键字最小的元素，作为有序子序列的第$i$个元素，直到第$n-1$趟做完，待排序元素只剩下1个，就不用再选了。选择排序中的堆排序算法是历年考查的重点。

简单选择排序

严书中关于简单选择排序的描述

根据上面选择排序的思想，可以很直观地得出简单选择排序算法的思想:假设排序表为L[ 1…n]，第i趟排序即从L[ i…n ]中选择关键字最小的元素与L(i)交换，每一趟排序可以确定一个元素的最终位置，这样经过n-1趟排序就可使得整个排序表有序。

简单选择排序算法的代码如下:

void SelectSort (ElemType A[] ,int n){
  for(i=0;i<n-1;i++){//一共进行n-1趟
    min=i;//记录最小元素位置
    for(j-i+1;j<n;j++)//在A[i...n-1]中选择最小的元素
      if(A[j]<A[min])min=j;//更新最小元素位置
    if(min!=i) swap (A[i],A[min]);//封装的swap()函数共移动元素3次
  }
}

简单选择排序算法的性能分析如下:

空间效率:仅使用常数个辅助单元，故空间效率为O(1)。

时间效率:从上述伪码中不难看出，在简单选择排序过程中，元素移动的操作次数很少，不会超过3(n-1)次，最好的情况是移动О次，此时对应的表已经有序;但元素间比较的次数与序列的初始状态无关，始终是n(n- 1)/2 次，因此时间复杂度始终是$O(n^2)$。

稳定性:在第i趟找到最小元素后，和第i个元素交换，可能会导致第i个元素与其含有相同关键字元素的相对位置发生改变。例如，表L= {$\color{green}{\text{2}}$,$\color{red}{\text{2}}$,1}，经过一趟排序后L= {1,$\color{red}{\text{2}}$,$\color{green}{\text{2}}$}，最终排序序列也是L= {1,$\color{red}{\text{2}}$,$\color{green}{\text{2}}$}，显然，$\color{red}{\text{2}}$与$\color{green}{\text{2}}$的相对次序已发生变化。因此，简单选择排序是一种不稳定的排序方法。

堆排序

Q：堆和平衡二叉树的区别
A：堆只保证父子(两层)之间的大小关系，而平衡二叉树需要保证所有层间的大小关系，而且大顶堆一定不是平衡二叉树

堆的定义如下，n个关键字序列L[ 1…n]称为堆，当且仅当该序列满足:

${\textstyle\unicode{x2460}}$ L(i) >=L(2i)且L(i) >=L (2i+1)或

${\textstyle\unicode{x2461}}$ L(i)<=L(2i)且L(i)<=L(2i+1)（$1\leq i \leq \lfloor n/2 \rfloor$)

可以将该一维数组视为一棵完全二叉树，满足条件①的堆称为大根堆（大顶堆)，大根堆的最大元素存放在根结点，且其任一非根结点的值小于等于其双亲结点值。满足条件②的堆称为小根堆（小顶堆)，小根堆的定义刚好相反，根结点是最小元素。图8.4所示为一个大根堆。

堆排序的思路很简单:首先将存放在L[ 1…n ]中的n个元素建成初始堆,由于堆本身的特点(以大顶堆为例)，堆顶元素就是最大值。输出堆顶元素后，通常将堆底元素送入堆顶，此时根结点已不满足大顶堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持大顶堆的性质，再输出堆顶元素。如此重复，直到堆中仅剩一个元素为止。可见堆排序需要解决$\color{green}{\text{两个问题}}$:

①如何将无序序列构造成初始堆?
②输出堆顶元素后，如何将剩余元素调整成新的堆?

堆排序的关键是构造初始堆。n 个结点的完全二叉树，最后一个结点是第$\lfloor n/2 \rfloor$个结点的孩子。对第$\lfloor n/2 \rfloor$个结点为根的子树筛选（对于大根堆，若根结点的关键字小于左右孩子中关键字较大者，则交换)，使该子树成为堆。之后向前依次对各结点$(\lfloor n/2 \rfloor -1\backsim 1)$为根的子树进行筛选，看该结点值是否大于其左右子结点的值，若不大于，则将左右子结点中的较大值与之交换，交换后可能会破坏下一级的堆，于是继续采用上述方法构造下一级的堆，直到以该结点为根的子树构成堆为止。反复利用上述调整堆的方法建堆，直到根结点。

如图8.5所示，初始时调整L(4)子树，09< 32，交换，交换后满足堆的定义;向前继续调整L(3)子树，78<左右孩子的较大者87，交换，交换后满足堆的定义;向前调整L(2)子树，17<左右孩子的较大者45，交换后满足堆的定义;向前调整至根结点L(1)，53<左右孩子的较大者87，交换，交换后破坏了L(3)子树的堆，采用上述方法对L(3)进行调整，53<左右孩子的较大者78，交换，至此该完全二叉树满足堆的定义。

输出堆顶元素后，将堆的最后一个元素与堆顶元素交换，此时堆的性质被破坏，需要向下进行筛选。将09和左右孩子的较大者78交换，交换后破坏了L(3)子树的堆，继续对L(3)子树向下筛选，将09和左右孩子的较大者65交换，交换后得到了新堆，调整过程如图8.6所示。

下面是建立大根堆的算法:

void BuildMaxHeap (ElemType A[] ,int len){
  for(int i=len/2;i>0;i--) //从 i-[n/2]～1,反复调整堆
    HeadAdjust(A,i,len);
}


void HeadAdjust (ElemType A[],int k,int len){
  //函数HeadAdjust将元素k为根的子树进行调整
  A[0]=A[k]; //A[0]暂存子树的根结点
  for(i=2*k;i<=len;i*=2){ //沿key较大的子结点向下筛选
    if(i<len& &A[i]<A[i+1])
      i++;//取key 较大的子结点的下标
    if(A[0]>=A[i]) break;//筛选结束
    else{
      A[k]=A[i];//将A[i]调整到双亲结点上
      k=i;//修改k值,以便继续向下筛选
    }
  }
  A[k]=A[0];//被筛选结点的值放入最终位置
}

调整的时间与树高有关，为O(h)。在建含n个元素的堆时，关键字的比较总次数不超过4n，时间复杂度为O(n)，这说明可以在线性时间内将一个无序数组建成一个堆。

关键字比较次数的推导，$\color{red}{\text{Q}}$：为什么是4n，还是没搞明白

严书关键字比较次数的推导

严书堆排序的算法

代码详情:严书堆排序的算法

通过对堆排序的基本了解，首先发现堆排序有两个过程刚开始得到一个待排序序列时候的$\color{green}{\text{建堆}}$和输出了一个元素之后的$\color{green}{\text{堆重建}}$

这两个步骤，都有一个$\color{green}{\text{共同的步骤}}$，「需要为$\color{red}{\text{工作指针}}$指向的元素的找到正确位置」 ，我们把这步叫做$\color{yellow}{\text{调整元素}}$

这个共同步骤的核心是按照大根堆还是小根堆(热知识：想得到一个升序序列那么使用大根堆，降序用小根堆)的需求，将$\color{red}{\text{工作指针}}$指向的元素“$\color{green}{\text{不断}}$向下层调整”,直到满足堆的定义

$\color{green}{\text{建堆}}$的关键:$\color{red}{\text{工作指针}}$从$\lfloor n/2 \rfloor$开始不断往前$\color{yellow}{\text{调整元素}}$

$\color{green}{\text{堆重建}}$的关键:将对堆顶元素输出（就是和最后一个元素交换），之后对堆顶元素进行$\color{yellow}{\text{调整元素}}$

下面是堆排序算法:

// 王道
void HeapSort (ElemType A[] ,int len){
  BuildMaxHeap (A,len);//初始建堆
  for(i=len;i>1;i--){//n-1趟的交换和建堆过程
    Swap (A[i],A[1]);//输出堆顶元素（和堆底元素交换)
    HeadAdjust(A, 1,i-1);//调整，把剩余的i-1个元素整理成堆
  }
}

同时，堆也支持插入操作。对堆进行插入操作时，先将新结点放在堆的末端，再对这个新结点向上执行调整操作。大根堆的插入操作示例如图8.7所示。

堆排序适合关键字较多的情况。例如，在1亿个数中选出前100个最大值?首先使用一个大小为100的数组，读入前100个数，建立小顶堆，而后依次读入余下的数，若小于堆顶则舍弃，否则用该数取代堆顶并重新调整堆，待数据读取完毕，堆中100个数即为所求。

堆排序算法的性能分析如下:

空间效率:仅使用了常数个辅助单元，所以空间复杂度为O(1)。

时间效率:建堆时间为O(n)，之后有n-1次向下调整操作，每次调整的时间复杂度为O(h),故在最好、最坏和平均情况下，堆排序的时间复杂度为$O(nlog_2n)$。

稳定性:进行筛选时，有可能把后面相同关键字的元素调整到前面，所以堆排序算法是一种不稳定的排序方法。例如,表L={1,$\color{green}{\text{2}}$,$\color{red}{\text{2}}$}，构造初始堆时可能将$\color{green}{\text{2}}$交换到堆顶，此时L={$\color{green}{\text{2}}$,1,$\color{red}{\text{2}}$}，最终排序序列为L={1,$\color{red}{\text{2}}$,$\color{green}{\text{2}}$}，显然，$\color{red}{\text{2}}$与$\color{green}{\text{2}}$的相对次序已发生变化。

归并排序和基数排序

归并排序

严书中归并排序的代码pp.296

归并排序与上述基于交换、选择等排序的思想不一样，“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。假定待排序表含有$n$个记录，则可将其视为$n$个有序的子表，每个子表的长度为1，然后两两归并，得到$\lceil n/2 \rceil$个长度为2或1的有序表;继续两两归并……如此重复，直到合并成一个长度为n的有序表为止，这种排序方法称为2路归并排序。

图8.8所示为2路归并排序的一个例子，经过三趟归并后合并成了有序序列。

Merge()的功能是将前后相邻的两个有序表归并为一个有序表。设两段有序表A[ low..mid ]、A[ mid+1…high ]存放在同一顺序表中的相邻位置，先将它们复制到辅助数组B中。每次从对应B中的两个段取出一个记录进行关键字的比较，将较小者放入A中，当数组B中有一段的下标超出其对应的表长(即该段的所有元素都已复制到A中）时，将另一段中的剩余部分直接复制到A中。算法如下:

ElemType *B=(Elemype *)malloc((n+1)*sizeof (ElemType));//辅助数组B
void Merge (ElemtType A[],int low,int mid,int high){
  //表A的两段A[low..mid]和A[mid+1..high]各自有序,将它们合并成一个有序表
  for (int k=low;k<=high;k++)
    B[k]=A[k];//将A中所有元素复制到B中
  for(i=low,j=mid+1,k=i;i<=mid&&j<=high; k++){
    if(B[i]<=B[j)//比较B的左右两段中的元素
      A[k]=B[i++];//将较小值复制到A中
    else
      A[k]=B[j++];
  }//for
  while (i<=mid) A[k++]=B[i++];//若第一个表未检测完，复制
  while(j<=high) A[k++]=B[j++];//若第二个表未检测完，复制
}

注意:上面的代码中，最后两个while循环只有一个会执行。

一趟归并排序的操作是，调用$\lceil n/2h \rceil$次算法merge ()，将L[ 1…n]中前后相邻且长度为h的有序段进行两两归并，得到前后相邻、长度为2h的有序段，整个归并排序需要进行$log_2n$趟。

递归形式的2路归并排序算法是基于分治的,其过程如下。

分解:将含有n个元素的待排序表分成各含n/2个元素的子表，采用2路归并排序算法对两个子表递归地进行排序。

void MergeSort (ElemType A[],int low,int high){
  if(low<high){
  int mid=(low+high) /2;//从中间划分两个子序列
  MergeSort (A,low, mid);//对左侧子序列进行递归排序
  MergeSort (A, mid+l,high);//对右侧子序列进行递归排序
  Merge (A, low,mid,high);//归并
  }//if
}

2路归并排序算法的性能分析如下:

空间效率:Merge ()操作中，辅助空间刚好为n个单元，所以算法的空间复杂度为O(n)。时间效率:每趟归并的时间复杂度为O(n)，共需进行$\lceil log_2n \rceil$趟归并，所以算法的时间复杂度为$O(nlog_2n)$。

为什么每趟归并的时间复杂度是$O(n)$

稳定性:由于 Merge ()操作不会改变相同关键字记录的相对次序，所以2路归并排序算法是一种稳定的排序方法。

注意:一般而言，对于$N$个元素进行$k$路归并排序时，排序的趟数m满足$k^m=N$，从而$m =log_kN$，又考虑到$m$为整数，所以$m =\lceil log_k N \rceil$。这和前面的2路归并是一致的。

基数排序

严书中基数排序的数据结构

严书中基数排序的代码

基数排序是一种很特别的排序方法，它不基于比较和移动进行排序，而基于关键字各位的大小进行排序。基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。

假设长度为$n$的线性表中每个结点$a_j$的关键字由$d$元组$(k_j^{d-1} , k_j^{d-2} ,\cdots ,k_j^{1},k_j^{0}$组成,满足$0 \leq k_j^i \leq r-1(0\leq j < n, 0 \leq i \leq d-1)$。其中$k_j^{d-1}$为最主位关键字，$k_j^0$为最次位关键字

为实现多关键字排序，通常有两种方法:第一种是最高位优先($\color{green}{\text{MSD}}$）法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。第二种是最低位优先（$\color{green}{\text{LSD}}$）法，按关键字权重递增依次进行排序，最后形成一个有序序列。

下面描述以r为基数的最低位优先基数排序的过程，在排序过程中，使用r个队列$Q0，Q_1,\cdots,Q{r-1}$。基数排序的过程如下：

对$i=0,1,\cdots,d-1$,一次做一次“分配”和“收集”（其实是一次稳定的排序过程）

分配：开始时，把$Q0，Q_1,\cdots,Q{r-1}$各个队列置成空队列，然后一次考察线性表中的每个节点$a_j(j=0,1,\cdots,n-1)$，若$a_j$的关键字$k_j^i=k$，就把$a_j$放进$Q_k$队列中

通常采用链式基数排序，假设对如下10个记录进行排序:

每个关键字是1000以下的正整数，基数r= 10，在排序过程中需要借助10个链队列，每个关键字由3位子关键字构成$K^1K^2K^3$，分别代表百位、十位和个位，一共需要进行三趟“分配”和“收集”操作。第一趟分配用最低位子关键字$K^3$进行，将所有最低位子关键字（个位)相等的记录分配到同一个队列，如图 8.9(a)所示，然后进行收集操作，第一趟收集后的结果如图8.9(b)所示。

第二趟分配用次低位子关键字$K^2$进行，将所有次低位子关键字(十位）相等的记录分配到同一个队列，如图8.10(a)所示，第二趟收集后的结果如图8.10(b)所示。

第三趟分配用最高位子关键字$K^1$进行，将所有最高位子关键字（百位）相等的记录分配到同一个队列，如图8.11(a)所示，第三趟收集后的结果如图8.11(b)所示，至此整个排序结束

基数排序算法的性能分析如下。
空间效率:一趟排序需要的辅助存储空间为r(r个队列:r个队头指针和r个队尾指针)，但以后的排序中会重复使用这些队列，所以基数排序的空间复杂度为O(r)。

时间效率:基数排序需要进行d趟分配和收集，一趟分配需要O(n)，一趟收集需要O(r)，所以基数排序的时间复杂度为O(d(n +r))，它与序列的初始状态无关。

稳定性:对于基数排序算法而言，很重要一点就是按位排序时必须是稳定的。因此.这也保证了基数排序的稳定性。

各种内部排序算法的比较及应用

内部排序算法的比较

前面讨论的排序算法很多，对各算法的比较是考研中必考的内容。一般基于三个因素进行对比:时空复杂度、算法的稳定性、算法的过程特征。

从时间复杂度看:简单选择排序、直接插入排序和冒泡排序平均情况下的时间复杂度都为$O(n^2)$,且实现过程也较简单,但直接插入排序和冒泡排序最好情况下的时间复杂度可以达到O(n)，而简单选择排序则与序列的初始状态无关。希尔排序作为插入排序的拓展，对较大规模的排序都可以达到很高的效率，但目前未得出其精确的渐近时间。堆排序利用了一种称为堆的数据结构，可在线性时间内完成建堆，且在$O(nlog_2n)$内完成排序过程。快速排序基于分治的思想，虽然最坏的情况下快速排序时间会达到$O(n^2)$，但快速排序平均性能可以达到$O(nlog_2n)$与初始序列的排列无关，优于其他排序算法。归并排序同样基于分治的思想，但由于其分割子序列与初始序列的排序无关，因此它的最好、最坏和平均时间复杂度均为$O(nlog_2n)$。

从空间复杂度看:简单选择排序、插入排序、冒泡排序、希尔排序和堆排序都仅需要常数个辅助空间。快速排序在空间上只使用一个小的辅助栈，用于实现递归，平均情况下大小位$O(log_2n)$，当然在最坏情况下可能会增长到$O(n)$。2路归并排序在合并操作中需要借助较多的空间用于元素复制，大小为$O(n)$，虽然有方法能克服这个缺点，但其代价是算法会很复杂而且时间复杂度会增加。

从稳定性看:插入排序、冒泡排序、归并排序和基数排序是稳定的排序方法，而简单选择排序、快速排序、希尔排序和堆排序都是不稳定的排序方法。对于排序方法的稳定性，读者应能从算法本身的原理上去理解，而不应拘泥于死记硬背。

从过程特征看:采用不同的排序算法，在一次循环或几次循环后的排序结果可能是不同的，考研题中经常出现给出一个待排序的初始序列和已经部分排序的序列，问其采用何种排序算法。这就要对各类排序算法的过程特征十分熟悉，如冒泡排序和堆排序在每趟处理后都能产生当前的最大值或最小值，而快速排序一趟处理就能确定一个元素的最终位置等。

表8.1列出了各种排序算法的时空复杂度和稳定性情况，其中空间复杂度仅列举了平均情况的复杂度，由于希尔排序的时间复杂度依赖于增量函数，所以无法准确给出其时间复杂度。

数组排序的方式：

排序方式	时间复杂度(最好/平均/最坏)	空间复杂度(最好/平均/最坏)	稳定性	数组	链表
直接插入排序	$O(n)$/$O(n^2)$/$O(n^2)$	$O(1)$	$\color{green}{\checkmark}$	$\color{green}{\checkmark}$	$\color{green}{\checkmark}$
希尔排序	$O(nlogn), O(n^{1.3})$/None/$O(n^2)$	$O(1)$	$\color{red}{\times}$	$\color{green}{\checkmark}$	$\color{red}{\times}$
冒泡排序	$O(n)$/$O(n^2)$/$O(n^2)$	$O(1)$	$\color{green}{\checkmark}$	$\color{green}{\checkmark}$	$\color{green}{\checkmark}$
快速排序	$O(nlogn)$/$O(nlogn)$/$O(n^2)$	$O(logn) \backsim O(n)$	$\color{red}{\times}$	$\color{green}{\checkmark}$	$\color{red}{\times}$
简单选择选择排序	$O(n^2)$/$O(n^2)$/$O(n^2)$	$O(1)$	$\color{red}{\times}$	$\color{green}{\checkmark}$	$\color{green}{\checkmark}$
堆排序	$O(nlogn)$/$O(nlogn)$/$O(nlogn)$	$O(1)$	$\color{red}{\times}$	$\color{green}{\checkmark}$	$\color{red}{\times}$
归并排序	$O(nlogn)$/$O(nlogn)$/$O(nlogn)$	$O(n)$	$\color{green}{\checkmark}$	$\color{green}{\checkmark}$	$\color{green}{\checkmark}$
基数排序	$O(d(n+r))$/$O(d(n+r))$/$O(d(n+r))$	$O(r)$	$\color{green}{\checkmark}$	$\color{green}{\checkmark}$	$\color{green}{\checkmark}$

• 关于为什么$\color{green}{\text{直接插入排序}}$可以用于$\color{green}{\text{链表}}$,直接插入排序将遍历有序表的插入位置变成指针的移动实现和for i一样的操作

可视化参考文献

三种方法解决链表排序问题

内部排序算法的应用

通常情况，对排序算法的比较和应用应考虑以下情况。

1）选取排序方法需要考虑的因素

${\textstyle\unicode{x2460}}$ 待排序的元素数目n。

${\textstyle\unicode{x2461}}$元素本身信息量的大小。

${\textstyle\unicode{x2462}}$ 关键字的结构及其分布情况。

${\textstyle\unicode{x2463}}$ 稳定性的要求。

${\textstyle\unicode{x2464}}$ 语言工具的条件,存储结构及辅助空间的大小等。

2）排序算法小结

${\textstyle\unicode{x2460}}$ 若n较小，可采用直接插入排序或简单选择排序。由于直接插入排序所需的记录移动次数较简单选择排序的多，因而当记录本身信息量较大时，用简单选择排序较好。

②若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。

③若n较大，则应采用时间复杂度为$O(nlog_2n)$的排序方法:快速排序、堆排序或归并排序。快速排序被认为是目前基于比较的内部排序方法中最好的方法，当待排序的关键字随机分布时，快速排序的平均时间最短。堆排序所需的辅助全间少于快速排序，并且不会出现快速排序可能出现的最坏情况，这两种排序都是不稳定的。若要求排序稳定且时间复杂度为$O(nlog_2n)$，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用，利用直接插入排序求得较长的有序子文件，然后两两归并。直接插入排序是稳定的，因此改进后的归并排序仍是稳定的。

④在基于比较的排序方法中，每次比较两个关键字的大小之后，仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明:当文件的n个关键字随机分布时，任何借助于“比较”的排序算法，至少需要$O(nlog_2n)$的时间。

⑤若n很大，记录的关键字位数较少且可以分解时，采用基数排序较好。

⑥当记录本身信息量较大时，为避免耗费大量时间移动记录，可用链表作为存储结构。

外部排序

外部排序可能会考查相关概念、方法和排序过程，外部排序的算法比较复杂,不会在算法去设计上进行考查。本节的主要内容有:

${\textstyle\unicode{x2460}}$ 外部排序指待排序文件较大，内存一次放不下，需存放在外存的文件的排序

②为减少平衡归并中外存读写次数所采取的方法:增大归并路数和减少归并段个数。

③利用败者树增大归并路数。

④利用置换-选择排序增大归并段长度来减少归并段个数。

${\textstyle\unicode{x2464}}$ 由长度不等的归并段，进行多路平衡归并，需要构造最佳归并树。

外部排序的基本概念

前面介绍过的排序方法都是在内存中进行的（称为内部排序)。而在许多应用中，经常需要对大文件进行排序，因为文件中的记录很多、信息量庞大，无法将整个文件复制进内存中进行排序。因此，需要将待排序的记录存储在外存上，排序时再把数据一部分一部分地调入内存进行排序，在排序过程中需要多次进行内存和外存之间的交换。这种排序方法就称为外部排序。

外部排序的方法

文件通常是按块存储在磁盘上的，操作系统也是按块对磁盘上的信息进行读写的。因为磁盘读/写的机械动作所需的时间远远超过内存运算的时间（相比而言可以忽略不计)，因此在外部排序过程中的时间代价主要考虑访问磁盘的次数，即I/O次数。

外部排序通常采用归并排序法。它包括两个相对独立的阶段:①根据内存缓冲区大小，将外存上的文件分成若干长度为$\ell$的子文件，依次读入内存并利用内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写回外存，称这些有序子文件为归并段或顺串;②对这些归并段进行逐趟归并，使归并段（有序子文件）逐渐由小到大，直至得到整个有序文件为止。

例如，一个含有2000个记录的文件，每个磁盘块可容纳125个记录，首先通过8次内部排序得到8个初始归并段R1~R8，每个段都含250个记录。然后对该文件做如图8.7所示的两两归并，直至得到一个有序文件。

把内存工作区等分为3个缓冲区，如图8.6所示，其中的两个为输入缓冲区，一个为输出缓冲区。首先，从两个输入归并段R1和R2中分别读入一个块，放在输入缓冲区1和输入缓冲区2中。然后，在内存中进行2路归并，归并后的对象顺序存放在输出缓冲区中。若输出缓冲区中对象存满，则将其顺序写到输出归并段(R1’)中，再清空输出缓冲区，继续存放归并后的对象。若某个输入缓冲区中的对象取空，则从对应的输入归并段中再读取下一块，继续参加归并。如此继续，直到两个输入归并段中的对象全部读入内存并都归并完成为止。当R1和R2归并完后，再归并R3和R4、R5和R6、最后归并R7和R8，这是一趟归并。再把上趟的结果R1’和R2’、R3’和R4’两两归并，这又是一趟归并。最后把R1”和R2”两个归并段归并，结果得到最终的有序文件，一共进行了3趟归并。

在外部排序中实现两两归并时，由于不可能将两个有序段及归并结果段同时存放在内存中，因此需要不停地将数据读出、写入磁盘，而这会耗费大量的时间。一般情况下:

外部排序的总时间=内部排序所需的时间＋外存信息读写的时间＋内部归并所需的时间

显然，外存信息读写的时间远大于内部排序和内部归并的时间，因此应着力减少I/O次数。由于外存信息的读/写是以“磁盘块”为单位的，可知每一趟归并需进行16次“读”和16次“写”,3趟归并加上内部排序时所需进行的读/写，使得总共需进行32x3＋32=128次读写。

$\color{red}{\text{Q}}$:为什么是16次读，16次写？
$\color{red}{\text{A}}$:2000/125=16

若改用4路归并排序，则只需⒉趟归并，外部排序时的总读/写次数便减至32×2 + 32 = 96。因此，增大归并路数，可减少归并趟数，进而减少总的磁盘IO次数，如图8.8所示。

一般地，对r个初始归并段，做k路平衡归并，归并树可用严格k叉树（即只有度为k与度为0的结点的k叉树）来表示。第一趟可将r个初始归并段归并为$\lceil r/k \rceil$个归并段，以后每趟归并将m个归并段归并成$\lceil m/k \rceil$ 个归并段，直至最后形成一个大的归并段为止。树的高度=$\lceil log_kr \rceil$= 归并趟数$S$。可见，只要增大归并路数$k$，或减少初始归并段个数$r$，都能减少归并趟数$S$，进而减少读写磁盘的次数，达到提高外部排序速度的目的。

多路平衡归并与败者树

上节讨论过，增加归并路数k能减少归并趟数S，进而减少I/O次数。然而，增加归并路数k时，内部归并的时间将增加。做内部归并时，在k个元素中选择关键字最小的记录需要比较k-1次。每趟归并n个元素需要做(n-1)(k-1)次比较，S趟归并总共需要的比较次数为

S(n- 1)(k- 1)=$\lceil log_k r \rceil$ (n - 1)(k - 1)=$\lceil log_k r \rceil$ (n - 1)(k - 1)/$\lceil log_2k \rceil$

式中，$(k-1)/log_2k$随k增长而增长，因此内部归并时间亦随k的增长而增长。这将抵消由于增大k而减少外存访问次数所得到的效益。因此，不能使用普通的内部归并排序算法。

为了使内部归并不受$k$的增大的影响，引入了败者树。败者树是树形选择排序的一种变体，可视为一棵完全二叉树。$k$个叶结点分别存放$k$个归并段在归并过程中当前参加比较的记录，内部结点用来记忆左右子树中的“失败者”，而让胜者往上继续进行比较，一直到根结点。若比较两个数，大的为失败者、小的为胜利者，则根结点指向的数为最小数。

S趟归并总共需要的比较次数怎么来的
外部归并的时候每一次要从内存中选出最小的值，最原始的算法就是遍历内存中的所有值

构建败者树的参考文献

构建败者树的过程

置换-选择排序(生成初始归并段）

最佳归并树