[数据结构与算法]数据结构笔记（王道考研） 第八章：排序

大部分内容基于中国大学MOOC的2021考研数据结构课程所做的笔记，该课属于付费课程（不过盗版网盘资源也不难找。。。）。后续又根据23年考研的大纲对内容做了一些调整，将二叉排序树和平衡二叉树的内容挪到了查找一章，并增加了并查集、平衡二叉树的删除、红黑树的内容。

排序一章的各种算法动态过程比较难以展现，所以阅读体验可能不是特别好。

西电的校内考试分机试和笔试。笔试占50分，机试2小时4道题占30分，做出2道满分，多做一道总分加5分。机试尽量把老师平时发的OJ题目都过一遍。笔试内容偏基础，但考的量比较大。

?

其他各章节的链接如下：

数据结构笔记（王道考研） 第一章：绪论

数据结构笔记（王道考研） 第二章：线性表

数据结构笔记（王道考研） 第三章：栈和队列

数据结构笔记（王道考研） 第四章：串

数据结构笔记（王道考研） 第五章：树和二叉树

数据结构笔记（王道考研） 第六章：图

数据结构笔记（王道考研） 第七章：查找

数据结构笔记（王道考研） 第八章：排序

其他各科笔记汇总

排序

排序的基本概念

什么是排序

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

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

输出：输入序列的一个重排$R_1^{\prime },R_2^{\prime },...,R_n^{\prime }$,使得有$k_1^{\prime }\le k_2^{\prime }\le ...\le k_n^{\prime }$（也可递减）

排序算法的评价指标

1.时间复杂度，空间复杂度

2.稳定性

若待排序表中有两个元素$R_i$和$R_j$，其对应的关键字相同即$ke{y}_i=ke{y}_j$，且在排序前$R_i$在$R_j$的前面，若使用某一排序算法排序后，$R_i$仍然在$R_j$的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。

排序的分类

排序算法可以分为

1.内部排序——数据都在内存中

2.外部排序——数据太多，无法全部放入内存

之所以有这种分类是因为磁盘的容量一般远大于内存，而运算速度又远不如内存。因此排序算法不仅要关注时间和空间复杂度，有时考虑到内存容量的问题还要关注如何使读/写磁盘次数更少

插入排序

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

算法实现

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

算法实现（带哨兵）

//直接插入排序(带哨兵)
void InsertSort(int 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];               //复制到插入位置
        }
}

优点：不用每轮循环都判断 $j\ge 0$

算法效率分析

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

只需要定义几个所需空间为常数级的辅助变量（如 $i，j，temp，a[0]$），与问题的规模$n$无关

?

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

下面的分析以带哨兵的版本为基础

?

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

共$n?1$趟处理，每一趟只需要对比关键字1次，不用移动元素

?

最坏情况：原本为逆序，$O(n^2)$

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

第二趟：对比关键字3次，移动元素4次

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

…

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

?

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

?

3.稳定性：稳定

优化 —— 折半插入排序

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

当$low>high$时折半查找停止，应将$[low,i?1]$内的元素全部右移，并将$A[0]$复制到$low$所指位置

如果$low>i?1$，则什么都不做

当$A[mid]==A[0]$时，为了保证算法的“稳定性”，应继续在$mid$所指位置右边寻找插入位置

?

//折半插入排序
void InsertSort(int 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(n^2)$

对链表进行插入排序

移动元素的次数变少了，但是关键字对比的次数依然是$O(n^2)$数量级，整体来看时间复杂度依然是$O(n^2)$

希尔排序（Shell Sort）

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

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

一般第一趟排序时设置增量$d=n/2$，每一趟排序后将增量缩小一半

算法实现

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

$i++$会切换着处理每个子表

算法性能分析

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

?

2.时间复杂度：和增量序列$d_1,d_2,d_3...$的选择有关，目前无法用数学手段证明确切的时间复杂度。最坏时间复杂度为$O(n^2)$，当n在某个范围内时，可达$O(n^{1.3})$

?

3.稳定性：不稳定

4.适用性：仅适用于顺序表，不适用于链表

冒泡排序

冒泡排序和快速排序是基于“交换”的排序

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

?

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

第1趟排序使关键字值最小的1个元素“冒”到最前面

前边已经确定最终位置的元素不用再对比

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

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

…

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

算法实现

//交换
void swap(int &a,int&b){
    int temp=a;
    a=b;
    b=temp;
}

//冒泡排序
void BubbleSort(int A[],int n){
    for(int i=0;i<n-1;i++){            
        bool 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==false)
            return;                    //本趟遍历后没有发生交换，说明表已经有序
    }
}

算法性能分析

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

2.时间复杂度：

最好情况（有序）

比较次数$=n?1$；交换次数$=0$

最好时间复杂度$=O(n)$

?

最坏情况（逆序）

比较次数$=(n?1)+(n?2)+...+1=n(n?1)2=$交换次数

每次交换都需要移动元素3次

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

?

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

?

3.稳定性：只有$A[j?1]>A[j]$时才交换，因此算法是稳定的

是否适用于链表？

可从前往后“冒泡”，每一趟将更大的元素“冒’'到链尾

快速排序

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

算法实现

//快速排序
void QuickSort(int A[],int low,int high){
    if(low<high){   //递归跳出的条件
        int pivotpos=Partition(A,low,high); //划分
        QuickSort(A,low,pivotpos-1);        //划分左子表
        QuickSort(A,pivotpos+1,high);       //划分右子表
    }
}

//用第一个元素将待排序序列划分为左右两个部分
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;             //返回存放枢轴的最终位置
}

算法效率分析

?

?

?

?

?

?

?

1.时间复杂度$=O(n\times$递归层数$)$

最好时间复杂度：$O(nlo{g}_{2}n)$

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

平均时间复杂度：$O(nlo{g}_{2}n)$

?

2.空间复杂度$=O($递归深度$)$

最好时间复杂度：$O(lo{g}_{2}n)$

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

?

若每次选中的“枢轴”将待排序序列划分为均匀的两个部分，则递归深度最小，算法效率最高

若每次选中的“枢轴”将待排序序列划分为很不均匀的两个部分，则会导致递归深度增加，算法效率变低

若初始序列有序或逆序，则快速排序的性能最差（因为每次选择的都是最靠边的元素）

?

快速排序算法优化思路：尽量选择可以把数据中分的枢轴元素

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

?

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

?

?

3.稳定性：不稳定

简单选择排序

简单选择排序和堆排序都属于选择排序

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

?

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

最后剩一个不用再处理

算法实现

//交换
void swap(int &a,int&b){
    int temp=a;
    a=b;
    b=temp;
}

//简单选择排序
void SelectSort(int A[],int n){
    for(int i=0;i<n-1;i++){            //一共进行n-1趟
        int min=i;                     //记录最小元素位置
        for(int 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次
    }
}

算法性能分析

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

?

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

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

总共需要对比关键字$(n?1)+(n?2)+...+1=\frac{n(n?1)}{2}$次

元素交换次数$<n?1$

?

3.稳定性：不稳定

4.适用性：既可以用于顺序表，也可以用于链表

堆排序

堆的定义

若$n$个关键字序列$L[\mathrm{1..}n]$满足下面某一条性质，则称为堆（$Heap$）

1.若满足：$L(i)\ge L(2i)$且$L(i)\ge L(2i+1)(1\le i\le n/2)$ ——大根堆（大顶堆）

2.若满足：$L(i)\le L(2i)$且$L(i)\le L(2i+1)(1\le i\le n/2)$ ——小根堆（小顶堆）

回顾之前二叉树顺序存储的知识，大根堆在逻辑视角上可以看成所有子树根$\ge$左、右的完全二叉树。堆排序就建立在堆顶元素关键字最大上

相应的小根堆也可以看成根$\le$左，右的完全二叉树

建立大根堆

大根堆：根$\ge$左，右

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

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

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

在顺序存储的完全二叉树中，非终端结点编号$i\le [n/2]$

$i$的左孩子 —— $2i$

$i$的右孩子 —— $2i+1$

$i$的父节点 —— $[i/2]$

?

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

//将以 k 为根的子树调整为大根堆
void HeadAdjust(int A[],int k,int len){
    A[0]=A[k];                     //A[0]暂存子树的根结点
    for(int 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]                      //将被筛选结点的值放入最终位置
}

基于大根堆进行排序

堆排序：每一趟将堆顶元素加入有序子序列（与待排序序列中的最后一个元素交换）

并将待排序元素序列再次调整为大根堆（小元素不断“下坠”）

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

?

代码如下

//建立大根堆
void BuildMaxHeap(int A[],int len)
    
//将以k为根的子树调整为大根堆
void HeadAdjust(int A[],int k,int len)
    
//堆排序的完整逻辑
void HeapSort(int A[],int len){
    BuildMaxHeap(A,len);         //初始建堆
    for(int i=len;i>1;i--){      //n-1趟的交换和建堆过程     
        swap(A[i],A[1]);         //堆顶元素和堆底元素交换
        HeadAdjust(A,1,i-1);     //把剩余的待排序元素整理成堆
    }
}

算法效率分析

堆排序的空间复杂度$=O(1)$

?

?

下方有两个孩子，则“下坠”一层，需对比关键字2次。下方只有一个孩子，则下坠一层，只需对比关键字1次。故一个结点，每“下坠”一层，最多只需对比关键字2次

若树高为$h$，某结点在第$i$层，则将这个结点向下调整最多只需要“下坠”$h?i$层，关键字对比次数不超过$2(h?i)$，$n$个结点的完全二叉树高$h=[lo{g}_{2}n]+1$

?

第$i$层最多有$2^{i?1}$个结点，而只有第$1～(h?1)$层的结点才有可能需要“下坠”调整

将整棵树调整为大根堆，关键字对比次数不超过${\sum }_{i=h?1}^1{2}^{i?1}2(h?i)={\sum }_{i=h?1}^1{2}^i(h?i)={\sum }_{j=1}^{h?1}{2}^{h?j}j\le 2n{\sum }_{j=1}^{h?1}\frac{j}{2^j}\le 4n$

${\sum }_{j=1}^{h?1}\frac{j}{2^j}$差比数列求和（错位相减法），求和结果小于2

?

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

?

?

初始建堆时间复杂度为$O(n)$

每趟交换和建堆过程，根节点最多“下坠”$h?1$层，每下坠一层最多只需对比关键字2次，因此每一趟排序时间复杂度不超过$O(h)=O(lo{g}_{2}n)$。共$n?1$趟，总的时间复杂度$=O(lo{g}_{2}n)$

堆排序的时间复杂度$=O(n)+O(nlo{g}_{2}n)=O(nlo{g}_{2}n)$

?

?

堆排序是不稳定的

堆的插入删除

在堆中插入新元素

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

在堆中删除元素

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

归并排序（Merge Sort）

?

Merge（归并/合并）

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

“2路”归并 —— 每选出一个小元素就需对比关键字1次。“4路”归并 —— 每选出一个小元素就需对比关键字3次。故$m$路归并，每选出一个元素需要对比关键字$m?1$次

归并排序（手算模拟）

在内部排序中一般采用2路归并

核心操作：把数组内的两个有序序列归并为一个

代码实现

int *B=(int *)malloc(n*sizeof(int)); //辅助数组B

//A[low...mid]和A[mid+1...high]各自有序，将两个部分归并
void Merge(int A[],int low,int mid,int high){
    int i,j,k;
    for(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])    
            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++];
}

void MergeSort(int A[],int low,int high){
    if(low<high){
        int mid=(low+high)/2;     //从中间划分
        MergeSort(A,low,mid);     //对左半部分归并排序
        MergeSort(A,mid+1，high); //对右半部分归并排序
        Merge(A,low,mid,high);    //归并
    }//if
}

算法效率分析

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

二叉树的第$h$层最多有$2h?1$个结点

若树高为h，则应满足$n\le 2h?1$

即$h?1=[log2n]$

结论：$n$个元素进行2路归并排序，归并趟数$=[lo{g}_{2}n]$

每趟归并时间复杂度为$O(n)$,则算法时间复杂度为$O(nlo{g}_{2}n)$

?

空间复杂度$=O(n)$，来自于辅助数组B

?

两个元素相等时，优先使用靠前的那个。归并排序是稳定的

基数排序（Radix Sort）

基数排序

?

?

?

?

?

?

?

?

?

?

?

假设长度为$n$的线性表中每个结点$a_j$的关键字由$d$元组（$k_j^{d?1},k_j^{d?2},...,k_j^1,k_j^0$）组成。其中，$0\le k_j^i\le r?1(0\le j\le n,0\le i\le d?1)$，$r$称为“基数”

$k_j^{d?1}$为最高位关键字（最主位关键字），$k_j^0$为最低位关键字（最次位关键字）

?

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

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

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

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

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

可见基数排序不是基于“比较”的排序算法

?

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

初始化：设置$r$个空队列，$Q_0,Q_1,...,Q_{r?1}$

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

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

收集：把$Q_0,Q_1,...,Q_{r?1}$各个队列中的结点依次出队并链接

算法效率分析

基数排序通常基于链式存储实现

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode, *LinkList;

typedef struct{              //链式队列
    LinkNode *front,*rear;   //队列的对头和队尾指针
}LinkQueue;

一般不太考察基数排序的代码实现

?

1.空间复杂度

需要$r$个辅助队列，空间复杂度$O(r)$

?

2.时间复杂度：

把关键字拆为$d$个部分，每个部分可能取得$r$个值

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

收集一个队列只需$O(1)$时间

p->next = Q[6].front;
Q[6].front = NULL;
Q[6].rear = NULL;

?

3.稳定性：稳定的

基数排序的应用

外部排序

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

外部排序原理

构建初始”归并段“

归并过程

第一趟归并：把8个有序子序列（初始归并段）两两归并

?

第二趟归并：把4个有序子序列（归并段）两两归并

归并之后得到的更长子序列放在磁盘的另一片空间当中，以前的这两片空间会归还给系统，这里只是为了美观

?

第三趟归并：将2个有序子序列（归并段）归并

经过3趟归并，整体有序

时间开销分析

优化

1.多路归并

$[lo{g}_{k}r]$向上取整

2.减少初始归并段数量

什么是多路平衡归并？

$[m/k]$向上取整

败者树

败者树的构造

败者树的使用

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

$[lo{g}_{2}k]$向上取整

败者树的实现思路

置换-选择排序

?

?

上面的演示每次读写一个记录，忽略了输出缓冲区和输入缓冲区

最佳归并树

归并树的性质

构造2路归并的最佳归并树

多路归并的情况

?

添加虚段的数量