数据结构--第八章排序

标签：归并排序 -- 复杂度元素结点第八章 int 数据结构

注：内容参考王道2024考研复习指导以及《数据结构》

一、排序的基本概念

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

排序算法的评价指标

时间复杂度
空间复杂度
稳定性

算法的稳定性，若待排序表中有两个元素Ri和Rj，其对应的关键字相同即keyi=keyj ，且在排序前R Ri在Rjj的前面，若使用某⼀排序算法排序后，Ri仍然在Rj的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。

排序算法的分类

内部排序，数据都在内存中，关注如何使算法的时、空间复杂度更低。
外部排序，数据太多，无法全部放入内存，还要关注如何使读/写磁盘次数更少。

注：！！！！！！！！！！！！！

进行基于比较的排序，至少要进行log2 n!次比较。

解释：n个数组成的不同排列方式有n！个。已经排好序的数列(假设是从小到大排列)是这n ! n!n!个序列中的一个，排序所作的就是找出这个序列。

设这数列中有两个数 a ,b。这n!种排列组合中a在b前和a在b后的机会是均等的。

比较一次a,b的大小（不妨假设a<b），那么所有 a排在b后的情况都是不符合从小到大的要求的。这样我们将n!个可能的情况剔除了一半。

重复以上步骤，理想状态下，每比较一次都可以排除一半的情况。

二、内部排序

1.插入排序

①.直接插入排序

算法思想

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

算法实现（无哨兵）

//直接插入排序
void InsertSort(int A[],int n){
    int i,j,temp;
    for(i=1;i<n;i++){//从第二个元素开始，进行排序
        if(A[i]<A[i-1]){//如果当前元素比前驱元素小，进行插入操作
            temp=A[i];
            for(j=i-1;j>=0 && A[j]>temp;j--){//从当前元素前驱元素开始，向前寻找，直到找到不大于当前元素的值，停止
                A[j+1]=A[j];//每往前寻找一个，进行交换
            }
            A[j+1]=temp;//插入找到的位置
        }
    }
}

算法实现（带哨兵）

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

自己理解：带哨兵的方式中，选择第0个位置为空，用于存放插入元素的值（方便比较），如果插入元素比其前驱元素大或者相等，直接插入了；如果插入元素比其前驱元素小，则一直从后往前比较，直至A[0]与并不小于比较的元素，此时将相比较的哪个元素后面的值全部后移，再插入元素。

算法效率分析

空间复杂度：O (1)

时间复杂度：主要来自对比关键、移动元素，若有n个元素，则需要对比n-1趟处理。则最好时间复杂度(全部有序)O(n)；最坏时间复杂度(全部逆序):O(n^2)；平均时间复杂度:O(n^2)

算法稳定性：稳定

适用性：直接插入排序适用于顺序存储和链式存储的线性表，采用链式存储时无需移动元素。

对链表进行插入排序

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

②.折半插入排序

思路：先用折半查找找到应该插入的位置，再移动元素。相当于直接插入排序的优化。

void InsertSort(int A[],int n){
    int i,j,low,mid,high;
    for(i=2;i<=n;i++){//A[0]位置作为哨兵，A[1]位置不需要排序
        A[0]=A[i];
        low=1;high=i-1;
        while(low<=high){
            mid=(low+high)/2;
            if(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];
    }
}

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

当 A[mid]==A[0]时，为了保证算法的“稳定性”，应继续在mid所指位置右边寻找插⼊位置。（停止条件是low>high，！！！！！！！！！即使查找到了对应的位置，也需要满足此条件，否则就继续砍半）

自己的理解：有序表两端有两个指针low与high，将有序的序列砍成两半查看其中间元素(向上取整或向下取整都可)，然后比较中间元素的值与要插入元素的值（不相等时同时去除此中间元素），在哪个范围，哪个范围就再砍一半，如此循环，直到low>high时折半查找停止。

性能分析

折半插入排序每趟的比较次数都为O(log2 m)，m为当前已经排好序的子序列的长度。

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

折半插入排序仅适用于顺序存储的线性表。

③.希尔排序

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

算法实现

void ShellSort(int A[],int n){
    int d,i,j;
    for(d=n/2;d>=1;d=d/2){
        for(i=d+1;i<=n;i++){//A[0]是暂存单元，不是哨兵
            if(A[i]<A[i-d]){
                A[0]=A[i];
                for(j=i-d;j>0 && A[0]<A[j];j-=d){
                    A[j+d]=A[j];
                }
                A[j+d]=A[0];
            }
        }
    }
}

自己的理解：一般来讲就是比如有8个数据（相同颜色为一组）
第一次d为8/2=4 0 1 2 3 4 5 6 7 其中i+d相同的为一组，组内直接插入排序
第二次d为4/2=2 0 1 2 3 4 5 6 7 同理
第三次d为2/2=1 0 1 2 3 4 5 6 7 同理

算法性能分析

空间复杂度:O(1)

时间复杂度：和增量序列d1,d2,d3...dn的选择有关，最坏时间复杂度为O(n^2)，当n在某个范围内时，最好时间复杂度可O(n^1.3).

稳定性：不稳定。

适用性：仅适用于顺序存储的线性表，不适用于链表

2.交换排序

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

①.冒泡排序

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

每一趟都会确定一个最小（或最大）的元素的位置。

算法实现

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 ;
    }
}

算法性能分析

空间复杂度：O(1)

时间复杂度：最好情况(有序)为O(n)；最坏情况(逆序)为 O(n^2)；平均时间复杂度为 O(n^2)。

适用性：冒泡排序适用于顺序存储和链式存储的线性表。

注：！！！！！！！！！
冒泡排序中所产生的有序子序列一定是全局有序的；每趟排序都会将一个元素放置到其最终的位置上。

②.快速排序

基于分冶法

在待排序表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)上，这个过程称为⼀次“划分”。（相当于一部分元素全部大于枢轴，另一部分全部小于枢轴）

然后分别递归地对两个子表重复上述过程，直⾄每部分内只有⼀个元素或空为止，即所有元素放在了其最终位置上。

算法实现

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 pivotpos=Parition(A,low,high);
        QuickSort(A,low,pivotpos-1);
        QuickSort(A,pivotpos+1,high);
    }
}

自己的理解：手算相当于取了两个指针i，j分别置于线性表的两端。开始时将第一个元素取走作为了枢轴，所以i指向位置为空，那么j就一直左移直到找到一个数比枢轴还小，将此数放置j处；同时j指向为空，则i右移，直至找到比枢轴还大的数，将其放置j处，如此循环直至i与j指向同一个位置（为空），然后把枢轴元素放入。（相当于i，j哪个为空就移动另一个）

算法性能分析

把n个元素组织成二叉树，二叉树的层数就是递归调用的层数，
n个结点的二叉树最小高度=⌊log2 n⌋+1，最大高度=n。

时间复杂度：相当于O(n*递归层数)，最坏情况下为O(n^2)，最好情况下为O(n*log2 n)。(其与划分是否对称有关)

空间复杂度：相当于O(递归层数)，最好情况为O(log2 n)，最坏情况为O(n),平均情况为O(log2 n)。（其空间复杂度与递归调用栈有关）

稳定性：不稳定

适用性：快速排序仅适用于顺序存储的线性表。

注：408原题中说，对所有尚未确定最终位置的所有元素进⾏⼀遍处理称为“⼀趟”排序，因此⼀次“划分”≠⼀趟排序。⼀次划分可以确定⼀个元素的最终位置，⽽⼀趟排序也许可以确定多个元素的最终位置。上图一层QuickSort对应一趟排序。

4.选择排序

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

①.简单选择排序

每次从未排序的记录中选择最小的关键字，将其放到排好序的记录尾部。

算法实现

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]);
        }
    }
}

自己的理解：就是在无序序列中选择最小或最大的值放入有序的序列中

算法性能分析

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

空间复杂度：O(1)

稳定性：不稳定

适用性：简单选择排序适用于顺序存储和链式存储的线性表，以及关键字较少的情况。

②.堆排序

堆排序是完全二叉树，但不是排序二叉树，其只有根与孩子之间有大小关系。

若n个关键字序列L[1…n] 满⾜下面某⼀条性质，则称为堆（Heap）：

若满足：L(i)≥L(2i)且L(i)≥L(2i+1) （1 ≤ i ≤n/2 ）—— 大根堆（大顶堆），即二叉树的左、右结点都不大于根结点
若满足：L(i)≤L(2i)且L(i)≤L(2i+1) （1 ≤ i ≤n/2 ）—— 小根堆（小顶堆），即二叉树的左、右结点都不小于根结点

基于“堆”进行排序

1）先建立大顶堆

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

在顺序存储的完全⼆叉树中，非终端结点编号 i≤⌊n/2⌋
检查当前结点是否满足根≥左、右，若不满足，将当前结点与更大的⼀个孩子互换。
若元素互换破坏了下⼀级的堆，则采用相同的方法继续往下调整（小元素不断“下坠”）。

代码实现

//建立大顶堆
void BuildMaxHeap(int A[],int len){
    for(int i=len/2;i>0;i--){
        HeadAdjust(A,i,len);
    }
}

void HeadAdjust(int A[],int k,int len){
    A[0]=A[k];
    for(int i=2*k;i<=len;i*=2){
        if(i<len && A[i]<A[i+1]){
            i++;
        }
        if(A[0]>=A[i])	break;
        else{
            A[k]=A[i];
            k=i;
        }
    }
    A[k]=A[0];
}

2）基于大顶堆进行排序

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

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

堆排序的完整逻辑

void HeapSort(int A[],int len){
    BuildMaxHeap(A,len);
    for(int i=len;i>1;i--){
        swap(A[i],A[1]);
        HeadAjust(A,1,i-1);
    }
}

算法效率分析

结论：⼀个结点，每“下坠”⼀层，最多只需对比关键字2次。
若树高为h，某结点在第 i 层，则将这个结点向下调整最多只需要“下坠” h-i 层，关键字对比次数不超过 2(h-i)，n个结点的完全二叉树树高h = ⌊ log 2 n ⌋ + 1。
第 i 层最多有 2i−1 个结点，而只有第 1 ~ (h-1) 层的结点才有可能需要“下坠”调整，将整棵树调整为大根堆，关键字对比次数不超过$$\sum_{i=h-1}^{1}{2^{i-1}} 2(h-i)<=4n$$，则建堆的过程，关键字对比次数不超过4n，建堆时间复杂度O(n)。

根节点最多“下坠” h-1 层，每下坠⼀层，⽽每“下坠”⼀层，最多只需对比关键字2次，因此每⼀趟排序复杂度不超过 O(log2 n)，共n-1 趟，总的时间复杂度= O ( n log ⁡ 2 n ) 。

综上，时间复杂度O(n*log2 n)，空间复杂度O(1)

稳定性：不稳定

适用性：堆排序仅适用于顺序存储的线性表

堆排序的插入与删除

1）堆中插入新元素

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

2）在堆中删除元素

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

注：！！！！！！！
堆是用于排序的，在查找时它是无序的，查找效率没有其他查找结构高。

5.归并排序和基数排序

①归并排序

归并（merge）：把两个或多个已经有序得到序列合并成一个。

“2路”归并：把两个有序序列合并成一个，每次选出一个小元素需要对比关键字1次。

“4路”归并：把四个有序序列合并成一个，每次选出一个小元素需要对比关键字3次。

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

代码实现

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

void Merge(int A[],int low,int mid,int high){
    int i,j,k;
    for(k=mid;k<=high;k++){
        B[k]=A[k];//复制到辅助数组B
    }
    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;
        MergeSort(A,low,mid);
        MergeSort(A,mid+1,high);
        Merge(A,low,mid,high)
    }
}

自己理解：比如说二路，相当于将排序的表首先两两分配为一起，进行排序，接着分配好的区域再次两两排序，直至排序完成。

算法效率分析

2路归并的归并树——形态上就是一棵倒立的二叉树，二叉树的第h层最多有2^(h-1)个结点，若树高为h，则应满足n<=2^(h-1)，即h-1=⌈log2 n⌉

时间复杂度：n个元素进行2路归并，归并趟数=⌈log2 n⌉ ，每趟归并时间复杂度为O(n)，则算法时间复杂度为O(n*log2 n)。

空间复杂度：空间复杂度为O(n)，来自辅助数组B

稳定性：稳定

适用性：归并排序适用于顺序存储和链式存储的线性表

注意：！！！！！！！！！！！！
对于N个元素的K路归并，排序趟数M满足K^M=N,从而M=logK N，M为整数则M=⌈logK N⌉。

②基数排序

按位值排序。

假设⻓度为n的线性表中每个结点a j a_jaj的关键字由d元组($$k^{d-1}_j,k^{d-2}_j,k^{d-3}_j,...,k^1_j,k^0_j$$)组成，其中，0 ≤ $$k^i_j$$ ≤ r − 1 (0 ≤ j < n , 0 ≤ i ≤ d − 1) ，r称为”基数“。

在上述示例中，每个结点都是由三元组组成（个位、十位、百位），每个位置的值都不超过9=10-1，所以，10称为该线性表的基数。

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

基数排序（Radix Sort）不基于比较和移动进行排序，而基于关键字各位的大小进行排序。

初始化：设置 r 个空队列，Q0,Q1, . . . ,Q (r−1)
按照各个关键字位权重递增的次序（个、十、百），对 d 个关键字位分别做“分配”和“收集”
- 分配：顺序扫描各个元素，若当前处理的关键字位=x，则将元素插⼊ Qx 队尾
- 收集：把 Q0,Q1, . . . ,Q (r−1)各个队列中的结点依次出队并链接

代码实现

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

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

typedef struct{
    LinkNode *front,*rear
}LinkQueue;

自己理解：比如说最高位有3位，有10个元素，可以将其分为10个队列，进行3次排序，第一次根据个位的值插入队列中，第二次根据十位的值分配回收，第三次根据百位的值分配回收。

算法效率分析

空间效率：一趟排序需要的辅助存储空间为r（r个队列：r个队头指针和r个队尾指针），但以后的排序中会重复使用这些队列，所以基数排序的空间复杂度为O(r)。

时间效率：基数排序需要进行d趟“分配”和”收集”操作。一趟分配需要遍历所有关键字，时间复杂度为O ( n ) O(n)O(n)；一趟收集需要合并r个队列，时间复杂度为O ( r ) O(r)O(r)。因此基数排序的时间复杂度为O(d(n+r))，它与序列的初始状态无关。

稳定性：稳定

适用性：基数排序适用于顺序存储和链式存储的线性表。

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

数据元素的关键字可以方便地拆分为 d 组，且 d 较小
每组关键字的取值范围不大，即 r 较小
数据元素个数 n 较大

③计数排序

计数排序也是一种不基于比较的排序算法。

计数排序思想

对每个待排序的元素x，统计小于x的元素个数，利用该信息就可以确定x的最终位置（当有多个元素相同时，该方案还需进行一定的优化）。

代码实现

在计数排序算法的实现中，假设输入是一个数组A[n]，序列长度为n，我们还需要两个数组：B[n]存放输出的排序序列，C[k]存储计数值。用输入数组A中的元素作为数组c的下标（索引），而该元素出现的次数存储在该元素作为下标的数组C中。

void CountSort(ELemType A[],ElemType B[],int n,int k){
    int i,C[k];
    for(i=0;i<k;i++){
        C[i]=0;
    }
    for(i=0;i<n;i++){
        C[A[i]]++;
    }
    for(i=1;i<k;i++){
        C[i]=C[i]+C[i+1];
    }
    for(i=n-1;i>=0;i--){
        B[C[A[i]]-1]=A[i];
        C[A[i]]=C[A[i]]-1;
    }
}

性能分析：

空间效率：计数排序是一种用空间换时间的做法。输出数组的长度为n；辅助的计数数组的长度为k，空间复杂度为O(n+k)。若不把输出数组视为辅助空间，则空间复杂度为O(n)。

时间效率：上述代码的第1个和第3个for循环所花的时间为O(k)，第2个和第4个for循环所花的时间为O(n)，总时间复杂度为O(n+k)。因此，当k=O(n)时，计数排序的时间复杂度为O (n)；但当
k >O(n*logn) 时，其效率反而不如一些基于比较的排序（如快速排序、堆排序等）。

稳定性：稳定。

适用性：计数排序更适用于顺序存储的线性表。计数排序适用于序列中的元素是整数且元素范围（0～k-1）不能太大，否则会造成辅助空间的浪费。

6.内部排序的比较

因素
时间复杂度	1. 简单选择排序、直接插入排序和冒泡排序在平均情况下时间复杂度都为O ( n 2 ) O(n^2)O(n2)，但直接插入排序和冒泡排序时间复杂度最好可以达到O ( n ) O(n)O(n)，而简单排序与序列初始状态无关。 2. 希尔排序作为插入排序的扩展，目前未得出精确的渐进时间。 3. 堆排序，利用堆结构，可以在线性时间内完成建堆，在O ( n log ⁡ 2 n ) O(n \log_2 n)O(nlog2n)内完成排序。 4. 快速排序基于分治思想，最坏时间复杂度会达到O ( n 2 ) O(n^2)O(n2)，但平均性能可以达到O ( n log ⁡ 2 n ) O(n \log_2 n)O(nlog2n)。 5. 归并排序基于分治思想，但其分割子序列与初始序列的排列无关，最好、最坏和平均时间复杂度均为O ( n log ⁡ 2 n ) O(n \log_2 n)O(nlog2n)。
空间复杂度	1. 简单选择排序、插入排序、冒泡排序、希尔排序和堆排序都仅需借助常数个辅助空间。 2. 快速排序需要借助一个递归工作栈，平均大小为O ( log ⁡ 2 n ) O(\log_2 n)O(log2n)，在最坏情况下可能会增长到O ( n ) O(n)O(n)。 3. 二路归并排序在合并操作中需要借助较多的辅助空间用于元素复制，大小为O ( n ) O(n)O(n)。
稳定性	1. 插入排序、冒泡排序、归并排序和基数排序是稳定的排序算法。 2. 简单选择排序、快速排序、希尔排序和堆排序都是不稳定的排序算法。 3. 平均时间复杂度为O ( n log ⁡ 2 n ) O(n \log_2 n)O(nlog2n)的稳定排序算法只有归并排序。
适用性	1. 折半插入排序、希尔排序、快速排序和堆排序适用于顺序存储。 2. 直接插入排序、冒泡排序、简单选择排序、归并排序和基数排序既适用顺序存储，又适用链式存储。