王道408---DS---排序

外部排序与内部排序

内部排序指排序期间元素全部存放在内存的排序

外部排序指排序期间元素无法同时存放在内存，必须在排序的过程中根据要求不断地在内、外存之间移动的排序。

插入排序---直接插入排序

算法思想

每遍历到一个元素，就拿这个元素一直向左比较，直到比左边元素小或相等或者直到数组下标为0时终止

算法性能

算法时间复杂度 : O(n) ~ O(n^2) 平均来看是O(n^2)

算法空间复杂度 : O(1)

算法稳定性

算法稳定

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

代码实现

#include <stdio.h>
int arr[16];


// 从小到大排序
void dirInsSort(int S[],int n){     // 对 下标为[1,15]的数组排序
    int i,j;
    for(i=2;i<n;i++){           // 遍历
        if(S[i] < S[i-1]){          // 当前这个数大于前面数时，不用管，因为符合从小到大 // 当前这个数小于前面数时:
            S[0] = S[i];            // 用S[0]只不过搜索方便存放数据，起一个中介作用
            for(j=i-1;S[0] < S[j];j--){    // S[0] 相当于哨兵
                S[j+1] = S[j];              // 向后移
            }
            S[j+1] = S[0];                  
        }
    }
}

void debug(){
    for(int i=1;i<16;i++){
        printf("%d ",arr[i]);
    }
    puts("");
}
int main(){

    for(int i=1;i<16;i++){
        arr[i] = 16-i;
    }    
    dirInsSort(arr,16);
    debug();
    return 0;
}

插入排序---折半插入排序

算法思想

该算法与直接插入排序唯一的区别是: 直接插入排序向左比较的时候是逐个比较的，而折半插入排序是借助折半查找完成比较的

所以该算法比较次数少一些，但由于每次循环都要把元素右移，这导致直接插入排序与折半插入排序的时间复杂度差不多

算法性能

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

空间复杂度: O(1)

算法稳定性

稳定算法

实际上，在使用二分法的时候，会产生两种情况:

1、结果左偏

2、结果右偏

如我们要二分获取 值为3的数在该数组的位置 1,2,3,3,4,5

第一种会使获取的结果偏左，也就是得到下标为2的3

第二种会使获取的结果偏右，也就是下标为3的3

我们只需根据比较次序，看情况选出左偏或右偏的代码即可

代码如下:

// 左偏 
#include <iostream>

using namespace std;


int arr[10] = {1,2,3,3,4,5};
int val = 3;
int main(){
    int l = 0,r = 5;
    while (l < r){
        int mid = l + r >> 1;        
        if(arr[mid] >= val){       //选定val在左闭区间里  // 这里选择 >= 号是因为 val 值在左(低)区间内 
            r = mid;
        }else{
            l = mid + 1;
        }
    }
    printf("%d\n",l);
    
    return 0;
}


// 右偏 
#include <iostream>

using namespace std;


int arr[10] = {1,2,3,3,4,5};
int val = 3;
int main(){
    int l = 0,r = 5;
    while (l < r){
        int mid = l + r + 1>> 1;
        if(arr[mid] <= val){       //选定val在右闭区间里 //这里选择 >= 号是因为 val 值在右(高)区间内  
            l = mid;
        }else{
            r = mid - 1;
        }
    }
    printf("%d\n",l);
    
    return 0;
}

代码实现

void InsertSort(int A[],int n){
    int low,high,mid;
    for(int i=2;i<=n;i++){
        A[0] = A[i];
        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(int j=i-1;j>=high+1;--j)
            A[j+1]=A[j];
 	    A[high+1]=A[0];
    }
}

插入排序---希尔排序

算法思想

1. 希尔排序本质上是分步长的插入排序，第一轮选择步长 \(dk_1\) , 则对$ (1,1+dk_11,1+dk_12 \quad ...)$ 、 \((2,2+dk_1*1,2+dk_1*2 \quad...)\)、等不同的组内进行直接插入排序

2. 第二轮选择步长 \(dk_2\)(\(dk_2\)必须小于\(dk_1\)，一般选为 \(dk_1\)的 一半)，进行分组\((1,1+dk_2*1,1+dk_2*2 \quad...)\) 、 \((2,2+dk_2*1,2+dk_2*2 \quad...)\) 组内进行排序

   ...

3. 直到选择的步长为1时，其组内排序的结果即为最后的排序结果

算法性能

时间复杂度: O(n) ~ O(n^2) 平均 O(n*log^2(n)) 或 O(n^1.5)

空间复杂度: O(1)

算法稳定性

不稳定

当相同关键字记录被划分到不同子表时，可能会改变他们的相对次序

代码实现

#include <stdio.h>
int arr[16];

void debug(){
    for(int i=1;i<16;i++){
        printf("%d ",arr[i]);
    }
    puts("");
}

void shellSort(int S[],int n){
    int dk,i,j;
    for(dk = n/2;dk>=1;dk/=2){          // 选择每一轮的步长
        
        for(i=dk+1;i<n;i++){
            if(S[i] < S[i-dk]){
                S[0] = S[i];
                for(j=i-dk;S[0] < S[j] && j>0;j-=dk){           //这时的S[0]就做不了哨兵的
                    S[j+dk] = S[j];
                }
                S[j+dk] = S[0];
            }
        }
    }    
}

int main(){

    for(int i=1;i<16;i++){
        arr[i] = 16-i;
    }    
    shellSort(arr,16);
    debug();
    return 0;
}

交换排序---冒泡排序

经典排序

总感觉是低配版的选择排序

算法思路

1. 遍历所有元素，比如遍历到了第一个元素

2. 从1到n两两比较相邻元素，若逆序就交换位置

3. 比较完第一轮之后进行第二轮，遍历到第二个元素时，两两比较第二个元素与除第一、二元素的所有元素，若逆序则交换元素值，则第二轮遍历结束后，第二个元素上就是第二大的元素

   ...

倒是有点像简陋版的选择排序，选择排序与冒泡唯一的区别就是，它找到较大的元素时不直接交换，而是先标记，看有没有更大的，直到循环结束才交换，因此算法效率比冒泡排序高不少，不过它是稳定排序算法

算法性能

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

空间复杂度: O(1)

算法稳定性

稳定排序算法

代码实现

#include <stdio.h>
#include <iostream>
using namespace std;
int arr[16];

void debug(){
    for(int i=1;i<16;i++){
        printf("%d ",arr[i]);
    }
    puts("");
}
void bubbleSort(int S[],int n){
 for(int i=0;i<n-1;i++){
        bool flag = false;
        for(int j=n-1;j>i;j--){
            if(S[j-1] > S[j]){          
                swap(S[j-1],S[j]);
                flag = true;
            }
        }
        if(!flag)           // 当一轮循环后没有发生交换则说明已经排序成功，直接退出即可
            return ;
    }
}
int main(){
    
    for(int i=1;i<16;i++){
        arr[i] = 16-i;
    }    
    bubbleSort(arr,16);
    debug();
    return 0;
}

交换排序---快速排序

算法思想

快速排序采用的是分治思想，即在一个无序的序列中选取一个任意的基准元素pivot，利用pivot将待排序的序列分成两部分，前面部分元素均小于或等于基准元素，后面部分均大于或等于基准元素，然后采用递归的方法分别对前后两部分重复上述操作，直到将无序序列排列成有序序列

算法性能

时间复杂度: O(nlogn) ~ O(n^2) 平均O(nlogn)

空间复杂度: O(logn) ~ O(n) 平均O(logn)

算法稳定性

不稳定

在划分算法中，若右端区间有两个关键字相同，且均小于基准值的记录，则在交换到左端区间后，他们的相对位置会发生变化

代码实现

#include <stdio.h>
int arr[16];

void debug(){
    for(int i=1;i<16;i++){
        printf("%d ",arr[i]);
    }
    puts("");
}


void quickSort(int S[],int low,int height){
    if(low >= height) return ;
    printf("%d %d\n",low,height);

    int pivot = S[low+height>>1];   // 枢轴点  
    int left = low;
    int right = height;
    while(left < right){
        while(S[right] > pivot) right--;        // 这里不要写 <= 号,不然当pivot与left或right相等时，就一直死循环了
        while(S[left] < pivot) left++;              
        if(left < right ){
            int tmp = S[left];S[left] = S[right];S[right] = tmp;
        } 
    }

    // printf("%d %d\n",left,right);
    quickSort(S,low,right);
    quickSort(S,right+1,height);
}


// 下面是王道408书上给的排序算法,与上面略有不同
void quickSort408(int S[],int low,int high){
    if(low >= high) return ;

    int pivot = S[low]; // 枢轴   // 以 low 为初值
    int left = low,right = high;
    while(left<right){
        while(left < right && S[right] >= pivot) --right;  // 必须是 >= 不然如果遇到与pivot相同的数据时会被卡住    // 以low 为初始值，我们需要先覆盖 S[low] 所以这里先减 right
        S[left] = S[right];
        while(left < right && S[left] <= pivot) ++left;
        S[right] = S[left];
    }
    S[left] = pivot;             //因为是先从 right 开始的，所以第一个被覆盖的数一定是S[low]，即pivot 这时我们需要补上pivot
    quickSort408(S,low,left-1);
    quickSort408(S,left+1,high);
}

int main(){
    
    for(int i=1;i<16;i++){
        arr[i] = 16-i;
    }    
    quickSort408(arr,0,15);
    debug();
    return 0;
}

选择排序---简单选择排序

算法思想

每次循环都取出剩余数组中最小的元素，并采用交换的策略使其交换出剩余数组(这也是该算法不稳定的源头)

算法性能

时间复杂度: 恒为O(n^2)

空间复杂度: O(1)

算法稳定性

不稳定

在第i躺找到最小元素后，和第i个元素交换，可能会使第i个元素与其含有相同关键字元素的相对位置发生改变。如L={2,2,1}，经过一趟排序后L={1,2,2}，最终排序序列也是L={1,2,2}，但位置已经发生了变化

注意，1与2的值的改变是交换改变，而不是直接复写，这就是算法不稳定的根本原因

代码实现

#include <stdio.h>
#include <iostream>
using namespace std;
int arr[16];

void debug(){
    for(int i=1;i<16;i++){
        printf("%d ",arr[i]);
    }
    puts("");
}


void simpleSelSort(int S[],int n){
    for(int i=0;i<n-1;i++){                     // 每次循环都取出剩余数组中最小的元素
        int min = i;
        for(int j=i+1;j<n;j++)
            if(S[j] < S[min]) min = j;  
        if(min != i) swap(S[i],S[min]);         // 简单选择排序的不稳定性就源于这个交换=> (2,2`,1) => (1,2`,2)  由于swap 把2与1的位置进行了交换，所以造成了简单排序的不稳定性   
    }
}


int main(){
    
    for(int i=1;i<16;i++){
        arr[i] = 16-i;
    }    
    simpleSelSort(arr,16);
    debug();
    return 0;
}

选择排序---堆排序

堆是具有特殊性质的完全⼆叉树

算法思路

不断的输出堆顶元素...

算法性能

时间复杂度: 建堆O(n)，堆排序O(nlog2n)

空间复杂度: O(1)

算法稳定性

不稳定

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

归并排序

算法设计思路

算法本质就是分治后，把两个有序表合并为一个有序表

我觉得没有比这个更清楚了;

算法性能

时间复杂度: O(nlog2n)

空间复杂度: O(n)

算法稳定性

稳定算法

代码实现

#include <stdio.h>
int arr[16];

void debug(){
    for(int i=1;i<16;i++){
        printf("%d ",arr[i]);
    }
    puts("");
}


// 算法本质就是分治后，把两个有序表合并为一个有序表
int B[20];
void Merge(int S[],int low,int mid,int high){           // 把S[low..mid] 和 S[mid+1..high] 两个有序表 合并为一个有序表
    int i,j,k;
    for(k=low;k<=high;k++)
        B[k] = S[k];
    for(i=low,j=mid+1,k=i;i<=mid && j<=high;k++){
        if(B[i] <= B[j])
            S[k] = B[i++];
        else
            S[k] = B[j++];
    }
    while(i<=mid) S[k++] = B[i++];          // 当一方到头，另一方还未检测完，复制
    while(j<=high) S[k++] = B[j++];         // 这俩while循环只会执行一个
}

void MergeSort(int S[],int low,int high){
    if(low >= high) return ;
    
    int mid = (low+high)/2;
    MergeSort(S,low,mid);
    MergeSort(S,mid+1,high);
    Merge(S,low,mid,high);
    
}

int main(){
    
    for(int i=1;i<16;i++){
        arr[i] = 16-i;
    }    
    MergeSort(arr,1,15);
    debug();
    return 0;
}

基数排序

算法设计思想

通常有两种方法:

1、最高位优先(MSD)

按关键字权重递减依此排序

2、最低位优先(LSD)

按关键字权重递增依此排序

权重是指个位、十位、百位之类的

下面以LSD为例，其中基数r = 10 ，权值为0，1，2

需要注意的是，我们每趟排序包含两种操作，第一种是分配，第二种是收集

分配需要O(n)的时间复杂度，收集需要O(r)，故每趟需要O(n+r)的时间复杂度

或者我们也可以使用下面这个比较清晰直观的图来理解

算法性能

时间复杂度: O(d(n+r)) 其中r代表基数，d代表趟数，也代表权重

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

算法稳定性

稳定

内部排序算法总结

需要注意的是，希尔排序的最好情况与最坏情况无法判断

比较次数与序列初态有关的算法

1、快速排序

快速排序 的排序趟数就是它的递归深度。当 快排 的数据是有序时候，会退化为冒泡排序，所以快排趟数也与初始序列顺序有关了

2、冒泡排序

其主要优化就是记录了前一趟是否冒泡，如果没有产生冒泡就说明数组已经有序，直接return。如果产生了冒泡，才继续执行

3、直接插入排序

如果全部有序，则只需要遍历一趟就完成了排序，比较次数为 n-1，并且在这个过程中没有发生元素的移动。因此，比较次数 与序列初态 有关 。初始序列基本有序时，移动元素最少（效率最高）

简单插入排序随着数据变成正序时，执行效率最好，每次插入都不用移动前面的元素，时间复杂度为O(N)。当数据是反序时，执行效率最差，此时时间复杂度为O(N*N).

4、希尔排序

因为其内部使用了插入排序，所以原因如上

5、堆排序

比如元素下沉的操作，虽然一个元素是从底部拉上来的，但这不代表这个元素一定会接着沉到底部，如果沉到中间就停止下沉的话，比较次数就少了。而这个过程的比较次数自然和下沉的深度是相关的。

比较次数与序列初态无关的算法

1、二路归并排序

2、简单选择排序

3、基数排序

排序趟数与初态有关的算法

1、冒泡排序

直接看源码就知道了

2、快速排序

这俩都是交换排序捏

排序趟数与初态无关的算法

1、直接插入排序

2、折半插入排序

3、希尔排序

4、简单选择排序

5、归并排序

6、基数排序

算法稳定性

选择排序、希尔排序、快速排序、堆排序都是不稳定的

速记: 堆选希块

外部排序

将待排序的记录存储在外存上，排序时再把数据一部分一部分地调入内存进行排序，在排序过程中需要多次进行内存和外存之间的交换的方法称为外部排序。

外部排序一般使用归并算法

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

一般来说，外存信息读写的时间远大于内部排序和内部归并的时间，因此应着力减少I/O次数。

下面我们先介绍归并方法，再介绍如何进行优化

外部排序的方法

以二路归并为例:

(自己写了好久，到最后发现还是书上原来的例子好，那就直接copy过来吧)

优化一---增加归并路数k

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

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

优化二---败者树---消除增加k(归并路数)带来的副作用

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

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

下面引入败者树

败者树

它是一棵完全二叉树 ，可以快速得到n个数中最小的元素，在n个记录中选择最小的关键字，最多需要 \(⌈log_2k⌉\) 次

内部结点用来记忆左右子树中的“失败者”，而让胜者往上继续进行比较，一直到根结点。若比较两个数，大的为失败者、小的为胜利者，则根结点指向的数为最小数。

https://www.bilibili.com/video/BV1DG411m7SJ/?spm_id_from=333.337.search-card.all.click&vd_source=87f7ad8544d4c3ad070c5c2ff28b7698

优化三---置换选择排序---减少初始归并段的个数r---生成初始归并段(大小不等的归并段)

显然，减少初始归并段的个数也可以减少归并趟数S

上面采用内部排序方法得到的各个初始归并段长度都相同（除最后一段外），它依赖于内部排序时可用内存工作区>的大小。因此，必须探索新的方法用来产生更长的初始归并段，这就引出了置换选择排序

参考:

https://www.bilibili.com/video/BV1Lw41127zJ/?spm_id_from=333.337.search-card.all.click&vd_source=87f7ad8544d4c3ad070c5c2ff28b7698

另外，若我们的工作区较大(n)，每次比较n个元素都会耗费很长的时间，为此，我们可以引入败者树来提高寻找最小数的时间

优化四---最佳归并树(m叉哈夫曼树)---组织长度不等的初始归并段的归并顺序

假设由置换-选择得到9个初始归并段，其长度（记录数)依次为9,30,12,18,3,17,2,6,24。现做3路平衡归并，其一般归并树:

(倒过来看更好

其I/O次数=2xWPL = 484 (好像没有算置换选择排序时的I/O次数，不过无所谓，毕竟下面的哈夫曼树也没算这一步)

下面将第4章中哈夫曼树的思想推广到m叉树的情形，在归并树中，让记录数少的初始归并段最先归并，记录数多的初始归并段最晚归并，就可以建立总的I/O次数最少的最佳归并树。上述9个初始归并段可构造成一棵如下图所示的归并树，按此树进行归并，仅需对外存进行446次读/写，这棵归并树便称为最佳归并树 (由此看来，最佳归并树是哈夫曼树的一种，且是"最佳"哈夫曼树)。

上图中的哈夫曼树是一棵严格3叉树，即树中只有度为3或0的结点。若只有8个初始归并段，如上例中少了一个长度为30的归并段。若在设计归并方案时，缺额的归并段留在最后，即除最后一次做2路归并外，其他各次归并仍是3路归并，此归方案的外存读/写次数为386。显然，这不是最佳方案

正确的做法是：若初始归并段不足以构成一棵严格k叉树时，需添加长度为0的“虚段”，按照哈夫曼树的原则，权为0
的叶子应离树根最远。因此，最佳归并树应如下图所示。

小总结

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

理想状态下的外部排序= 较大的k路归并 + 较少的初始归并个数r

具体化一下就是 : 败者树(减少多路k中内部排序的时间)+置换选择排序(减少r) + 哈夫曼树(优化比较顺序)

需要注意的是

1、败者树是完全二叉树

2、最佳归并树是哈夫曼树的一种，它是"最优的" 哈夫曼树

本栏目推荐文章
• 考研408之C语言基础学习记录
• 考研408之C语言入门
• 2200左右的DS题单
• IBM DS5020存储更换硬盘操作
• DS coding interview
• STM32CubeMX配置I2C读取DS3231
• PVE服务器安装黑群晖DS920+
• 3ds Max网络渲染结果不一致怎么解决？
• 20231213-sdfz多校集训-DS
• DS/MLE Road map and Courses

王道 408 DS王道408 ds 绪论 王道408 ds 王道 小结408 co 链路 王道 数据408 王道 文件408 os 王道 线程 进程408 王道408 os 王道 试卷 问题408 王道408 cn 王道 内存408 cs