智能后端和架构
数据结构和算法精要总结
更新时间 2021-07-19 17:37:12    浏览 0   

TIP

本文主要是介绍 知识点精要总结 。

# 绪论

# 抽象数据类型

一个数学模型以及定义在该模型上的一组操作。

  • 抽象数据类型的定义仅取决于它的一组逻辑特性，而与计算机内部如何表示和实现无关。

# 数据结构

相互之间存在一种或多种特定关系的数据元素的集合。

  • 数据结构包括三方面内容：逻辑结构、存储结构、数据的运算。

# 逻辑结构

数据元素之间的逻辑关系，与存储无关。可分为线性结构和非线性结构。

  • 线性结构是一组有序的元素集合。

# 存储结构

数据在计算机中的表示，也称物理结构。可分为顺序存储、链式存储、索引存储、散列存储。

  • 顺序存储是把逻辑上相邻的元素存储在物理位置上也相邻的单元中。
    • 优点：随机存取
    • 缺点：可能产生较多的外部碎片
  • 链式存储不要求逻辑上相邻的单元在物理位置上也相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。
    • 优点：没有外部碎片
    • 缺点：指针占用额外空间，且只能顺序存取
  • 索引存储除了存储数据，还建立附加的索引表。
    • 优点：检索速度快
    • 缺点：增加索引表占用较多的存储空间，修改表项也浪费时间
  • 散列存储是根据关键字直接计算出元素的存储地址。
    • 优点：检索、增加、删除结点都很快
    • 缺点：存在冲突

# 算法

对特定问题求解步骤的一种描述。

  • 算法不等于程序
  • 重要特性：有穷性、确定性、可行性、输入、输出

# 线性表

具有相同数据类型的n个数据元素的有限序列。

# 顺序表

  • 动态分配：存储数组的空间是在程序执行过程中通过动态存储分配语句分配的。
  • 动态分配并非链式存储，它同样属于顺序存储结构，物理结构没有变化，依然可以采用随机存取方式，只不过分配空间的大小可以在运行时决定。

# 链式表

  1. 单链表

    • 头结点：头结点的指针域指向线性表的第一个元素结点。

      • 头指针：不管有无头结点，头指针始终指向链表的第一个结点。在有头结点的链表中，头指针指向头结点；在物头结点的链表中，头指针指向第一个元素结点。
      • 头结点的优点：
        • 链表的第一个位置上的操作和其他位置上的操作一致，无需特殊处理。
        • 无论链表是否为空，头指针始终指向头结点。空表和非空表的处理得到统一。

    • 链表创建

      • 头插法
      • 尾插法。增加一个指向链表尾结点的指针。

    • 插入结点

      • 如果需要先找到前驱结点，则f ( n ) = O ( n ) f(n)=O(n)f(n)=O(n);如果直接给出，则f ( n ) = O ( 1 ) f(n)=O(1)f(n)=O(1)

      • 插入结点元素为s，直接前驱是p。

        s.next = p.next;
p.next = s; 
12

      • 插入结点元素为s，直接后继是p。

        s.next = p.next;
p.next = s; 
swap(s.data,p.data);
123

    • 删除结点

      • 如果需要先找到前驱结点，则f ( n ) = O ( n ) f(n)=O(n)f(n)=O(n);如果直接给出，则f ( n ) = O ( 1 ) f(n)=O(1)f(n)=O(1)

      • 待删除结点为q，直接前驱是p。

        p.next = q.next;
1

    • 求表长

      • 对不带头结点的链表，当表为空时，要单独处理。

  2. 双链表

    • 增加一个指向前去的prior指针，使得访问前驱结点的时间复杂度为O ( 1 ) O(1)O(1)。

    • 插入结点

      • 待插入结点为s，直接前驱为p。

        s.next = p.next;
p.next.prior = s;
s.prior = p;
p.next = s.prior;
1234

    • 删除结点

      • 待删除结点为q，直接前驱为p。

        p.next = q.next;
q.netx.prior = p;
12

  3. 循环链表

    • 表中最后一个结点的指针不是NULL，而是改为指向头结点，形成一个环。
    • 循环单链表在处理表头和表尾的操作时，效率非常高，都只有f ( n ) = O ( 1 ) f(n)=O(1)f(n)=O(1)。

  4. 静态链表

    • 用数组描述线性表的链式存储结构，因此也要预先分配一块连续的内存空间。

# 选取存储结构的理由

  1. 基于存储的考虑。如果难以估算线性表长度时，宜采用链表。
  2. 基于运算的考虑。如果按序号访问元素比较多，宜采用顺序表；如果插入删除操作比较多，宜采用链表。
  3. 基于环境的考虑。顺序表容易实现。

# 栈和队列

# 栈

只允许在一端进行插入和删除操作的线性表。

  1. 顺序栈
    • 用一组连续的存储单元存放自栈底到栈顶的数据元素。
    • 栈的操作
      • 栈顶指针：S.top
      • 栈空：S.top == -1
      • 进栈：S.data[++top] = x;
      • 出栈：x = S.data[top–];
  2. 共享栈
    • 让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在数组两端，两个栈顶向数组中间延伸。
    • 目的：两个栈空间相互调节，更有效地利用存储空间。
  3. 链栈
    • 优点：便于多个栈合理共享存储空间并提高效率、不存在栈满上溢的情况。
    • 采用单链表实现，所有操作都是在表头进行。表头是栈顶，表尾是栈底。

# 队列

队列也是一种操作受限的线性表，只允许在表的一端进行插入，另一端进行删除。

  1. 循环队列
    • 顺序存储：分配一块连续的存储单元存放队列中的元素。
    • 循环队列：将顺序队列臆造为一个环状的空间，逻辑上成环。
    • 队尾指针Q.rear永远不可能小于队首指针Q.front。
    • 操作：
      • 初始情况：Q.front = Q.rear = 0;
      • 队首指针进1：Q.front = (Q.front + 1) % MaxSize
      • 队首指针进1：Q.rear = (Q.rear + 1) % MaxSize
      • 队列长度：（Q.front - Q.rear + MaxSize）% MaxSize
  2. 链式队列
    • 一个带有头指针和尾指针的单链表。 头指针始终指向队首结点，尾指针始终指向队尾结点。
    • 最好带有头结点，操作更简单。
    • 优点：便于多个队列合理共享存储空间并提高效率、不存在栈满上溢的情况。
  3. 双端队列
  • 两端都可以进行入队和出队操作的队列。
  • 一般是输入受限或输出受限的双端队列。

# 应用

  • 栈的应用
    • 括号匹配
      • 出现右括号则满足一个最急迫期待的左括号。要注意括号相同类型。
    • 表达式
      • 中缀表达式转后缀表达式
      • 字母按顺序写，符号按优先级低的往后放，去括号。
    • 递归
      • 递归既要有递归表达式，也要有边界条件。

*队列的应用

  • 层次遍历二叉树
    • 用队列实现
  • 计算机系统中的应用
    • 主机和外部设备速度不匹配——缓冲区
    • 资源竞争问题——CPU调度

# 树

# 概念

  1. 树是n个结点的有限集合。n=0时为空树。任意一棵非空树应满足：
    1. 有且仅有一个根结点。
    2. 当n>1时，其余结点可分为m个互不相交的有限集合，这些集合本身又是一棵树称为根结点的子树。
  2. 度
    1. 结点的度：一个结点的子结点的个数。
    2. 树的度：结点的最大度数。
  3. 分支结点：非终端结点。
  4. 路径：两个结点之间的路径是由这两个结点之间所经过的结点序列构成的。（树的路径是从上往下的，不能逆转）
  5. 路径长度
    1. 路径上所经过的边的个数。
    2. 树的路径长度是树根到所有结点路径长度的总和。
    3. 树的高度是树根到所有节点路径长度的最大值。

# 进阶概念

  1. 二叉树是n个结点的有限集合。（二叉树不同于度为2的树，是有序树，也可以是空树）
    1. n=0时为空二叉树。
    2. 非空二叉树由一个根结点和两个互不相交的左子树和右子树组成。左右子树分别是一个二叉树。
  2. 满二叉树：高度为h，且含有2 h − 1 2^h-12h−1个结点的二叉树。
  3. 完全二叉树：一个高度为h、有n个结点的二叉树，当且仅当每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树。
  4. 二叉排序树：一棵二叉树，或者是空树，或者是左子树上所有结点的关键字都小于根结点的关键字，右子树上所有结点的关键字都大于根结点的关键字。左右子树又各是一棵二叉排序树。
  5. 平衡二叉树：树上任一结点的左右子树高度差的绝对值不超过的二叉树。
  6. 平衡因子：结点的左子树和右子树的高度差。可取值：-1，0，1。
  7. 哈夫曼树：
    1. 树的结点被赋予某种意义的数值，称为权。
    2. 从根结点到任意结点的路径长度与该结点的权的乘积，称为该结点带权路径长。
    3. 树种所有叶结点的带权路径长之和，称为树的带权路径长度（WPL）。
    4. 带权路径长度最小的二叉树，称为哈夫曼树，也称最优二叉树。

# 二叉树的遍历

  1. 先序遍历

    先访问根结点，再依次访问左右子结点。

    //递归
void preOrder(Node n){
    if(n != null){
        visit(n);
        preOrder(n.left);
        preOrder(n.right);
    }
}
12345678

  2. 中序遍历

    先访问左孩子，再访问根结点，最后访问右孩子。

    //非递归
void inOrder(Node n){
    Stack s = new Stack();
    Node p = n;
    while(p || !s.isEmpty){
        if(p != null){
            s.push(p);
            p = p.left;
        }else{
            s.pop(p);
            visit(p);
            p = p.right;
        }
    }
}
123456789101112131415

  3. 后序遍历 先访问左右孩子结点，最后访问根结点。

  4. 层次遍历

  5. 能够根据两种特定的遍历序列唯一确定一棵二叉树。

# 线索二叉树

  • 目的：加快查找结点前驱和后继的速度。
  • 定义：对二叉树的线索化，实质是遍历一次二叉树，只是在便利的过程中，检查当前结点左右指针域是否为空，若为空，将它们改为指向前驱结点或后继结点的线索。
  • 原理：充分利用二叉树中大量的空指针；若无左子树，则left指向前驱；若无右子树，则right指向后继。引入左右tag表明当前指针指向的是左右孩子还是前驱后继。

# 树的存储结构

  • 双亲表示法
    • 顺序存储
    • 可以快速查找双亲结点，但查找孩子结点时需要遍历整个结构。
  • 孩子表示法
  • 孩子兄弟表示法
    • 左指针指向第一个孩子结点、右指针指向下一个兄弟
    • 优点：灵活、将树、森林转换为二叉树

# 树的遍历

  • 先根遍历
    • 先访问根结点，后依次访问孩子结点
    • 顺序和相应二叉树的先序遍历相同
  • 后根遍历
    • 先一次访问孩子结点，后访问根结点
    • 顺序和相应二叉树的中序遍历相同

# 并查集

# 二叉排序树

  • 查找：从根结点开始沿某个分支向下进行比较。
  • 插入：
    • 若原二叉排序树为空，则直接插入结点。
    • 若插入结点的关键字小于根结点的关键字，插入左子树。
    • 若插入结点的关键字大于根结点的关键字，插入右子树。
    • 递归进行。
  • 构造：多次插入。
  • 删除：
    • 若是叶子结点，直接删除。
    • 若只有一棵左子树或右子树，则让孩子代替删除结点的位置。
    • 若有两个子树，则让中序遍历的直接后继或前驱代替删除节点的位置。
  • 查找效率：BST的平均查找长度取决于树的高度。
    • 若是一个倾斜的单支树，f ( n ) = O ( n ) f(n)=O(n)f(n)=O(n)
    • 若是平衡二叉树，平均f ( n ) = O ( l o g 2 n ) f(n)=O(log_2n)f(n)=O(log2n)
    • 静态查找，二分查找法合适；动态查找，BST合适。

# 平衡二叉树

  • 每当在二叉排序树中插入或删除一个结点，就要检查其插入路径上的结点是否不再平衡。如果不平衡，需要先找到插入路径上离插入结点的最近的平衡因子的绝对值大于1的结点A，再对以A为根的子树，在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新平衡。
  • 旋转方法：
    • RL不平衡，则先右转，再左转。
    • LR不平衡，则先左转，再右转。
  • 设深度为h的平衡二叉树中含有的最少结点数为N h N_hN**h，则： N 0 = 0 N_0=0N0​=0，N 1 = 1 N_1=1N1​=1，N 2 = 2 N_2=2N2​=2，并且有N h = N h − 1 + N h − 2 + 1 N_h=N_{h-1}+N_{h-2}+1N**h​=N**h−1​+N**h−2​+1

# 哈夫曼树

  • 构造：每次选两个根结点值最小的树合并成一个新的树。
  • 应用：哈夫曼编码(可变长度编码)

# 图

# 基础概念

  1. 图G GG由顶点集V VV和边集E EE构成，记作G = ( V , E ) G=(V,E)G=(V,E)。其中，V VV是有限非空集。
  2. 有向图：E EE是有向边（弧）的有限集合时，则图G GG为有向图。
  3. 无向图：E EE是无向边的有限集合时，则图G GG为无向图。
  4. 简单图：图G GG满足：不存在重复边、不存在顶点到自身的边，则图G GG为简单图。
  5. 完全图：无向图中任意两个顶点之间都存在边，称为无向完全图；有向图中，任意两个顶点之间都存在方向相反的弧，称为有向完全图。
  6. 子图：设有两个图G = ( V , E ) G=(V,E)G=(V,E)和G ′ = ( V ′ , E ′ ) G'=(V',E')G′=(V′,E′)，若V ′ V'V′是V VV的子集，E ′ E'E′是E EE的子集，则称G ′ G'G′是G GG的子图。
  7. 回路：第一个顶点和最后一个顶点相同的路径，也成为环。
  8. 简单路径：在路径序列中，顶点不出现重复的路径。
  9. 有向树：一个顶点的入度为0，其余顶点的入度为均为1的有向图。

# 进阶概念

  1. 生成子图：满足V ′ = V V'=VV′=V的子图G ′ G'G′，称为图G GG的生成子图。
  2. 连通图、连通分量：
    1. 连通：在无向图中，两个顶点之间有路径存在。
    2. 连通图：图中任意两个顶点都是连通。
    3. 连通分量：无向图中的极大连通子图。连通分量可能有不只一个。
  3. 强连通图、强连通分量：
    1. 强连通：在有向图中，顶点之间互相可达。
    2. 强连通图：有向图中任意一对顶点都是强连通。
    3. 强连通分量：有向图中的极大强连通子图。
  4. 生成树：在连通图中，包含图中全部顶点的一个极小连通子图，并且只含尽可能少的边。（只能在连通图中，并且刚好有n-1条边）
  5. 生成森林：在非连通图中，由连通分量的生成树构成。
  6. 最小生成树：在一个带权无向连通图中，所有可能的生成树中各边权值之和最小的那棵树。

# 图的存储

  • 邻接矩阵法
    • 顺序存储。
    • 无向图的邻接矩阵是对称矩阵。
  • 邻接表法
  • 十字链表
    • 存储有向图
  • 邻接多重表
    • 存储无向图

# 图的遍历

如果图是连通的，则遍历一次就能访问图中所有顶点。

  • 广度优先搜索（BFS）
    • 借助队列实现，所以不需要递归
  • 深度优先搜索（DFS）
    • 借助递归工作栈实现。

# 最小生成树

  • 在一个带权无向连通图中，最小生成树可能有多个，但最小生成树边的权值之和是唯一的。
  • 构造方法：
    • Prim算法
    • Kruskal算法：适合稀疏图
    • 这两种方法的共同点：在添加一条新边的时候，都要检查是否构成回路。

# 最短路径

  • Dijkstra算法求单源最短路径

# 拓扑排序

  • 有向无环图（DAG）
  • AOV网：用DAG表示一个工程，顶点表示活动，有向边表示活动之间的先后关系。将这种图称为顶点表示活动的网络，即Activity of Vertex（AOV网）。
  • 构造方法：
    1. 从DAG中找一个没有前驱的顶点并输出。
    2. 删除该顶点以及所有以它为起点的边。
    3. 重复操作1和2。

# 关键路径

  • AOE网：用边表示活动的网络。有向边表示活动，权值表示开销。
  • 具有最大路径长度的路径称为关键路径，关键路径上的活动称为关键活动。
  • 找出所有事件的最早发生时间和最迟发生时间，两者相等的就是关键活动。
  • 起点事件和终点事件的是关键活动，所以最早开始时间和最迟开始时间一定是相等的。

# 查找

# 基本概念

  1. 查找表：用于查找的数据集合，由同一类型的数据元素组成。
  2. 静态查找表：一个查找表的操作不涉及插入和删除，则无需动态修改查找表。
    • 适合静态查找表的方法：折半查找、顺序查找、散列查找
    • 是合动态查找表的方法：二叉排序树查找、散列查找
  3. 关键字：数据元素中唯一标识该元素的某个数据项的值。关键字查找的结果是唯一的。
  4. 平均查找长度（ASL）：所有查找过程中进行关键字的比较次数的平均值。

# 顺序查找

# 折半查找

  • 时间复杂度O ( l o g 2 N ) O(log_2N)O(log2N)。

# 分块查找/索引顺序查找

  • 将查找表分为若干子块，块内元素可以无序，但块之间是有序的。建立一个索引表，记录每块的最大关键字和块的起始位置。

# B树（多路平衡查找树）

  1. 定义：一棵m阶B树，或者为空树，或者为满足如下性质的m叉树：

    • 树中每个结点至多有m个子树。
    • 若根结点不是终端结点，则至少有两棵子树。
    • 除根结点外的所有非叶节点至少有c e i l ( m / 2 ) ceil(m/2)cei**l(m/2)个子树。
    • 所有非叶结点结构···
    • 所有的叶结点都出现在同一层次，并且不带信息。（实际上这些结点不存在）

  2. B树高度

    1. 注意，在讨论B树高度时，一般不考虑最后一层叶节点。所以，高度h实际有h+1层。 查找成功的最大磁盘存取次数等于B树高度h。
    2. 若n>0，任意一棵树包含n个关键字，高度为h，阶数为m。
      • B树中每个结点最多有m-1个关键字,每个结点最多m个子树，则： n ⩽ ( m − 1 ) ( 1 + m + m 2 + m 3 + ⋅ ⋅ ⋅ + m h − 1 ) n\leqslant(m-1)(1+m+m^2+m^3+···+m^{h-1})n⩽(m−1)(1+m+m2+m3+⋅⋅⋅+m**h−1)，即h ⩾ l o g m ( n + 1 ) h\geqslant log_m(n+1)h⩾log**m​(n+1)。
      • 除根结点外，B树中每个结点最少有c e i l ( m / 2 ) − 1 ceil(m/2)-1cei**l(m/2)−1个关键字，每个结点最少有c e i l ( m / 2 ) ceil(m/2)cei**l(m/2)个子树，则h+1层至少有2 c e i l ( m / 2 ) h − 1 2ceil(m/2)^{h-1}2cei**l(m/2)h−1个结点，则： n + 1 ⩾ 2 ∗ c e i l ( m − 1 ) h − 1 n+1\geqslant2ceil(m-1)^{h-1}n+1⩾2∗ceil*(m−1)h−1，即h ⩽ l o g c e i l ( m / 2 ) ( ( n + 1 ) / 2 + 1 ) h\leqslant log_{ceil(m/2)}((n+1)/2+1)h⩽*logcei**l*(m/2)​((n+1)/2+1)。

  3. 插入和删除

    1. 注意合并和分裂。
    2. 注意找到关键字的前驱和后继。

  4. B+树

    与B树相比，有所不同的是：

    1. 具有n个关键字的结点只有n个子树，每个关键字对应一棵子树。
    2. 每个结点的关键字个数n的范围是c e i l ( m / 2 ) ⩽ n ⩽ m ceil(m/2) \leqslant n \leqslant mcei**l(m/2)⩽n⩽m。
    3. 叶结点包含信息，所有非叶结点仅起索引作用，且索引项中只存在指针而不含物理地址。
    4. 叶结点包含了全部关键字。

# 散列

  1. 概念
    1. 散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数。
    2. 冲突：散列函数可能会把两个或两个以上的不同关键字映射到同一地址。这些关键字被称为同义词。
    3. 解决冲突的两个方向：设计好的散列函数以减少冲突、设计好的处理冲突的方法。
    4. 散列表：根据关键字而直接进行访问的数据结构。
    5. 堆积：使用线性探测法解决冲突时，大量元素在相邻的散列地址上“聚集”起来而降低查找效率。
    6. 装填因子：定义一个散列表的装满程度。α = 已 有 记 录 数 / 散 列 表 长 度 \alpha=已有记录数/散列表长度α=已有记录数/散列表长度
  2. 散列函数
    1. 直接定址法：H ( k e y ) = a ∗ k e y + b H(key)=akey+bH*(key)=a∗key+b。适合关键字基本连续分布的情况。
    2. 除留余数法：H ( k e y ) = k e y % p H(key)=key%pH(key)=key%p。
    3. 数字分析法
    4. 平方取中法
    5. 折叠法
  3. 处理冲突的方法
    1. 开放定址法
      1. 可存放新表项的的空闲地址既向他的同义词表项开放，又向非同义词表项开放。
      2. 递推公式：H i = ( H ( k e y ) + d i ) % m H_i=(H(key)+d_i)%mH**i=(H(key)+d**i)%m。关键是处理好d i d_id**i。
      3. 设计d i d_id**i的方法：线性探测法、平方探测法、再散列法、伪随机序列法
      4. 缺点：不能随便物理删除表中已有元素。
    2. 拉链法
      1. 把所有同义词存储在一个线性链表中。
  4. 性能分析
    1. 散列表ASL依赖于散列函数、处理冲突的方法、装填因子。
    2. 散列表越满，发生冲突的可能性越大。

# 排序

# 概念

  1. 稳定性：两个关键字同等的元素，排序前后相对的顺序不变。说明不稳定性只要举出反例即可。
    • 具有稳定性的算法：直接插入排序、折半插入排序、冒泡排序、归并排序、基数排序
    • 不稳定的算法：希尔排序、快速排序、简单交换排序、堆排序
  2. 内部排序：在排序期间元素全部存放在内存中。
  3. 外部排序：在排序期间元素无法全部同时存放在内存中，必须根据需要不断地在内存、外村之间移动。外部排序一般是文件太大，必须存放在磁盘上。

# 插入排序

  1. 直接插入排序
    • 特点：待排序数组一部分是有序的，另一部分是无序的。
    • 时间效率：当数组元素有序时，f ( n ) = O ( n ) f(n)=O(n)f(n)=O(n)。一般情况下，f ( n ) = O ( n 2 ) f(n)=O(n^2)f(n)=O(n2)。
  2. 折半插入排序
  • 主要针对直接插入排序的定位算法进行优化。定位更快，插入不变。
  • 时间效率：f ( n ) = O ( n 2 ) f(n)=O(n^2)f(n)=O(n2)。
  1. 希尔排序
    • 设置步长d将表分块，在不同块中使用直接插入排序，逐步缩小d指到1。
    • 不稳定的算法
    • 仅适用于顺序存储的线性表
    • 时间效率：较佳情况下f ( n ) = O ( n 1.3 ) f(n)=O(n^{1.3})f(n)=O(n1.3)，最坏情况f ( n ) = O ( n 2 ) f(n)=O(n^2)f(n)=O(n2)。

# 交换排序

  1. 冒泡排序
    • 时间效率：当数组元素有序时，f ( n ) = O ( n ) f(n)=O(n)f(n)=O(n)。一般情况下f ( n ) = O ( n 2 ) f(n)=O(n^2)f(n)=O(n2)。
  2. 快速排序
    • 通过一趟排序将排序表划分为左右两部分，使得左边所有元素小于右边所有元素。 从前往后查看元素，标记为i；从后往前查看元素，标记为j。 先从j开始，如果a[j]>a[i],则j–；否则swap（a[i],a[j]）,并将主动权给到i。 从i开始后，如果a[j]>a[i],则i++；否则swap（a[i],a[j]）,并将主动权还给j。 最后直到满足一轮排序的要求。
    • 效率：当数组元素有序时，f ( n ) = O ( n 2 ) f(n)=O(n^2)f(n)=O(n2)。一般情况下，f ( n ) = O ( n ∗ l o g 2 n ) f(n)=O(nlog_2n)f(n)=O(n∗log2n*)。
    • 在快排中，不会产生有序序列，但每趟排序会将一个元素放到最终位置上。

# 选择排序

  1. 简单选择排序
    • 每一趟选一个最小的放到最前面
  2. 堆排序
    • 堆的定义：n个关键字序列L [ 1... n ] L[1...n]L[1...n]称为堆，当且仅当该序列满足其中一条：
      1. L ( i ) ⩽ L ( 2 i ) L(i)\leqslant L(2i)L(i)⩽L(2i)且L ( i ) ⩽ L ( 2 i + 1 ) L(i)\leqslant L(2i+1)L(i)⩽L(2i+1)
      2. L ( i ) ⩾ L ( 2 i ) L(i)\geqslant L(2i)L(i)⩾L(2i)且L ( i ) ⩾ L ( 2 i + 1 ) L(i)\geqslant L(2i+1)L(i)⩾L(2i+1)
    • 小根堆：最小元素存放在根结点中，对任意非根结点，它的值⩾ \geqslant⩾其双亲结点的值。
    • 堆排序：一种树形排序方法，将L [ 1... n ] L[1...n]L[1...n]看作一棵完全二叉树的顺序存储结构。
    • 堆的构造：先按初始序列建造成完全二叉树的形式，再进行调整，反复调整。
    • 堆的删除：只能删除堆顶元素，删除前先将最后一个元素和堆顶元素交换，再向下调整。
    • 堆的插入：插入在堆的末端，再向上调整。
    • 空间复杂度：O ( 1 ) O(1)O(1)
    • 时间复杂度：建堆时间O ( n ) O(n)O(n)，调整时间O ( h ) O(h)O(h)。排序时间始终是O ( n l o g 2 n ) O(nlog_2n)O(nlo**g2n)。

# 归并排序

  • 归并：将两个或两个以上的有序表组合成一个新的有序表。
  • 空间复杂度：O ( n ) O(n)O(n)
  • 时间复杂度：每趟归并O ( n ) O(n)O(n)，归并次数l o g 2 n log_2nlog2n。最终时间O ( n l o g 2 n ) O(nlog_2n)O(nlo**g2n)。

# 基数排序

  • 多关键字排序思想。对单关键字采用“分配”和“收集”两种操作。
  • r是辅助存储空间，即r个队列。n是n个元素。
  • 空间复杂度：O ( r ) O(r)O(r)
  • 时间复杂度：O ( d ( n + r ) ) O(d(n+r))O(d(n+r))

# 总结

1） 快速排序和堆排序相比，选择堆排序的理由：

  • 快排需要使用递归栈，堆排序辅助空间只有O ( 1 ) O(1)O(1)。
  • 快排最慢可达到O ( n 2 ) O(n^2)O(n2)，堆排序始终是O ( n l o g 2 n ) O(nlog_2n)O(nlo**g2n)。

# 参考文章

  • https://blog.csdn.net/wy827349995/article/details/103450307
更新时间: 2021-07-19 17:37:12

← 线性数据结构-线性表 →

  0
数据结构和算法精要总结
手机看
公众号
讨论
左栏
全屏
上一篇
下一篇
扫一扫 手机阅读
可分享给好友和朋友圈