十一. 排序

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

排序算法评价指标：

• 时间复杂度

• 空间复杂度

• 算法稳定性：指表中相同元素先后位置，经过排序后有没有相对的变动。

  

  注意：稳定排序算法并不一定比不稳定的算法优秀，主要看实际需求。

排序算法分类：

1. 内部排序：数据都在内存中。更关注算法时间和空间复杂度
2. 外部排序：数据太多，无法全部放入内存。除了要关注算法时间和空间复杂度，还要关注如何使读$/$$/$写磁盘次数更少。

1. 插入排序

主要分为：直接插入排序、折半插入排序、希尔排序

1.1 插入排序

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

动画演示：

算法实现及分析

排序从第二个元素开始，默认当前排序元素左边已经有序。只要比当前元素大的都往后移动，直到碰到比当前元素小(相等)的。

代码实现：

1
//直接插入排序
2
void InsertSort(int A[],int n){
3
    int i,j, temp;
4
    for(i=1;i<n;i++)            //将各元素插入已排好序的序列中
5
        if(A[i]<A[i-1]){        //若A[i]关键字小于前驱
6
            temp=A[i];          //用temp暂存A[i]
7
            for(j=i-1;j>=0 && A[j]>temp;--j) //检查所有 前面已排好序的元素
8
                A[j+1]=A[j];    //所有大于temp的元素都向后挪位
9
            A[j+1]=temp;        //复制到插入位置
10
        }
11
}

带哨兵实现方法：

代码实现：

xxxxxxxxxx
11
1
//直接插入排序(带哨兵)
2
void InsertSort(int A[],int n){
3
    int i,j;
4
    for(i=2;i<=n;i++)           //依次将A[2]~A[n]插入到前面已排序序列
5
        if(A[i]<A[i-1]){        //若A[i]关键码小于其前驱，将A[i]插入有序表
6
            A[0]=A[i];          //复制为哨兵，A[0]不存放元素
7
            for(j=i-1;A[0]<A[j];--j)//从后往前查找待插入位置
8
                A[j+1]=A[j];    //向后挪位
9
            A[j+1]=A[0];        //复制到插入位置
10
        }
11
}

带哨兵排序步骤：

1. 实际存放元素从$1$$1$开始。会将当前排序元素复制到$A[0]$$A[0]$位置。
2. 接着对比左边元素，比当前元素大的都会后移，当左边某个元素大于或等于当前排序元素时，内层循环结束，将当前排序元素放在$j+1$$j+1$的位置。

这样做的优点是不用没轮循环都判断$j\ge 0$$j\ge0$

算法效率分析：

• 空间复杂度：$O(1)$$O(1)$

• 时间复杂度：主要来自对比关键字、移动元素若有$n$$n$个元素，则需要$n-1$$n-1$趟处理

  最好情况(已经有序)：共$n-1$$n-1$趟处理，每一趟只需要对比关键字$1$$1$次，不用移动元素，则最好时间复杂度$O(n)$$O(n)$

  最坏情况(逆序)：每次都要移动元素。所以最坏时间复杂度$O(n^2)$$O(n^2)$。

  平均时间复杂度：$O(n^2)$$O(n^2)$

• 算法稳定性：相同两个元素，排序后相对位置不会改变，所以稳定。

• 适用性：可用于链表，也可用于顺序表。

算法优化

思路：之前都是用顺序查找方式移动元素，实际可用折半查找找到应该插入的位置，再移动元素

假设下面$55$$55$之前元素已经有序，则优化插入排序步骤：

• 首先low=20;high=80，则mid=(low+high)/2=4，即mid指向$50$$50$元素。

  

• 由于$55>50$$55>50$所以元素$55$$55$可能插入再$50$$50$元素的右边区间内。low=mid+1;mid=(low+high)/2=6，即mid指向$70$$70$

  

• 而$70>55$$70>55$，所以$55$$55$只可能插入在$70$$70$元素左边区间。high=mid-1;mid=(low+high)/2=5，即mid指向$60$$60$

  

• $60>55$$60>55$，所以$55$$55$只可能插入在$60$$60$元素左边区间。high=mid-1;，此时low>high，故折半查找停止，应将[low, i-1]内的元素全部右移，并将A[0]复制到low所指位置。

  

• 后面元素$60,90,10$$60,90,10$同上，但要注意，当mid指向的元素和被查找元素相等时，不应该停止查找，为了算法稳定性，当元素相等时，我们应该在这个元素右边区间内查找。

代码实现：

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

算法效率：

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

直接插入排序可以用于链表的排序。对于链表来说移动元素的次数变少了，但是关键字对比的次数依然是$O(n^2)$$O(n^2)$数量级,整体来看时间复杂度依然是$O(n^2)$$O(n^2)$

1.2 希尔排序

希尔排序是对插入排序的优化。对于插入排序来说，如果要排序的元素基本有序，那么排序效率会高很多。而希尔排序核心思想是：先追求表中的元素部分有序，再逐渐逼近全局有序。

实现大致步骤：

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

动画演示：

例如：将下列表中元素进行升序排列

步骤：

• 第一趟假设$d_1=\frac{n}{2}=4$$d_1=\frac{n}{2}=4$，$n$$n$为元素个数。将表中所有相距距离为$d(4)$$d(4)$的元素视为同一子表。

  

• 对上面四个子表进行直接插入排序。

  

• 第二趟假设$d_2=\frac{d_1}{2}=2$$d_2=\frac{d_1}{2}=2$。将表中所有相距距离为$d(2)$$d(2)$的元素视为同一子表。

  

• 对上面各个子表进行直接插入排序。

  

• 接着第三趟$d_3=\frac{d_2}{2}=1$$d_3=\frac{d_2}{2}=1$，此时所有元素都会划分为同一个子表。

  

• 整个表此时已呈现出基本有序，对整体再进行一次直接插入排序

  

上面例子中，每次将增量$d$$d$缩小一半。这要是建议的做法。

代码实现：

xxxxxxxxxx
12
1
//希尔排序
2
void ShellSort(int A[] ,int n){
3
    int d,i,j;                      //A[0]只是暂存单元,不是哨兵,当j<=0时,插入位置已到
4
    for(d=n/2; d>=1; d=d/2)         //步长变化
5
        for(i=d+1; i<=n; ++i)
6
            if(A[i]<A[i-d]){        //需将A[i]插入有序增量子表
7
                A[0]=A[i];          //暂存在A[0]
8
                for(j= i-d; j>0 && A[0]<A[j]; j-=d)
9
                    A[j+d]=A[j];    //记录后移，查找插入的位置
10
                A[j+d]=A[0];        //插入
11
            }//if
12
}

上面内层第一个for循环中的++i，会让以$d$$d$为间隔的子表轮流切换排序。

算法性能分析：

• 空间复杂度：$O(1)$$O(1)$

• 时间复杂度：根据$d_i$$d_i$ 不同会受到影响目前无法用数学手段证明确切的时间复杂度。

  最坏时间复杂度：当$d=1$$d=1$时，会直接变为插入排序。最坏时间复杂度为$O(n^2)$$O(n^2)$

  当数据元素$n$$n$在某个范围内时，可达$O(n^{1.3})$$O(n^{1.3})$

• 稳定性：不稳定

  

• 适用性：仅适用于线性表，不能用于链表。

2. 交换排序

主要有：冒泡排序和快速排序

2.1 冒泡排序

冒泡排序和快速排序一样属于交换排序的一种。

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

代码实现：

xxxxxxxxxx
19
1
//交换
2
void swap(int &a，int &b){
3
    int temp = a;
4
    a=b;
5
    b = temp;
6
}
7
//冒泡排序
8
void BubbleSort(int A[],int n){
9
    for(int i=0;i<n-1;i++){
10
        bool flag=false;            //表示本趟冒泡是否发生交换的标志
11
        for(int j=n-1;j>i;j--)      //一趟冒泡过程
12
            if(A[j-1]>A[j]){        //若为逆序
13
                swap(A[j-1],A[j]);  //交换
14
                flag=true;  
15
            }
16
        if(flag==false)
17
            return;                 //本趟遍历后没有发生交换，说明表已经有序
18
    }
19
}

注意：如果某一趟排序过程中未发生"交换"则算法可提前结束。

算法效率分析：

• 空间复杂度：$O(1)$$O(1)$

• 时间复杂度：

  最好情况(原本有序)：$O(n)$$O(n)$

  最坏情况(逆序)：$O(n^2)$$O(n^2)$

  平均情况：$O(n^2)$$O(n^2)$

• 稳定性：稳定

• 适用性：链表，顺序表都可用

2.2 快速排序

算法实现思路：

在待排序表中任取一个元素作为枢轴(通常取首元素)。通过一趟排序，将待排序表划分为独立的两个部分。这两部分中，左半部分所有元素都小于枢轴元素；右半部分都大于枢轴元素，则枢轴元素确定其最终元素位置。这个过程称为一次划分。然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在最终位置上，完成排序。

动画演示如下：

代码如下：

​x
1
//默认low=0,high=arr.length-1
2
int partition(int arr[],int low,int high) {
3
    int tempA=arr[low];                 //枢轴元素
4
    while(low<high) {                   //用low、high搜索枢轴的最终位置
5
        while(low<high&&arr[high]>=tempA) high--;//从右开始,比枢轴小的元素移动到左端,即low所指位置
6
        arr[low]=arr[high];
7
        while(low<high&&arr[low]<=tempA) low++;//从左边开始,比枢轴大的元素移动到右端,即high所指位置
8
        arr[high]=arr[low];
9
    }
10
    arr[low]=tempA;                     //确定枢轴元素存放到最终位置
11
    return low;                         //返回存放枢轴的最终位置
12
}
13

14
void quickSort(int arr[],int low,int high) {
15
    if(low<high) {
16
        int p=partition(arr,low,high);  //划分确定枢轴元素位置
17
        quickSort(arr,low,p-1);         //枢轴左边表进行递归确定位置
18
        quickSort(arr,p+1,high);        //右表确定位置
19
    }
20
}

效率分析：

通过上图可以看出每一层只需要处理剩下蓝色部分待排序元素，所以时间复杂度不超过$O(n)$$O(n)$。即时间复杂度$O(n\ast \text{递}\text{归}\text{层}\text{数})$$O(n*递归层数)$

由于需要用到递归，层数越多用到空间越多，所以每一层空间复杂度是$O(\text{递}\text{归}\text{层}\text{数})$$O(递归层数)$

可以看出对于快速排序时间与空间复杂度分析必须要研究递归层数：

可以得出结论：快速排序就是把$n$$n$个元素组织成二叉树，二叉树的层数就是递归调用的层数。所以可以将问题转换为二叉树高度求法。

$n$$n$个结点二叉树最小高度$=\lfloor {\log }_{2}n\rfloor +1$$=\lfloor\log_2n\rfloor+1$；最大高度$=n$$=n$。

所以对于快速排序其最小递归层数$=\lfloor {\log }_{2}n\rfloor +1$$=\lfloor\log_2n\rfloor+1$，最大递归层数$=n$$=n$。即

• 最好时间复杂度是：$O(n{\log }_{2}n)$$O(n\log_2n)$；

  最坏时间复杂度：$O(n^2)$$O(n^2)$

• 最好空间复杂度：$O({\log }_{2}n)$$O(\log_2n)$

  最坏空间复杂度：$O(n)$$O(n)$

快速排序是不稳定地算法。

注意：若每一次选中的枢轴元素将待排序序列划分为均匀的两个部分，则递归深度最小，算法效率最高。若初始序列有序或逆序，则快速排序的性能最差(因为每次选择的都是最靠边的元素)。

基于上面分析，快速排序算法优化思路：尽量选择可以把数据中分的枢轴元素。如：

1. 选头、中、尾三个位置的元素，取中间值作为枢轴元素
2. 随机选一个元素作为枢轴元素

在实际应用当中快速排序是所有内部排序算法中平均性能最优的排序算法。

3. 选择排序

主要有：简单选择排序和堆排序

3.1 简单选择排序

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

选择排序分类：简单选择排序和堆排序。

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

动画演示：

实现代码：

xxxxxxxxxx
18
1
//交换
2
void swap(int &a,int &b){
3
    a=a-b;
4
    b=a+b;
5
    a=b-a;
6
    
7
}
8

9
//简单选择排序
10
void SelectSort(int A[],int n){
11
    for(int i=0;i<n-1;i++){             //一共进行n-1趟
12
        int min=i;                      //记录最小元素位置
13
        for(int j=i+1;j<n;j++)          //在A[i...n-1]中选择最小的元素
14
            if(A[j]<A[min]) min=j;      //更新最小元素位置
15
        if(min!=i)
16
            swap(A[i],A[min] );         //封装的swap()函数移动元素
17
    }
18
}

算法效率分析：

• 时间复杂度：无论有序、逆序、还是乱序，一定需要$n-1$$n-1$趟处理。所以时间复杂度$=O(n^2)$$=O(n^2)$
• 空间复杂度：$O(1)$$O(1)$
• 稳定性：不稳定

适用性：即可用于顺序表，也可以用于链表。

3.2 堆排序

堆排序的实现需要用到堆这种数据结构。堆这种数据结构又可以进一步划分为大根堆和小根堆。

堆结构和二叉树的顺序存储类似：

二叉树顺序表中存储结构：

几个重要操作：

• $i$$i$号结点的左孩子：$2i$$2i$
• $i$$i$号结点的右孩子：$2i+1$$2i+1$
• $i$$i$号结点的父节点：$\lfloor i/2\rfloor$$\lfloor i/2\rfloor$
• $i$$i$结点所在的层次：$\lceil {\log }_2(n+1)\rceil \text{或}\lfloor {\log }_{2}n\rfloor +1$$\lceil\log_2(n+1)\rceil或\lfloor\log_2n\rfloor+1$

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

• 判断$i$$i$是否有左孩子：$2i\le n?$$2i\le n?$
• 判断$i$$i$是否有右孩子：$2i+1\le n?$$2i+1\le n?$
• 判断$i$$i$是否是叶子$/$$/$分支结点：$\lfloor i>n/2\rfloor ?$$\lfloor i>n/2\rfloor?$

堆排序实现

堆结构也可以看作是一颗完全二叉树在顺序表存储结构：

上图左边是存储结构，右边是逻辑结构。可以观察到大根堆就是在完全二叉树中，所有的根结点$\ge$$\ge$左右子树。

所以堆排序步骤：

1. 首先将给定的随机序列表按照根结点$\ge$$\ge$左右子树特点，将表转换为大根堆结构

   具体做法是检查二叉树中所有根结点是否满足根结点$\ge$$\ge$左右子树这一特性，若不满足，与当前结点更大的孩子交换。

2. 由于大根堆表中第一个元素一定是最大元素，所以将其移动至表尾

3. 接着对剩下的表中元素再次进行大根堆结构恢复操作。

4. 依次循环上面三个步骤，直到所有最后表中只剩一个元素，排序结束

例子：给定以下序列表进行升序排序

排序步骤：

• 首先将序列表组成的二叉树转换为大根堆结构。在顺序表的完全二叉树中，非终端结点的编号为$i\le \lfloor \frac{n}{2}\rfloor$$i\le\lfloor\frac{n}{2}\rfloor$。即第一个被处理根结点是$\frac{8}{2}=4$$\frac{8}{2}=4$。即$9$$9$元素。

• 对于$9$$9$元素，其只有左孩子，并且左孩子$32>9$$32>9$，所以交换位置

  

• 接着处理$3$$3$号结点，即$78$$78$，其左右孩子为$65,87>78$$65,87>78$，所以交换$78$$78$和$87$$87$位置

  

• 处理$2$$2$号结点$17$$17$，其左右孩子$32,45$$32,45$，比左右孩子都小所以取最大的$45$$45$交换

  

• $1$$1$号结点$53$$53$比右孩子$87$$87$小，所以交换

  

• 交换后发现以$53$$53$为根的子树仍然不平衡，继续用之前方法，$53$$53$小于左右子树，所以挑最大的元素$78$$78$交换

  

• 此时，整个二叉树已经称为标准的大根堆结构，将序列表第一个元素换至表尾

  

• 接着将剩下元素重新恢复大根堆结构。恢复后结构如下：

  

• 此时已经完成第一趟处理，之后重复上述操作即可。经过$n-1$$n-1$趟处理，将序列表变为有序表：

  

注意：基于大根堆的堆排序，得到是递增序列，而基于小根堆得到的是递减序列。

实现代码：

xxxxxxxxxx
29
1
//将以k为根的子树调整为大根堆
2
void HeadAdjust(int A[],int k,int len){
3
    A[0]=A[k];                  //A[0] 暂存子树的根结点
4
    for(int i=2*k;i<=len;i*=2){ //沿key较大的子结点向下筛选
5
        if(i<len&&A[i]<A[i+1])
6
            i++;                //取key较大的子结点的下标
7
        if(A[0]>=A[i]) break;   //筛选结束
8
        else{
9
            A[k]=A[i];          //将A[i]调整到双亲结点上
10
            k=i;                //修改K值，以便继续向下筛选
11
        }
12
    }
13
    A[k]=A[0];                  //被筛选结点的值放入最终位置
14
}
15

16
//建立大根堆
17
void BuildMaxHeap(int A[],int len){
18
    for(int i=len/2;i>0;i--)    //从后往前调整所有非终端结点
19
        HeadAdjust(A,i,len);
20
}
21

22
//堆排序的完整逻辑
23
void HeapSort(int A[],int len){
24
    BuildMaxHeap(A,len);        //初始建堆
25
    for(int i=len;i>1;i--){     //n-1趟的交换和建堆过程
26
        swap(A[i],A[1]);        //堆顶元素和堆底元素交换
27
        HeadAdjust(A,1,i-1);    //把剩余的待排序元素整理成堆
28
    }
29
}

算法效率分析：

由于所有操作都是基于HeadAdjust()这个函数的，所以要分析该函数效率：

由于一个结点每下坠一层，最多只需要对比关键字两次。若树高为$h$$h$，某结点在第$i$$i$层，则将这个结点向下调整最多只需要下坠$h-i$$h-i$层，关键字对比次数不超过$2(h-i)$$2(h-i)$，$n$$n$个结点的完全二叉树树高$h=\lfloor {\log }_{2}n\rfloor |+1$$h=\lfloor \log_2n\rfloor|+1$。

第$i$$i$层最多有$2^{i-1}$$2^{i-1}$个结点，而只有第$1\sim (h-1)$$1\sim (h-1)$层的结点才有可能需要下坠调整。将整棵树调整为大根堆，关键字对比次数不超过：

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

而HeapSort()中for循环排序过程中总共需要$n-1$$n-1$趟调整，每趟调整都要将根结点下坠。而每次下坠最多只需要对比关键字$2$$2$次，因此每一趟排序复杂度不超过$O(h)=O({\log }_{2}n)$$O(h)=O(\log_2n)$，所以总的时间复杂度是$O(n{\log }_{2}n)$$O(n\log_2n)$。

• 堆排序总的时间复杂度$=O(n{\log }_{2}n)+O(n)=O(n{\log }_{2}n)$$=O(n\log_2n)+O(n)=O(n\log_2n)$
• 总的空间复杂度$=O(1)$$=O(1)$
• 稳定性：不稳定

堆的插入

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

例：将下列小根堆中插入新元素$13$$13$

• 首先将新元素$13$$13$放入表尾，再和父结点进行对比，父结点是$\lfloor \frac{9}{2}\rfloor =4$$\lfloor\frac{9}{2}\rfloor=4$，即元素$32$$32$。而$32>13$$32>13$，所以互换

  

• 接着继续和父结点$17$$17$，对比，显然$13$$13$更小，交换

  

• 接着和父结点$9$$9$对比，$9<13$$9<13$，所以不用交换结束，小根堆符合条件。

插入总共对比关键字$3$$3$次。

堆的删除

首先从序列表中将被删除元素删除，接着将表尾元素替换到被删除元素位置，再进行小根堆恢复：被删除的元素用堆底元素替代，然后让该元素不断下坠，直到无法下坠为止。

例：将下列小根堆中删除$13$$13$元素

• 首先删除$13$$13$元素，将表位元素$46$$46$移动到$13$$13$位置，即下标为$2$$2$的位置

  

• $46$$46$和左右孩子进行对比，和最小的交换。即$17$$17$和$46$$46$交换

  

• 接着再和左右孩子对比，$46<32$$46<32$，继续交换

  最后小根堆恢复

  

删除总共对比关键字$4$$4$次。

4. 归并排序

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

首先开辟一个能放入上面两个数组的更大的数组。

对比上面待排序两个数组，将$i$$i$、$j$$j$所指元素，选择更小的一个放入$k$$k$所指位置。放入后选中元素的指针$(i/j)$$(i/j)$和$k$$k$指针往后移动。当待排序数组的$i、j$$i、j$指针中有一个超出数组下标，则说明一个子表已经排序完毕，还剩一个子表未合并，可以将该表中剩余元素全部加到总表。

上面的归并称为二路归并，即每次选出一个子表中最小的元素插入新的排序序列中，这种每次选出一个元素需要对比$1$$1$次关键字。

同样还有四路归并：

对比$p1$$p1$、$p2$$p2$、$p3$$p3$、$p4$$p4$所指元素，选择更小的一个放入$k$$k$所指位置。$4$$4$路归并：每选出一个小元素注需对比关键字$3$$3$次。

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

归并排序模拟：给定以下序列，每个序列都是独立集合。

• 首先第一趟可以将初试序列，两两归并：

  

• 第二趟同样将第一趟归并后的序列再次两两归并：

  

• 第三趟归并，将第二趟序列做最后一次合并即可：

  

通过上面步骤可以得到归并排序核心操作：把数组内的两个有序序列归并为一个。

代码实现：

xxxxxxxxxx
25
1
//辅助数组B
2
int *B=(int *)malloc(n*sizeof(int));
3

4
//A[low.mid]和A[mid+1...high]各自有序,将两个部分归并
5
void Merge(int A[],int low,int mid,int high){
6
    int i,j,k;
7
    for( k=low; k<=high;k++)
8
        B[k]=A[k];              //将A中所有元素 复制到B中
9
    for(i=low, j=mid+1,k=i; i<=mid&&j<=high;k++){
10
        if(B[i]<=B[j])
11
            A[k]=B[i++];        //将较小值复制到A中
12
        else
13
            A[k]=B[j++];
14
    }//for
15
    while(i<=mid)  A[k++]=B[i++];
16
    while(j<=high) A[k++]=B[j++];
17
}
18
void MergeSort(int A[],int Low,int high){
19
    if(low<high){
20
        int mid=(low+high)/2;       //从中间划分
21
        MergeSort(A,low,mid);       //对左半部分归并排序
22
        MergeSort (A,mid+1,high);   //对右半部分归并排序
23
        Merge(A,low,mid,high);      //归并
24
    }//if
25
}

算法效率分析：

可以看到上面MergeSort()函数使用了递归进行排序。所有也可以认为二路归并是一棵倒立的二叉树。可以利用二叉树特性分析二路归并排序的算法效率。分治法递归树如下：

更详细图解：

二路归并总共需要$h-1$$h-1$趟。二叉树第$h$$h$层，最多有$2^{h-1}$$2^{h-1}$个结点，所以若树高为$h$$h$，则应满足$n\le 2^{h-1}$$n\le2^{h-1}$，$n$$n$表示结点数，即$h-1=\lceil {\log }_{2}n\rceil$$h-1=\lceil\log_2n\rceil$。

对上面算法例子进行归并分析：

时间复杂度：上面第二趟排序中，将两个序列归并时，所需要关键字对比次数$\le n-1$$\le n-1$，因为每次对比都能挑出两个序列中关键字最小的元素，所以每次对比时间复杂度是$O(n)$$O(n)$。再看初始序列，每次进行两两对比，每两个运算之间比较次数为一次，所以总共比较次数就是$\frac{n}{2}$$\frac{n}{2}$，也是$O(n)$$O(n)$这个量级，所以不管哪一趟归并，每次对比次数都需要$O(n)$$O(n)$这样的数量级。

空间复杂度为$O(n)$$O(n)$，主要来自于辅助数组$B$$B$。由于递归深度不会超过$\lceil {\log }_{2}n\rceil$$\lceil\log_2n\rceil$这个数量级，所以递归栈的空间复杂度忽略不计。

结论：$n$$n$个元素进行二路归并排序，归并趟数$=\lceil {\log }_{2}n\rceil$$=\lceil\log_2n\rceil$。每趟归并时间复杂度为$O(n)$$O(n)$，则算法时间复杂度为$O(n{\log }_{2}n)$$O(n\log_2n)$。并且归并排序是一个稳定的算法。其排序效率可以和堆排序、快速排序达到同样的优秀程度。

归并排序总结：

5. 基数排序

假设长度为$n$$n$的线性表中每个结点$a_j$$a_j$的关键字由$d$$d$元组$(k_j^{d-1},k_j^{d-2},k_j^{d-3},\cdots ,k_j^1,k_j^0)$$(k_j^{d-1},k_j^{d-2},k_j^{d-3},\cdots,k_j^{1},k_j^{0})$组成，这里的$k_j^{d-1}$$k^{d-1}_j$表示最高位关键字，$k_j^0$$k^0_j$表示最低位关键字。其中

这里的$r$$r$称为"基数"，即代表最每一位可能出现数字个数，正常数字中每位数组可能为$0\sim 9$$0\sim9$，故基数为$10$$10$。

基数排序得到递减序列的过程如下：

1. 初始化：设置$r$$r$个空队列，$Q_{r-1},Q_{r-2}\cdots Q_0$$Q_{r-1},Q_{r-2}\cdots Q_0$。

2. 按照各个关键字位权重递增的次序(个$>$$>$十$>$$>$百)，对$d$$d$个关键字位分别做"分配"和"收集"。

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

   收集：把$Q_{r-1},Q_{r-2}\cdots Q_0$$Q_{r-1},Q_{r-2}\cdots Q_0$各个队列中的结点依次出队并链接。

基数排序模拟：假设给定以下序列，要求得到关键字递减的有序序列：

上面数组中关键字基数为$r=10$$r=10$，需要建立$10$$10$个辅助队列。

• 第一趟处理：以"个位"进行分配，队列第一个关键字$520$$520$个位是$0$$0$，所以放入$Q_0$$Q_0$队列，后面所有关键字按照个位数$i$$i$的值，依次进入对应的$Q_i$$Q_i$队列。

  

• 之后进行收集工作：将各个队列中的关键字组织成一个统一的链表。由于这里要求得到递减的数列，所以从$Q_9$$Q_9$开始收集。

  

  第一趟"收集"结束：得到按"个位"递减排序的序列。

• 第二趟处理：基于第一趟结果，对"十位"进行分配。第一个关键字$438$$438$十位是$3$$3$，所以会放入$Q_3$$Q_3$队列。后面所有关键字按照个位数$i$$i$的值，依次进入对应的$Q_i$$Q_i$队列。

  

  收集结果如下：

  

  第二趟"收集"结束：得到按"十位"递减排序的序列，"十位"相同的按"个位"递减排序。

• 第三趟处理：以"百位"进行分配。队列第一个关键字是$996$$996$，百位是$9$$9$，所以放入$Q_9$$Q_9$队列中，后面所有关键字按照个位数$i$$i$的值，依次进入对应的$Q_i$$Q_i$队列。

  

  收集结果如下：

  

  第三趟按"百位"分配、收集：得到一个按"百位"递减排列的序列，若"百位"相同则按"十位"递减排列，若"十位"还相同则按"个位"递减排列。

由此可以看出基数排序不是基于"比较"的排序算法。

基数排序实现：基数排序大都基于链式存储结构实现。

xxxxxxxxxx
9
1
typedef struct LinkNode{
2
    ElemType data;
3
    struct LinkNode *next;
4
}LinkNode,*LinkList;
5

6
//队列是链式队列
7
typedef struct{
8
    LinkNode *front,*rear; //队列的队头和队尾指针
9
}LinkQueue; //LinkQueue Q[10]

算法效率分析：

空间复杂度：需要$r$$r$个辅助队列，所以空间复杂度$=O(r)$$=O(r)$。

时间复杂度：一趟分配$O(n)$$O(n)$，一趟收集$O(r)$$O(r)$，总共$d$$d$趟分配、收集，总的时间复杂度$=O(d(n+r))$$=O(d(n+r))$。而收集一个队列只需要$O(1)$$O(1)$时间复杂度。收集队列核心代码如下：

xxxxxxxxxx
4
1
//收集Q5队列
2
p->next = Q[5].front;
3
Q[5].front=NULL;
4
Q[5].rear=NULL;

同时也可以看出基数排序具有稳定性。

基数排序应用：某学校有$10000$$10000$学生，将学生信息按年龄递减排序。生日可拆分为三组关键字：年($1991\sim 2005$$1991\sim2005$)、 月($1\sim 12$$1\sim12$)、 日($1\sim 31$$1\sim31$)。日期权重为$\text{日}<\text{月}<\text{年}$$日<月<年$，所以根据基数排序要按照权重递增次序进行分配收集。

上面例子中基数排序的时间复杂度为：$O(d(n+r))=O(3(10000+31)=O(30000)$$O(d(n+r))=O(3(10000+31)=O(30000)$，这里的$d$$d$是$3$$3$，因为分为三轮(年、月、日)分配收集，$n$$n$是$10000$$10000$，$r=max\{31,12,15\}$$r=\max\{31,12,15\}$。若采用堆排序和快排$O(n{\log }_{2}n)\approx =140000$$O(n\log_2n)\approx=140000$。

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

1. 数据元素的关键字可以方便地拆分为$d$$d$组，且$d$$d$较小。反例：给$5$$5$个人身份证号排序(这里$d=18$$d=18$，而$n=5$$n=5$)
2. 每组关键字的取值范围不大，即$r$$r$较小。反例：给中文名排序(这里$d=2/3/4/$$d=2/3/4/$，但$r=\mathrm{\infty }$$r=\infty$因为姓氏很多)
3. 数据元素个数$n$$n$较大。擅长例子：给十亿人身份证号排序。这里虽然$d=18$$d=18$，但$n=\text{十}\text{亿}$$n=十亿$，此时相对来说仍能得到很高的效率。

基数排序总结：

6. 外部排序

磁盘的读$/$$/$写以"块"为单位，数据读入内存后才能被修改。修改完了还要写回磁盘。

外部排序是指数据元素太多，无法一次全部读入内存进行排序。可以使用归并排序的方法，最少只需在内存中分配$3$$3$块大小的缓冲区即可对任意大的文在进行排序。这里三个缓冲区大小相等。

6.1 外部排序实现

假如在内存中开辟以下三个缓冲区：

同时要排序以下磁盘中的没见，每块大小为$1kb$$1kb$

磁盘中分为$16$$16$块数据。每块中包含$3$$3$个记录关键字。现在要对磁盘中的记录关键字进行递增排序。

• 首先在归并排序开始之前，需要构造一些有序的子序列。首先将内存中前两块的内存读入输入缓冲器$1,2$$1,2$，进行内部排序。

  

  首先将输入缓冲区$1$$1$中关键字放入输出缓冲区

  

  再通过输出缓冲区写回磁盘

  

  之后将输入缓冲区$2$$2$数据放入输出缓冲区，再放回磁盘中。

  

  此时磁盘块前两个空间内的数据有序。这样的有序初试序列称为归并段。同样的将磁盘后面的块进行两两有序的内部排序。

  

  通过这样方式可以得到$8$$8$个初始的归并段。之后可以用这八个归并段进行归并排序。由于磁盘中每块都需要进行读写两次访存，所以$16$$16$块就需要$32$$32$次$\text{读}/\text{写}$$读/写$操作。

• 之后用上面的初始归并段进行排序，首先进行第一趟归并

  

  将两个归并段中更小的归并段先放入缓冲区，之后进行归并排序，排序方法是依次将两个输入缓冲区中最小的放入输出缓冲区。

  

  由于输出缓冲区与两个输入缓冲区大小一致，所以只能放入三个记录关键字，当记录关键字填满了输出缓冲区之后，输出缓冲区会将数据写回磁盘块。

  

  接着继续对输入缓冲区中的记录关键字进行归并，当某一个输出缓冲区空时，需要将对应的归并段下一块补上。

  

  这里将归并段$1$$1$中的第二块放入输入缓冲区$1$$1$。

  

  之后继续归并将关键字填入输出缓冲区，当缓冲区$2$$2$空了，就需要用归并段$2$$2$下一块补齐。

  

  之后继续进行归并，直到两个归并段合并

  

  之后可以用与之上面类似方法对后面三组(每组两个)进行归并。归并后这一趟归并结束，结果如下：

  

  在这一趟归并结束后，可以将$8$$8$个初始的归并段，归并为$4$$4$个。

• 接着进行第二趟归并，将这四个归并段，分别进行两两归并。

  

  之后用归并排序的方法，依次将两个输入缓冲区中更小的记录关键字写入输出缓冲区，同样的当输入缓冲区$i$$i$空时，就需要将归并段$i$$i$内的下一块记录关键字补上。

  

  最后如上图可以将这两个归并段归并为一个。两外一组进行归并方法一样，结果如下：

  

  完成了这一趟的归并后得到两个归并段。

• 最后一趟归并将上面的两个归并段合并为一个。方法与上面一样，经过这一次归并就可以将这一片内存中的$16$$16$块记录关键字变为递增序列。

  

注意：这里每趟归并会开辟一个与两个归并块大小之和的磁盘块，一趟排序结束后之前的磁盘块销毁。且每当输入缓冲区$i$$i$空时，就立即将对应的归并段$i$$i$的下一块记录关键字放入，接着继续进行归并排序。

外部排序时间开销分析如下：

通过上图不难发现外部排序时间开销$=$$=$读写外存的时间$+$$+$内部排序所需时间$+$$+$内部归并所需时间。

上面读写外村时间与读写磁盘次数成正比，上面例子首先初始化归并段读写$32$$32$次，之后需要$3$$3$趟归并排序，每趟都要读写$32$$32$次，总共是$32+32\ast 2=128$$32+32*2=128$次。可以看出读写外存时间占比很大。显然上面文件要排序块数是无法改变的，但是可以通过缩短归并趟数达到优化效果。

6.2 外部排序优化

优化方法是使用多路归并。

这里以四路归并举例，如果是四路归并，就需要在内存中开辟四个输入缓冲区。之后将四个归并段中的内容读入缓冲区。

将四个归并段中第一块记录关键字块放入对应的输入缓冲区。

之后归并方法与上面一致。同样需要注意的是当一个输入缓冲区$i$$i$空时，就需要将对应归并段$i$$i$的下一块记录关键字块补全。

这样在一趟归并完成后就得到两个归并段

之后再需要一趟二路归并即可。

效率分析：

这样采用$4$$4$路归并，只需进行两趟归并即可。读、写磁盘次数$=32+32\ast 2=96$$=32+32*2= 96$次。

重要结论：采用多路归并可以减少归并趙数，从而减少磁盘$I/O$$I/O$(读写)次数。对$r$$r$个初始归并段，做$k$$k$路归并，则归并树可用$k$$k$叉树表示。若树高为$h$$h$，则归并趟数$=h-1=\lceil {\log }_{k}r\rceil$$=h-1=\lceil\log_kr\rceil$。

推导：$k$$k$叉树第$h$$h$层最多有$k^{h-1}$$k^{h-1}$个结点，则$r\le k^{h-1}$$r\le k^{h-1}$，$(h-1{)}_{\text{最}\text{小}}=\lceil {\log }_{k}r\rceil$$(h-1)_{最小}=\lceil\log_kr\rceil$。所以说$k$$k$越大，$r$$r$越小，归并趟数越少，读写，磁盘次数越少。

当然也不并不是$k$$k$路归并的$k$$k$越大越好，$k$$k$路归并带来的负面影响：

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

除了增加$k$$k$，还可以减少$r$$r$初始段数量。所以若能增加初始归并段的长度(输入缓冲区个数)，则可减少初始归并段数量。即$k$$k$越大，$r$$r$越小，归并趟数越少，读写，磁盘次数越少。

外部排序总结：

注：按照本节介绍的方法生成的初始归并段，若共$N$$N$个记录，内存工作区可以容纳$L$$L$个记录，则初始归并段数量$r=N/L$$r= N/L$。可以通过败者树，减少关键字对比次数，并减少$k$$k$路归并时$k$$k$太大造成影响。另外可以通过置换$-$$-$选择排序进一步减少初始归并段的数量。

这里补充$k$$k$路平衡归并，满足$k$$k$路平衡归并条件如下：

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

如上图仅仅是四路归并树，而不是四路平衡归并树。因为第一趟$8$$8$个归并段经过一趟处理后得到$3$$3$个新的归并段，而对于四路平衡归并树来说如果一趟有$8$$8$个归并段参与的话就是$\lceil 8/4\rceil =2\ne 3$$\lceil 8/4\rceil=2\ne3$。四路平衡归并树如下：

6.3 败者树

上面外部排序优化可以得出增加$k$$k$，可以提高外部排序效率，但是会增加对比次数，所以本节的败者树可以从$k$$k$个归并段中挑出最小关键字对比次数更少。

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

败者树在多路平衡归并中的应用：

有如上图所示的八个归并段。要从这八个归并段中每次选出最小的记录关键字。传统方式，每次都需要进行七次对比才能得到一个最小关键字，而采用败者树方式如下：

将每个归并段的第一个元素放入叶子结点。接着就需要构造一棵败者树。构造方法是：每次底部两个叶子结点进行对比，较小的晋级到父结点，但是这里晋级到父结点后并不是记录这个关键字的值，而是记录更小关键字来自哪个归并段。

第一趟对比如下：

结果是归并段$3$$3$中的记录关键字$1$$1$最小。

第二趟将归并段$3$$3$中记录关键字$6$$6$补齐叶子结点：

之后$6$$6$会和父结点进行对比，依次晋级。先和父结点$4$$4$(表示归并段$4$$4$中的记录关键字$17$$17$)对比，显然更小晋级，和归并段$2$$2$关键字$12$$12$对比，胜出。最后和归并段$5$$5$关键字$2$$2$对比，失败，受的败者树如下：

本轮关键字归并段$5$$5$中的关键字$2$$2$最小，所以胜出。本次对比进行三次。

之后归并段$5$$5$关键字$3$$3$补齐叶子结点，继续进行上述对比即可

结论：对于$k$$k$路归并，第一次构造败者树需要对比关键字$k-1$$k-1$次。有了败者树，选出最小元素，只需要对比关键字$\lceil {\log }_{2}k\rceil$$\lceil\log_2k\rceil$次即可。

代码实现：

八路归并情况下只需要对应一个长度为$8$$8$的数组，数组下标为$1$$1$对应上面败者树传统根节点，$0$$0$号数组下标对应冠军结点。这里要注意上面的叶子结点是虚拟结点，实际结构中不存在的。

总结：败者树解决的问题是使用多路平衡归并可减少归并趟数，但是用老土方法从$k$$k$个归并段选出一个最小$/$$/$最大元素需要对比关键字$k-1$$k-1$次，构造败者树可以使关键字对比次数减少到$\lceil {\log }_{2}k\rceil$$\lceil\log_2k\rceil$。

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

上图归并段有$5$$5$个，所以数组长度是$ls[5]$$ls[5]$。$1\sim 4$$1\sim4$对应的是失败者结点，而$0$$0$号对应的是胜利者结点。而对于下面的归并段的编号是$b0\sim b1$$b0\sim b1$。上面败者树对应的$ls$$ls$数组如下：

上面败者树建立后，后序选出一个更小关键字最多只需要$\lceil {\log }_{2}k\rceil =3$$\lceil\log_2k\rceil=3$次。也有可能是两次，因为可以新填补的元素是在$b0、b1、b2$$b0、b1、b2$三个结点上。

6.4 置换-选择排序

之前讲过进行$k$$k$路归并时需要$S$$S$趟，$S=\lceil {\log }_{k}r\rceil$$S=\lceil\log_kr\rceil$，如果能让初始归并的段变少，即让$r$$r$减少，则外部排序效率可以进一步提升。可以用置换-选择排序进一步减少初始归并段数量。

实现原理：在用于内部排序的内存工作区中，可以容纳$l$$l$（之前的例子都是对应$3$$3$个记录关键字）个记录，则每个初始归并段也只能包含$l$$l$个记录，若文件共有$n$$n$个记录，则初始归并段的数量$r=n/l$$r=n/l$。可以用置换-选择排序扩大内存工作区。

设初始待排文件为$FI$$FI$，初始归并段输出文件为$FO$$FO$，内存工作区为$WA$$WA$，$FO$$FO$和$WA$$WA$的初始状态为空，$WA$$WA$可容纳$w$$w$个记录。置换选择算法的步骤如下：

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

实现模拟：假设有以下待排序文件：

这里假设用于内部排序的内存工作区只能容纳$3$$3$个记录。按照递增顺序排序：

• 首先将待排序文件数据中三个记录关键字放入$WA$$WA$中

  

• 选择最小的$4$$4$置换出去，放到初始归并段输出文件$FO$$FO$中，$MINIMAX=4$$MINIMAX=4$变为当前输出值。

  

  之后依次将$FI$$FI$放入$WA$$WA$并置换出最小的关键字放入$FO$$FO$中，修改$MINIMAX$$MINIMAX$值为每次置换出去的值。

  

  直到当前记录关键字$10$$10$放入内存工作区中，但是此时$10<MINIMAX=13$$10<MINIMAX=13$，所以关键字$10$$10$不可能输出，标记为红色。

  

• 之后继续置换，直到内存工作区$WA$$WA$中三个关键字全部标记为红色，此时归并段$1$$1$置换结束。

  

  第二个归并段，恢复$WA$$WA$中标记为红色的文件，继续按照第一趟归并步骤，每次将内存工作区$WA$$WA$中比$MINIMAX$$MINIMAX$小的关键字置换出去。

  

  此时$WA$$WA$全部为红色关键字，归并段$2$$2$置换结束。

• 归并段$3$$3$置换步骤同上，结果如下：

  

可以看到上个例子中得到的三个初始归并段可以超过内存工作区的限制。每个归并段所包含的关键字越多，$r$$r$值越小，外部排序归并效率越高。

注意：这里的输出文件$FO$$FO$是存方在磁盘中的，真正的执行是内存工作区$WA$$WA$和$FO$$FO$之间会有输出缓冲区，当输出缓冲区满了之后才会将置换的关键字全部放入$FO$$FO$中。同样的初始待排序文件$FI$$FI$输入到内存工作$WA$$WA$过程也是一样。

6.5 最佳归并树

上面的学习可以知道如果使用置换-选择排序构造初始归并段，这些初始的归并段长度可能各不相同。

下面有一个初始归并段：

这里$R_1$$R_1$表示使用置换-选择排序构造初始归并段后需要$2$$2$个磁盘块，对应的$R_2$$R_2$归并段需要$5$$5$个磁盘块。可以看出各个初始归并段之间的差异很大。

上面初始归并段中，如果$R_2$$R_2$和$R_3$$R_3$合并，需要读$/$$/$写磁盘次数为$5+1=6$$5+1=6$次。之后构造一棵二叉归并树如下：

这颗归并树的读$/$$/$写次数为$6+8+14+16=44$$6+8+14+16=44$次。而$WPL=2\times 1+(5+1+6+2)\times 3=44$$WPL=2\times1 + (5+1+6+2)\times3= 44$，也是$44$$44$。这里$WPL$$WPL$指叶子结点权值到根节点路径长度，上面$5$$5$到根节点$16$$16$长度是$3$$3$，所以是$5\times 3$$5\times3$。

可以得出一个重要结论：归并过程中的磁盘$I/O$$I/O$次数$=$$=$归并树的$WPL\ast 2$$WPL * 2$。可以想到如果想构造一棵$I/O$$I/O$次数少，即$WPL$$WPL$长度短的树，可以构造一棵哈夫曼树。上面初始归并段构造成哈夫曼树如下：

最佳归并树$WP{L}_{min}=(1+2)\times 4+2\times 3+5\times 2+6\times 1=34$$WPL_{\min}=(1+2)\times4+2\times3+5\times2+6\times1=34$。故读磁盘次数$=$$=$写磁盘次数$=34$$=34$次。总的磁盘$I/O$$I/O$次数$=68$$=68$。

上面是二路归并情况，以下是多路归并：

上面初始归并段含义同上。假设现在要采用$3$$3$路归并策略，按照之前传统的方法归并结果如下：

这个归并树的$WPL=(9+30+12+18+3+17+2+6+24)\times 2=242$$WPL=(9+30+12+18+3+17+2+6+24)\times2=242$，归并过程中磁盘$I/O$$I/O$总次数$=484$$=484$次。

显然这不是最佳归并树，三路归并树构造和二路类似：每次选出三个权值最小的结点构造成树即可。上面出时段构造哈夫曼树如下：

归并树$WP{L}_{min}=(2+3+6)\times 3+(9+12+17+24+18)\times 2+30\times 1=223$$WPL_{\min}=(2+3+6)\times3+(9+12+17+24+18)\times2+30\times1=223$。归并过程中磁盘$I/O$$I/O$总次数$=446$$=446$次。

但是如果减少一个归并段，即有$8$$8$个归并段构造三路归并树，最后会进行一次二路归并，这显然违反哈夫曼树定义，所以是不正确的构造方法，解决方法是再添加一个权值为$0$$0$的归并段即可。

构造成$3$$3$路哈夫曼树如下：

这棵树的$WP{L}_{min}=(2+3+0)\times 3+(6+9+12+17+18)\times 2+24\times 1=163$$WPL_{\min}=(2+3+0)\times3+(6+9+12+17+18)\times2+24\times1=163$。归并过程中磁盘$I/O$$I/O$总次数$=326$$=326$次。

结论：对于$k$$k$(大部分情况下是$k>2$$k>2$)叉归并，若初始归并段的数量无法构成严格的$k$$k$叉归并树，则需要补充几个长度为$0$$0$的"虚段"，再进行$k$$k$叉哈夫曼树的构造。

这里的虚段本质是，三个输入缓冲区中一个为$NULL$$NULL$即代表虚段。

再接着深入分析：$k$$k$叉的最佳归并树一定是一棵严格的$k$$k$叉树，即树中只包含度为$k$$k$、度为$0$$0$的结点。设度为$k$$k$的结点有$n_k$$n_k$个，度为$0$$0$的结点有$n_0$$n_0$个，归并树总结点数$=n$$=n$，则$\text{初}\text{始}\text{归}\text{并}\text{段}\text{数}\text{量}+\text{虚}\text{段}\text{数}\text{量}=n_0$$初始归并段数量+虚段数量=n_0$。

另外根据$k$$k$叉树性质：$n=n_0+n_k;k·n_k=n-1$$n=n_0+n_k;k·n_k=n-1$。这里$k·n_k$$k·n_k$是分分叉总数量，等于总结点树减去一个根结点。从而可知$n_0=(k-1)n_k+1⟹n_k=\frac{(n_0-1)}{(k-1)}$$n_0=(k-1)n_k+1\Longrightarrow n_k=\frac{(n_0-1)}{(k-1)}$，所以说如果是"严格$k$$k$叉树"，一定能除得尽。

所以，判断初始段序列是否需要添加虚段方式：

1. 若$(\text{初}\text{始}\text{归}\text{并}\text{段}\text{数}\text{量}-1)\mathrm{\%}(k-1)=0$$(初始归并段数量-1)\%(k-1)=0$，说明刚好可以构成严格$k$$k$叉树，此时不需要添加虚段。
2. 若$(\text{初}\text{始}\text{归}\text{并}\text{段}\text{数}\text{量}-1)\mathrm{\%}(k-1)=u\ne 0$$(初始归并段数量-1)\%(k-1)=u\ne0$，则需要补充$(k-1)-u$$(k-1)-u$个虚段即可。

$\text{例}:$$\Large 例:$假设现在需要进行$8$$8$路归并，如果初始归并段数量$=19$$=19$，需要添加几个虚段？

最佳归并树总结：