排序的概念，插入排序【直接插入排序，折半插入排序，希尔排序】，交换排序【冒泡排序，快速排序】，选择排序【简单选择排序，堆排序】，归并排序，基数排序，外部排序【败者树，置换-选择排序，最佳归并树】

视频讲解，习题讲解，思维导图，PPT资源

链接: https://pan.baidu.com/s/10PuvWgq_th7xFmcQQr7RnA 密码: 9koe

数据结构可视化：

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

1. 排序的基本概念

排序(Sort)，就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。

输入：n个记录 R₁，R₂，… ， R_n，对应的关键字为 k₁，k₂，…， k_n

输出：输入序列的一个重排 R₁^ʹ，R₂^ʹ，…，R_n^ʹ，使得有 $k_{1}^{‘} \leq k_{2}^{ʹ}…\leq k_{n}^{‘}$ (也可递减)

2. 排序算法的评价指标

时间复杂度

空间复杂度

稳定性：若待排序表中有两个元素 R_i 和 R_j，其对应的关键字相同即 key_i = key_j，且在排序前 R_i在 R_j 的前面，若使用某一排序算法排序后，R_i仍然在 R_j 的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的，关键字相同的元素在排序之后相对位置不变

3. 排序算法的分类

3.1. 内部排序

数据都在内存中，关注如何使算法时间复杂度，空间复杂度更低

插入排序：直接插入排序，折半插入排序，希尔排序

交换排序：冒泡排序，快速排序

选择排序：简单选择排序，堆排序

归并排序

基数排序

3.2. 外部排序

数据太多，无法全部放入内存，还要关注如何使读写磁盘次数更少

时间复杂度=读写磁盘时间+内部排序时间(生成最初归并段)+内部归并时间

败者树—减少关键字比较次数

置换-选择排序—增加初始段长度—减少初始段数量

最佳归并树—构建严格K叉哈夫曼树—减少WPL—减少磁盘I/O次数

4. 插入排序

4.1. 算法思想

每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。

4.2. 算法代码

void InsertSort(int A[],int n){
  for(int i=1;i<n;i++){
    if(A[i]<A[i-1]){
      int j;
      for(j=i-1;j>=0&&A[j]>A[i];j--){
        A[j+1]=A[j];
      }
      A[j+1]=A[i];
    }
  }
}
//===========带哨兵===========================
void InsertSort(int A[],int n){
  for(int i=2;i<=n;i++){
    if(A[i]<A[i-1]){
      A[0]=A[i];
      int j;
      for(j=i-1;A[j]>A[0];j--){
        A[j+1]=A[j];
      }
      A[j+1]=A[0];
    }
  }
}

4.3. 算法分析

4.3.1. 空间复杂度——O(1)

4.3.2. 时间复杂度

主要来自对比关键字，移动元素。若有 n 个元素，则需要 n-1 趟处理。

最好情况：

共n-1趟处理，每一趟只需要对比关键字1次，不用移动元素 —— O(n)

比较总次数为 n-1

最坏情况—带有哨兵情况:

第1趟：对比关键字2次，移动元素3次

第2趟：对比关键字3次，移动元素4次
…
第 i 趟：对比关键字 i+1次，移动元素 i+2 次

第n-1趟：对比关键字 n 次，移动元素 n+1 次

最坏时间复杂度——O(n²)

总的比较次数为 $\frac{n(n-1)}{2}$

最好时间复杂度(全部有序)：O(n)

最坏时间复杂度(全部逆序)：O(n²)

平均时间复杂度：O(n²)

4.3.3. 算法稳定性——稳定

4.3.4. 适用性——顺序表&链表

4.4. 折半插入排序——顺序表

思路：先用折半查找找到应该插入的位置，再移动元素

当 low>high 时折半查找停止，应将 [low, i-1] 内的元素全部右移，并将 A[0] 复制到 low 所指位置
当 A[mid]==A[0] 时，为了保证算法的“稳定性”，应继续在 mid 所指位置右边寻找插入位置

void InsertSort(int A[],int n){
  int i,j,low,high,mid;
  for(int i=1;i<n;i++){
    low = 1;
    high = i-1;
    while(low<=high){
      mid = (low+high)/2;
      if(A[mid]>A[i]){
        high = mid-1;
      }
      else{
        low = mid+1;
      }
    }
    for(j=i-1;j>=high+1;j--){
        A[j+1]=A[j];
    }
    A[high+1]=A[i];
  }
}

比起“直接插入排序”，比较关键字的次数减少了，但是移动元素的次数没变，整体时间复杂度依然是O(n²)

4.5. 希尔排序

先追求表中元素部分有序，再逐渐逼近全局有序

先将待排序表分割成若干形如 L[i, i + d, i + 2d,…, i + kd] 的“特殊”子表，对各个子表分别进行直接插入排序。缩小增量d，重复上述过程，直到d=1为止

4.5.1. 举例

4.5.2. 算法代码

void ShellSort(int A[],int n){
  int d,i,j;
  for(d=n/2;d>=1;d/=2){
    for(i=d+1;i<=n;i++){
      if(A[i]<A[i-d]){
        A[0]=A[i];
        for(j=i-d;j>0&&A[j]<A[0];j-=d){
          A[j+d]=A[j];
        }
        A[j+d]=A[0];
      }
    }
  }
}

4.5.3. 时间复杂度

和增量序列 d₁, d₂, d₃… 的选择有关，目前无法用数学手段证明确切的时间复杂度，最坏时间复杂度为 O(n²)，当n在某个范围内时，可达O(n^1.3)

4.5.4. 稳定性—不稳定

4.5.5. 适用性——顺序表

5. 交换排序

根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置

5.1. 冒泡排序

从后往前(或从前往后)两两比较相邻元素的值，若为逆序(即A[i-1]>A[i])，则交换它们，直到序列比较完。称这样过程为“一趟”冒泡排序

第i趟结束后，最小的i个元素会“冒”到最前边

若某一趟排序没有发生“交换”，说明此时已经整体有序。

5.1.1. 算法代码

void swap(int &a,int &b){
  int temp = a;
  a = b;
  b = temp;
}
//======从后往前=======
void BubbleSort(int A[],int n){
  bool flag = false;
  for(int i=0;i<n-1;i++){
    flag = false;
    for(int j=n-1;j>i;j--){
      if(A[j-1]>A[j]){
        swap(A[j-1],A[j]);
        flag = true;
      }
    }
    if(!flag){
      return;
    }
  }
}
//======从前往后=======
void BubbleSort(int A[],int n){
  bool flag = false;
  for(int i=0;i<n-1;i++){
    flag = false;
    for(int j=0;j<n-1-i;j++){
      if(A[j]>A[j+1]){
        swap(A[j+1],A[j]);
        flag = true;
      }
    }
    if(!flag){
      return;
    }
  }
}

5.1.2. 空间复杂度——O(1)

5.1.3. 时间复杂度

最好情况(有序)：第一趟冒泡后flag依然为false，从而直接跳出循环。比较次数=n-1；交换次数=0；最好时间复杂度=O(n)

最坏情况(逆序)：比较次数=(n-1)+(n-2)+…+1 = n(n − 1)/2 =交换次数；最坏时间复杂度=O(n²)

平均时间复杂度=O(n²)

5.1.4. 稳定性——稳定

5.1.5. 适用性——顺序表&链表

5.2. 快速排序

5.2.1. 算法思想

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

枢轴：用第一个元素把待排序序列“划分”为两个部分。左边更小，右边更大。该元素的最终位置已确定

5.2.2. 一“趟”排序

408考点中：对尚未确定最终位置的所有元素都处理一遍才是一趟排序。

要对枢纽前后两块子表各做一次快速排序才是一“趟”快速排序。

不可能是快速排序第二趟结果的是：【4】

02，05，12，16，28，32，60，72

05，02，16，12，28，60，32，72

第一趟匹配72，第二趟匹配28
02，16，05，28，12，60，32，72

第一趟匹配72，第二趟匹配2
02，12，16，05，28，32，72，60

第一趟匹配02，第二趟匹配28或32
05，02，12，28，16，32，72，60

第一趟匹配12/32，第二趟匹配？

5.2.3. 算法代码

int Partition(int A[],int low,int high){
  int 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 low;
}

void QuickSort(int A[],int low,int high){
  if(low<high){
    int pivot = Partition(A,low,high);
    QuickSort(A,low,mid-1);
    QuickSort(A,mid+1,high);
  }
}

采用随机划分

int Partition(int A[],int low,int high){
  int randIndex = low+rand()%(high-low+1);
  swap(A[low],A[randIndex]);
  int pivot = A[low];
  int i = low;
  for(int j=low+1;j<=high;j++){
    if(A[j]<pivot){
      A[++i]=A[j];
    }
  }
  swap(A[i],A[low]);
  return i;
}

5.2.4. 空间复杂度

O(递归层数)

最好空间复杂度=O(log₂n) 最坏空间复杂度=O(n)

5.2.5. 时间复杂度

每一层的 QuickSort 只需要处理剩余的待排序元素，时间复杂度不超过O(n)

时间复杂度=O(n*递归层数)

把n个元素组织成二叉树，二叉树的层数就是递归调用的层数

n个结点的二叉树，最小高度 = $\left \lfloor log_{2}n \right \rfloor +1$，最大高度 = n ——数据已有序，树变单支

最好时间复杂度=O(nlog₂n) ：每次选的枢轴元素都能将序列划分成均匀的两部分

最坏时间复杂度=O(n²)：若序列原本就有序或逆序，则时间复杂度最高(可优化，尽量选择可以把数据中分的枢轴元素)

平均时间复杂度=O(nlog₂n)

快速排序是所有内部排序算法中平均性能最优的排序算法

5.2.6. 稳定性—不稳定

5.2.7. 适用性——顺序表

6. 选择排序

每一趟在待排序元素中选取关键字最小(或最大)的元素加入有序子序列

6.1. 简单选择排序

每一趟在待排序元素中选取关键字最小的元素加入有序子序列

n个元素的简单选择排序需要 n-1 趟处理

6.1.1. 算法代码

void SelectSort(int A[],int n){
  for(int i=0;i<n-1;i++){
    int min = i;
    for(int j=i+1;j<n;j++){
      if(A[j]<A[min]){
        min = j;
      }
    }
    if(min!=i){
      swap(A[i],A[min]);
    }
  }
}

6.1.2. 空间复杂度——O(1)

6.1.3. 时间复杂度

O(n²)

无论有序、逆序、还是乱序，一定需要 n-1 趟处理

总共需要对比关键字 (n-1)+(n-2)+…+1 = n(n − 1)/2 次

元素交换次数 < n-1

6.1.4. 稳定性—不稳定

6.1.5. 适用性——顺序表&链表

6.2. 堆排序

6.2.1. 什么是“堆(Heap)”

若n个关键字序列L[1…n] 满足下面某一条性质，则称为堆(Heap):

若满足：L(i) $\geq L(2i)且L(i) \geq L(2i+1) (1 \leq i \leq \frac{n}{2})$—— 大根堆(大顶堆) ：完全二叉树中根 $\geq$左、右
若满足：L(i) $\leq L(2i)且L(i) \leq L(2i+1) (1 \leq i \leq \frac{n}{2}$ )—— 小根堆(小顶堆)：完全二叉树中根$\geq$左、右

在顺序存储的完全二叉树中，非终端结点编号 i $\leq \left \lfloor n/2 \right \rfloor$

6.2.2. 二叉树的顺序存储

i的左孩子 ——2i
i 的右孩子 ——2i+1
i的父节点 ——i/2
i 所在的层次 —— $\left \lceil log_{2}(n + 1)\right \rceil$ 或 $\left \lfloor log_{2}n \right \rfloor$ + 1

若完全二叉树中共有n个结点，则

判断 i 是否有左孩子? ——2i ≤ n
判断i是否有右孩子? ——2i+1≤n
判断i是否是叶子/分支结点?——i > $\left \lfloor n/2 \right \rfloor$

如果不是完全二叉树，依然按层序将各节点顺序存储，那么无法从结点编号反映出结点间的逻辑关系

最坏情况：高度为 h 且只有 h 个结点的单支树(所有结点只有右孩子)，也至少需要 2^h-1 个存储单元

结论：二叉树的顺序存储结构，只适合存储完全二叉树

6.2.3. 算法思想

把所有非终端结点都检查一遍，是否满足大根堆的要求，如果不满足，则进行调整

检查当前结点是否满足根 $\geq$左、右，若不满足，将当前结点与更大的一个孩子互换

若元素互换破坏了下一级的堆，则采用相同的方法继续往下调整(小元素不断“下坠”)

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

堆排序：将堆的最后一个元素与堆顶元素交换，此时堆的性质被破坏，从堆顶元素开始向下进行筛选

6.2.4. 算法代码

void AdjustDown(int A[],int i,int len){
  int j = 2*i;
  while(j<=len){
    if(j+1<=len&&A[j]<A[j+1]){
      j++;
    }
    if(A[i]>A[j]){
      break;
    }
    else{
      swap(A[i],A[j]);
      i=j;
      j=2*j;
    }
  }
}

void createHeap(int A[],int len){
  for(int i=len/2;i>0;i--){
    AdjustDown(A,i,len);
  }
}

void HeapSort(int A[],int n){
  createHeap(A,n);
  for(int i=n;i>1;i--){
    //与待排序序列中的最后一个元素交换
    swap(A[i],A[1]);
    AdjustDown(A,1,i-1);
  }
}

6.2.5. 空间复杂度 ——O(1)

6.2.6. 时间复杂度

结论：一个结点，每“下坠”一层，最多只需对比关键字2次

若树高为h，某结点在第 i 层，则将这个结点向下调整最多只需要“下坠” h-i 层，关键字对比次数不超过 2(h-i)

n个结点的完全二叉树树高 h= $\left \lfloor log_{2} n \right \rfloor$ + 1

第 i 层最多有 2ⁱ⁻¹ 个结点，而只有第 1 ~ (h-1) 层的结点才有可能需要“下坠”调整

将整棵树调整为大根堆，关键字对比次数不超过

$\sum_{i=h-1}^{1}2^{i-1}2(h-i) = \sum_{i=h-1}^{1} 2^{i}(h-i) = \sum_{i=1}^{h-1}2^{h-j}j \leq 2n\sum_{i=1}^{h-1}\frac{j}{2^{j}} \leq 4n$

建堆的过程，关键字对比次数不超过4n，建堆时间复杂度=O(n)

交换最后一个结点和堆顶结点，重新进行下坠，总共需要 n-1趟，根节点最多“下坠” h-1 层，每下坠一层而每“下坠”一层，最多只需对比关键字2次，因此每一趟排序复杂度不超过 O(h) = O(log₂n) 共n-1 趟，总的时间复杂度 = O(nlog2n)

堆排序的时间复杂度 = O(n) + O(nlog2n) = O(nlog2n)

6.2.7. 稳定性——不稳定

建立初始堆

交换堆顶和最后一个元素

将堆顶2进行下坠判断，是否符合大根堆（符合），继续和最后一个元素1交换后进行堆排序

6.2.8. 堆中的插入

对于小根堆，新元素放到表尾，与父节点对比，若新元素比父节点更小，则将二者互换。新元素就这样一路“上升”，直到无法继续上升为止

void AdjustUp(int A[],int i){
  int temp = A[i];
  int j = i/2;
  while(j>0&&A[j]<A[i]){
      swap(A[j],A[i]);
      i=j;
      j=j/2;
  }
}

6.2.9. 堆中的删除

被删除的元素用堆底元素替代，然后让该元素不断“下坠”，直到无法下坠为止

6.2.10. 适用性——顺序表

6.2.11. 适用案例

在1亿个数中选出前100个最大值？

适用大小为100的数组，读入前100个数，建立小根堆，而后依次读入余下的数，若小于堆顶则舍弃，否则用该数取代堆顶并重新调整堆，代数据读取完毕，堆中100个数即为所求。

7. 归并排序

归并：把两个或多个已经有序的序列合并成一个

“2路”归并：每选出一个小元素需对比关键字1次

“4路”归并：每选出一个小元素需对比关键字3次

m路归并，每选出一个元素需要对比关键字m-1次

7.1. 2路归并排序(手算模拟)

7.2. 代码实现

int *B=(int *)malloc(n*sizeof(int));

//A[low,mid]和A[mid+1,high]各自有序，将两个部分归并
void merge(int A[],int low,int mid,int high){
  int i,j,k;
  for(int k=low;k<=high;k++){
    B[k]=A[k];
  }
  for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
    //两个元素相等时，优先使用靠前的那个(稳定性)
    if(B[i]<=B[j]){
      A[k]=B[i++];
    }else{
      A[k]=B[j++];
    }
  }
  while(i<=mid){
    A[k++]=B[i++];
  }
  while(j<=high){
    A[k++]=B[j++];
  }
}

//归并排序-递归
void MergeSort(int A[],int low,int high){
  if(low<high){
    int mid = (low+high)/2;
    // 将左右两个子序列分别进行归并排序(每个子序列只含有1个元素)
    MergeSort(A,low,mid);
    MergeSort(A,mid+1,high);
    // 左右两个子序列分别有序之后再将二者归并
    Merge(A,low,mid,high);
  }
}

//非递归
void MergeSort(int A[],int n){
  for(int step = 2;step<=n/2;step+=2){
    for(int i=0;i<n;i+=step){
      int mid = left+step/2-1;
      if(mid+1<n){
        merge(A,i,min(i+step-1,n-1));
      }
    }
  }
}

7.3. 时间复杂度

2路归并的“归并树”——形态上就是一棵倒立的二叉树

二叉树的第h层最多有 2^h−1个结点若树高为h，则应满足 n ≤ 2^h−1 即 h − 1 = $\left \lceil log_{2} n \right \rceil$

结论：n个元素进行2路归并排序，归并趟数= $\left \lceil log_{2} n \right \rceil$

每趟归并时间复杂度为 O(n)，则算法时间复杂度为 O(nlog₂n)

7.4. 空间复杂度

O*(*n)，来自于辅助数组B

7.5. Sort函数实现

void MergeSort(int A[],int n){
  for(int step = 2;;step*=2){
    for(int i=0;i<n;i+=step){
      sort(A+i,A+min(i+step,n));
    }
    if(step>n){
      return;
    }
  }
}

8. 基数排序

8.1. 得到按关键字“递减”的有序序列

8.2. 算法思想

假设⻓度为n的线性表中每个结点 a_j 的关键字由 d 元组 ( $k^{d-1}{j}，k^{d-2}{j}，k^{d-3}{j}，… ，k^{1}{j}，k^{0}_{j}$ ) 组成

其中，0 $\leq k^{j}_{i} \leq r-1 (0 \leq j \leq n, 0 \leq i \leq d-1)$，r 称为“基数”

基数排序得到递增序列的过程如下，

初始化: 设置 r 个空队列，Q₀, Q₁,…, Q_r−1

按照各个关键字位权重递增的次序(个、十、百)，对 d 个关键字位分别做“分配”和“收集”

分配：顺序扫描各个元素，若当前处理的关键字位=x，则将元素插入 Qx 队尾

收集：把 Q₀, Q₁,…, Q_r−1 各个队列中的结点依次出队并链接

8.3. 空间复杂度 ——O(r)

需要 r 个辅助队列

8.4. 时间复杂度

一趟分配O(n)，一趟收集O(r)，总共 d 趟分配、收集，总的时间复杂度=O(d(n+r))

把关键字拆为d个部分

每个部分可能取得 r 个值

8.5. 稳定性——稳定

8.6. 应用

某学校有 10000 学生，将学生信息按年龄递减排序

生日可拆分为三组关键字:年(1991~~2005)、月(1~~12)、日(1~31)，权重：年>月>日

第一趟分配、收集(按“日”递增)：1，2，3，… ，31

第二趟分配、收集(按“月”递增)：1，2，3，… ，12

第三趟分配、收集(按“年”递增)：1991，1992，1993，… ，2004，2005

基数排序，时间复杂度 = O(d(n+r)) = O(3x(10000+max{31,12,14})) $\approx$ O(30000)

若采用O(n²)的排序，$\approx$ O(10⁸)

若采用O(nlog₂n)的排序，$\approx$ O(140000)

基数排序擅⻓解决的问题：

数据元素的关键字可以方便地拆分为 d 组，且 d 较小

反例：给5个人的身份证号排序，18位身份证号需要分配、回收18趟
每组关键字的取值范围不大，即 r 较小

反例：给中文人名排序，每个字可能有上万种取值
数据元素个数 n 较大，擅⻓：给十亿人的身份证号排序

9. 各类内部排序对比

算法种类	最好时间复杂度	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性	排序趟数与序列原始状态无关
直接插入排序	O(n)	O(n²)	O(n²)	O(1)	稳定	趟数固定为n-1
希尔排序					不稳定
冒泡排序	O(n)	O(n²)	O(n²)	O(1)	稳定
快速排序	O(nlog₂n)	O(nlog₂n)	O(n²)	O(log₂n)	不稳定	趟数固定为log₂n
简单选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定	趟数固定为n-1
堆排序	O(nlog₂n)	O(nlog₂n)	O(nlog₂n)	O(1)	不稳定
归并排序	O(nlog₂n)	O(nlog₂n)	O(nlog2n)	O(n)	稳定
基数排序	O(d(n+r))	O(d(n+r))	O(d(n+r))	O(r)	稳定	趟数固定为d

与初始状态无关

	直接插入	希尔	快速	简单选择	堆	归并	基数
排序趟数与序列原始状态无关	☑️	☑️	☑️	☑️	☑️		☑️
排序移动次数与序列原始状态无关						☑️	☑️
排序比较次数与序列原始状态无关				☑️			☑️
算法复杂度与序列原始状态无关				☑️	☑️	☑️	☑️

10. 外部排序

10.1. 外存、内存之间的数据交换

10.2. 外部排序原理

若要进行K路归并原理，则需要在内存中分配K个输入缓冲区和1个输出缓冲区

步骤：

生成r个初始归并段，若共 N 个记录，内存工作区可以容纳 L 个记录，则初始归并段数量 r = $\left \lceil N/L \right \rceil$
进行S趟K路归并，S= $\left \lceil log_{k} r \right \rceil$
把K个归并段的块读入K个输入缓冲区
用“归并排序”的方法从K个归并段中选出几个最小记录暂存到输出缓冲区中
当输出缓冲区满时，写出外存

10.2.1. 进行2路归并

需要在内存中分配2个输入缓冲区和1个输出缓冲区

10.2.1.1. 构造初始“归并段”

把2个归并段的块读入2个输入缓冲区，用“归并排序”的方法从2个归并段中选出最小记录暂存到输出缓冲区中

当输出缓冲区满时，写出外存

最终生成有序的初始归并段

共有8个初始归并段，则需要进行 S= $\left \lceil log_{2} 8 \right \rceil$ = 3趟2路归并

10.2.1.2. 第一趟归并

把8个有序子序列(初始归并段)两两归并

10.2.1.3. 第二趟归并

把4个有序子序列(归并段) 两两归并

10.2.1.4. 第三趟归并

把2个有序子序列 (归并段)归并

10.2.1.5. 时间开销分析

10.2.2. 什么是多路平衡归并?

误❌：对 r个初始归并段，做k路平衡归并，归并树可用严格 k 叉树(即只有度为 k 与度为0的结点的 k 叉树)来表示

k路平衡归并：

最多只能有k个段归并为一个;
每一趟归并中，若有 m 个归并段参与归并，则经过这一趟处理得到 $\left \lceil m/k \right \rceil$个新的归并段

10.2.3. 开稍时间总结

磁盘是慢速设备，读写次数太多导致时间开销大幅增加

外部排序时间开销=读写外存的时间+内部排序所需时间+内部归并所需时间

读写外存的时间——磁盘I/O时间

内部排序所需时间——生成初始归并段时间

10.2.4. 优化外部排序

10.2.4.1. 多路归并

改用4路归并，将4个有序归并段归并为一个

重要结论：

采用多路归并可以减少归并趟数，从而减少磁盘I/O(读写)次数

对 r 个初始归并段，做 k 路归并，则归并树可用 k 叉树表示

若共 N 个记录，内存工作区可以容纳 L 个记录，则初始归并段数量 r = $\left \lceil N/L \right \rceil$

若树高为 h，则归并趟数 = h-1 = $\left \lceil log_{k} r \right \rceil$

推导：

k叉树第h层最多有 k^h−1 个结点则 r $\leq k^{h-1}$，

(h-1)_最小 = $\left \lceil log_{k} r \right \rceil$

k越大，r越小，归并趟数越少，读写磁盘次数越少

多路归并带来的负面影响：

k路归并时，需要开辟k个输入缓冲区，内存开销增加。
每挑选一个关键字需要对比关键字 (k-1)次，内部归并所需时间增加

通过使用败者树减少关键字对比次数

10.2.4.2. 减少初始归并段数量r

生成初始归并段的“内存工作区”越大，初始归并段越⻓

若能增加初始归并段的⻓度，则可减少初始归并段数量 r

使用置换—选择排序算法生成不等长的初始归并段，从而减少初始归并段数量

10.3. 败者树

外部排序时间开销**=**读写外存的时间+内部排序所需时间+内部归并所需时间

归并趟数 S = $\left \lceil log_{k} r \right \rceil$，归并路数k增加，归并趟数S减小，读写磁盘总次数减少

使用k路平衡归并策略，选出一个最小元素需要对比关键字 (k-1)次，每趟归并n个元素需要做(n-1)(k-1)次比较

有了败者树，选出最小元素，只需对比关键字 $\left \lceil log_{2} k \right \rceil$次

10.3.1. 比较次数计算

设有5个初始归并段，每个归并段有20个记录，采用5路平衡归并排序，若不采用败者树，使用传统的顺序选出最小记录，使用简单选择排序，总的比较次数是？

5个记录中选出最小的需要做4次比较，共有100个记录，需要做99次选择最小记录的操作，所以需要的比较次数为4x99=396次

采用败者树，总的比较次数？

败者树的高度为 h= $\left \lceil log_{2} 5 \right \rceil$ = 3，每次参加比较的记录中选择一个关键字最小的记录，比较次数不超过h，共100个记录，需要的比较次数不超过100x3 = 300

10.3.2. 概念

可视为一棵完全二叉树(多了一个头头)。k个叶结点分别是当前参加比较的元素，非叶子结点用来记忆左右子树中的“失败者”，而让胜者往上继续进行比较，一直到根结点

则归并段3的1存入输出缓冲区

10.3.3. 实现思路

对于 k 路归并，第一次构造败者树需要对比关键字 k-1 次

有了败者树，选出最小元素，只需对比关键字 $\left \lceil log_{2} k \right \rceil$次

10.4. 置换-选择排序

10.4.1. 概念

用于内部排序的内存工作区WA可容纳L个记录，则每个初始归并段也只能包含L个记录，若文件共有 N个记录，则初始归并段的数量 r=N/L，归并路数越多，需要用于内部排序的内存区域越大，内存开销增加。产生更长的初始归并段可以减少归并段数量，从而减少归并趟数。

10.4.2. 步骤

设初始待排文件为FI，初始归并段输出文件为FO，内存工作区为WA，FO和WA的初始状态为空，WA可容纳w个记录

置换-选择算法的步骤如下:

从FI输入w个记录到工作区WA
从WA中选出其中关键字取最小值的记录，记为MINIMAX记录
将MINIMAX记录输出到FO中去
若FI不空，则从FI输入下一个记录到WA中
从WA中所有关键字比MINIMAX记录的关键字大的记录中选出最小关键字记录，作为新的 MINIMAX记录
重复3)~5)，直至在WA中选不出新的MINIMAX记录为止，由此得到一个初始归并段，输出一个归并段的结束标志到FO中去
重复2)~6)，直至WA为空。
由此得到全部初始归并段。

10.5. 最佳归并树

文件经过置换-选择排序后得到的长度不等的初始归并段，需要对归并段进行归并排序，如何组织长度不等的初始归并段的归并顺序？—— 最佳归并树

10.5.1. 归并树性质

5表示需要有5个磁盘块

每个初始归并段看作一个叶子结点，归并段的⻓度作为结点权值，则这棵归并树的带权路径⻓度

WPL = 2x1 + (5+1+6+2) x 3 = 44 = 读磁盘的次数 = 写磁盘的次数

归并过程中的磁盘I/O次数=归并树的WPLx2

要让磁盘I/O次数最少，就要使归并树WPL最小——哈夫曼树

最佳归并树 WPL_min = (1+2)x4 + 2x3+5x2 + 6x1= 34

读磁盘次数=写磁盘次数=34次；总的磁盘I/O次数 = 68

10.5.2. k叉哈夫曼树的构造

对于k叉归并，若初始归并段的数量无法构成严格的 k 叉归并树(只有度为k和度为0的结点)，则需要补充几个⻓度为 0 的“虚段”，再进行 k 叉哈夫曼树的构造。

k叉的最佳归并树一定是一棵严格的 k 叉树，即树中只包含度为k、度为0 的结点。设度为k的结点有 n_k 个，度为0的结点有 n₀ 个，归并树总结点数=n

若(初始归并段数量 -1)% (k-1)= 0，说明刚好可以构成严格k叉树，此时不需要添加虚段
若(初始归并段数量 -1)% (k-1)= u != 0，则需要补充 (k-1) - u 个虚段