个人笔记展示

菜单

ZephyrSky
发布于 2025-02-17 / 16 阅读
0

算法与数据结构

#cs408

排序

CSDN九种排序简单介绍

B站256种排序可视化

1. 简单排序

1. 冒泡排序

2. 插入排序

  • 整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。

3. 二分插入排序

  • 在插入排序的基础上用二分查找方法确定插入位置的排序

4. 希尔排序

  • 希尔排序是插入排序的更高效改进版本

  • 先取一个正整数d1<n作为第一个增量，把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d_2<d_1，重复上述分组和排序操作；直至d_i=1（d_i<d_{i-1}<…<d_2<d_1），即所有记录放进一个组中排序为止。

image-20231205103616971

  • 增量序列取法

    • 各个增量间无除1以外的公因子

    • 最后一个增量必须为1

  • 希尔排序是非稳定排序算法

5. 选择排序

  • 进行n-1次遍历，第i次遍历将最小的数放在第i给位置

总结

算法名称

时间复杂度

空间复杂度

冒泡排序

n^2

n

插入排序

n^2

n

二分插入排序

n^2

n

希尔排序

n^2

n

选择排序

n^2

n

2. 快速排序

  • 主要思想：分而治之

  • 不稳定排序

1. 过程

  1. 划分(Partition)：对于给定的数组a[l:r],l<r,以x=a[q]为基准元素，确定一个下标q, l≤q≤r，将a[l:r]分成3段,即：a[l:q-1]，a[q]和a[q+1:r], 满足a[l:q-1]中的任一元素都不大于x, 同时，a[q+1:r]中的任一元素都不小于x；

  2. 递归求解：将这种策略依次分别递归地运用于a[l:q-1]和a[q+1:r], 使得a[l:q-1]和a[q+1:r]分别从小到大排好序;从而达到数组a[l:r]从小到大排好序。

2. 算法实现

void QuickSort(Item a[ ], int l, int r){
    if(l<r){
        int q=Partition(a,l,r); //划分
        QuickSort(a, l, q-1); //对左段快速排序
        QuickSort(a, q+1, r); //对右段快速排序
    }
}
//对a[0:n-1]快速排序只要调用QuickSort (a,0,n-1);
​
int Partition(Item a[], int l, int r){
    int i = l,j = r + 1;
    Item x = a[l];
    while(1){
    while(a[++i] < x);
       while(a[--j] > x);
    if(i >= j) break;
       else
           Swap(a[i],w[j]);
    }
    a[l] = a[j]; 
    a[j] = x;//把要排序数组范围的第一个元素与最后一个小于该值的元素交换
    return j;//a[j]为开头排列的数，左边<=该值，右边>=该值
}

3. 性能分析

  • 最坏情况T(n) = O(n^2)

    最坏情况发生在划分产生的两段分别包含n-1个元素和1个元素的时候。

  • 最好情况T(n) = O(n\log{}{n})

    在最好情况下，每次划分所取的基准都恰好为中值，即每次划分都产生大小相当的2段

4. 随机快速排序算法

  • 如果在a[0:n-1]中选择作为划分的基准值是随机的，那么可以证明，此时快速排序算法在平均情况下的时间复杂性就是O(n\log{}{n}) ，即达到基于比较的排序算法类中的最好水平。 因此可以将划分(Partition) 的基准值不固定为数组的第一个值或是最后一个值，而是在a[l:r]中随机地挑选。其它思想不变，这就是随机快速排序算法。

5. 三数取中划分算法

  • 对快速排序算法的划分可以采用三数取中的思想，即对待排序数组a[l:r]，选取a[l]，a[r]，a[(l+r)/2]这三个数的中位数作为划分基准，从而改进划分的对称性。//首位，末尾，中间三位

  • 序列最左和最右元素不参与划分，但是要参与递归调用。

    最左和最右元素不进行排序，因为排序前已近对三个数进行排序了，但是要参与下一轮递归

6. 三划分快速排序算法

  • 当待排序数组a[l:r]中有大量键值相同的元素时，采用三划分快速排序算法可以明显改进算法的性能

  • 以v=a[r]为基准进行划分时，将数组a[l:r]划分为左中右三段：

    • a[l:i]中均为键值小于v的元素；

    • a[i+1:j-1]中均为键值等于v的元素；

    • a[j:r]中均为键值大于v的元素。

7. 快速排序的非递归实现

  • 方法：显式的使用堆栈，记录当前划分数组的起止下标。

3. 合并排序算法

1. 递归实现

  • 基本思想

    将待排序元素序列简单地分成大小大致相等的左右两段，接着依次分别对这两段子序列递归地进行合并排序，然后利用这两段子序列已得到的有序性，将它们有序地合并在一个工作区，最后用工作区中排好序的全序列更新原待排序的元素序列成为所要求的排好序的元素序列。

  • 代码实现

void MergeSort(Item a[ ], int l, int r){
    if(l<r){ //至少有两个元素
    int m=(l+r)/2;
    MergeSort(a, l, m);
    MergeSort(a, m+1, r);
    Merge(a, b, l, m, r);//合并到数组b,b为临时数组
    Copy(b, a, l, r); //将b复制回a
    }
}
void Merge(Item a[ ], Item b[ ], int l, int m, int r){
    int i=1, j=m+1, k=1;
    while((i<=m) && (j<=r))
    if(a[i]<=a[j]) b[k++]=a[i++];
    else b[k++]=a[j++];
    if(i>m)
        for(int q=j; q<=r; q++) b[k++]=a[q];
    else
        for(int q=i; q<=m; q++) b[k++]=a[q];
}

  • 时间复杂度T(n)=O(n\log{}{n})

  • 空间复杂度S(n)=O(n)

  • merge函数的改进

    将a[l:m]复制到b[l:m],将a[m+1:r]逆序复制到b[m+1:r]中，然后从b[l:r]的两头开始，合并到数组a中。

2. 非递归实现

  • 基本思想

    事实上，算法MergeSort的递归过程只是将待排序数组一分为二，直至待排序数组中只有1个元素为止(它已有序)。然后不断地合并相邻的2个已有序的数组段。按此机制，可以首先将数组a中相邻元素两两配对。用Merge算法将它们合并，得到n/2个长度为2的排好序的数组段。然后再将它们Merge成长度为4的排好序的数组段，…，如此继续下去，直至整个数组排好序。

  • 代码

    void MergeSort(Item a[ ], Item b[ ],int n){
    int s=1;
    while(s<n){
    MergePass(a,b,s,n);
    s+=s;
    MergePass(b,a,s,n);
    s+=s;
    }
}
    void MergePass(Item a[ ], Item b[ ], int s, int n){
    int i=0;
    while(i<=n-2*s){
    Merge(a ,b, i, i+s-1, i+2*s-1);
    i=i+2*s;
    }
//剩下的元素少于2s个
    if(i+s<n) 
            Merge(a, b, i, i+s-1, n-1);
    else
        for(int j=i; j<n-1; j++)
    b[j] = a[j];
}

  • 时间复杂度T(n)=O(n\log{}{n})

    • MergePass只需O(n/(2s)*(2s))= O(n)的时间； 非递归的MergeSort算法，其中的主循环while的循环体只需O(n)的时间，而循环次数只有O(\log{}{n})次，所以算法只需要O(n\log{}{n})的时间。

  • 空间复杂度S(n)=O(n)

3. 自然合并排序

image-20231206145308802

4. 特殊有序集的线性时间排序算法

1. 计数排序

鸽巢排序的升级版

计数排序在鸽巢排序的基础上加入的前缀和，即每一位表示小于等于该数字的数量，根据该数量将数据插入到指定的位置，接着将该数量减一。

  • 基本思想

    • 数组a[0:n-1]中的每个元素均为0~m之间的一个整数；

    • 设立一个计数器数组c[0:m]，用于对数组中的元素进行计数；c[i]用来记录第i个元素出现在a[0:n-1]中的次数；

    • i从0~m-1，计算c[i]=c[i-1]+c[i]，使c[i]可以表示小于等于i的元素个数；

    • 对a数组从后向前扫描，根据c[i]的值确定a[i]元素的位置，并将对应的c[i]减1。

  • 时间复杂度T(n)=O(n)//只遍历一遍原始数组

  • 空间复杂度O(n)=O(n + m)

2. 桶排序

  • 基本思想

    给每一个元素键值设一个相应的桶，并将要排序的元素按键值对号入桶，让同一个桶内的元素保有它们输入时的相对顺序；然后按键值的序收集各相应的桶中的元素。这样，所得到的元素序列就是所要求的排好序的序列。

3. 基数排序

5. 中位数与第k小元素

  • 借助快速排序类似的随机划分RandomPartition做预处理，然后根据k值与划分点处值的关系决定在分出的两段中哪一段递归地查找。

Item randomselect(Item a[],int l,int r,int k)
{
    int i,j,p;
    if(r<=l) return a[r];
    i=randompartition(a,l,r);//a[i]左边的元素小于a[i],右边大于
    j=i-l+1;
    if(j==k) return a[i];
    if(j>k) return randomselect(a,l,i-1,k);
    else return randomselect(a,i+1,r,k-j);
}

  • Select算法找划分基准

image-20231207144550040

树

1. 普通的树

1. 树的遍历

image-20231207144747288

2. 特殊形式的二叉树

  • 满二叉树

image-20231207145149561

  • 近似满二叉树

image-20231207145211653

  • 近似满二叉树性质

    如果对一棵有n个结点的完全二叉树的结点按层次遍历的顺序编号，则对任一结点i(1≤i≤n)，有：

    1. 如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是i/2(去尾)

    2. 如果2i>n，则结点i无左孩子；如果2i\le n，则其左孩子是2i

    3. 如果2i+1>n，则结点i无右孩子；如果2i+1\le n，则其右孩子是2i+1

3. ADT二叉树

1. 用顺序存储结构实现(一种无边表示)

  • 适用对象：近似满二叉树

  • 基本想法：若将所有的结点按层次遍历的顺序，从1开始编号。

image-20231207150017319

2. 二叉树的结点度表示法(另一种无边表示)

  • 将二叉树中所有结点按照后序列表排列，并为每个结点附加一个状态值。image-20231207150125993

4. 线索二叉树

1. 引入原因

  • 用指针实现二叉树时，每个结点只有指向其左、右儿子结点的指针，所以从任一结点出发直接只能找到该结点的左、右儿子。在一般情况下无法直接找到该结点在某种遍历序下的前驱和后继结点。若在每个结点中增加指向其前驱和后继结点的指针，虽可提高遍历的效率却降低了存储效率。注意到用指针实现二叉树时，n个结点二叉树中有n+1个空指针。 若利用这些空指针存放指向结点在某种遍历次序下的前驱或后继的指针,那么,可以期望提高遍历的效率。

2. 线索化

  • 在每个结点添加前序/中序/后续遍历中的前驱和后继结点

3. 优缺点

image-20231207150905082

2. 线段树

1. 定义

  • 线段树是一种静态的树形数据结构，树中的每个结点代表一条线段，长度为1的线段称为线段树的初等线段，对应于线段树中的叶结点。

  • 线段树的每个非叶子结点有两个儿子结点，且任意非叶子结点的两个子树的高度相差不超过1，是一棵平衡二叉搜索树。

image-20231207151337992

2. 构造思想

  • 划分原则：对于线段区间(x_L,x_R]代表的线段，以左右端点坐标的中点(x_L+x_R)/2作为划分坐标，其中将(x_L, (x_L+x_R)/2]归为左儿子结点线段区间，将((x_L+x_R)/2, x_R]作为右儿子结点线段区间。对新生成的两个线段区间递归构造直到线段区间的单位长度1.

image-20231207151815670

3. 正则覆盖

  • 结点v被区间[l,r]覆盖，即[v.left, v.right]\subseteq[l,r]，但是v的父结点不被[l,r]覆盖，此时称结点v是[l,r]的正则覆盖结点。

3. 序列树

4. 二叉搜索树(AVL树)

1.定义

  • 二叉搜索树(BST,Binary Search Tree),也称二叉排序树或二叉查找树。

  • 二叉搜索树：可以为空；如果不为空，满足以下性质：

    • 非空左子树的所有键值小于其根结点的键值；

    • 非空右子树的所有键值大于其根结点的键值；

    • 左、右子树都是二叉搜索树

image-20231210102822888

2. 最大最小元素

  • 最大元素一定是在树的最右下的结点上(如上图 5)

  • 最小元素一定是在树的最左下的结点上(如上图 18)

3. 删除节点

设要删除二叉搜索树中的结点p ，分三种情况：

  1. p为叶结点\longrightarrow直接删除节点pp

  2. 只有左子树或右子树

    • p只有左子树\longrightarrow用p的左儿子代替p p

    • 只有右子树\longrightarrow用p的右儿子代替p

  3. p左、右子树均非空

找p的左子树的最大元素结点（即p的前驱结点(中序排序)），用该结点代替结点p，然后删除该结点。

image-20231210103409326

  • 时间复杂度

    • 最好情况T(n)=O(\log n)

    • 最坏情况

      第i个元素需要T(n)=O(i)时间

      插入n个元素的时间为\sum_{i=1}^{n},既O(n^2)

      每次插入平均需要O(n)时间

4. AVL树

image-20231211102415453

img

散列表

1. 集合

用位向量实现ADT集合

image-20231212103708159

  • 检测元素在位向量中相应的位来判定成员属性

  • 通过集合A和B的位向量按位或来实现并集运算

  • 通过集合A和B的位向量按位与来实现交集运算

用链表实现ADT集合

Set SetIntersection (Set A, Set B) //交集运算实现
{ 
       link a, b, p, q, r;
    Set tmp = SetInit( );
    a= A->first; b= B->first; p= NewNode( ); q= p;
    while (a && b){
        if (a->data == b->data){
            r = NewNode( ); 
            r->data = a->data; r->next=0;
            p->next=r; p=r; 
            a=a->next; b=b->next; }
        else if (a->data < b->data) a=a->next;
        else b=b->next; }
    if (p!=q) tmp->first=q->next;
    free (q);
    return tmp;
}

2. 散列技术

用数组实现散列

用散列表实现符号表

开散列

image-20231212105259285

开散列表是将数组和表结合在一起的一种数据结构，并且利用二者的优点，克服二者的缺点。

闭散列

image-20231212105429858

Test