2、数据结构-图

MrJason...大约 36 分钟

第五章：图

图的基本概念

定义：
树是N（N≥0）个结点的有限集合，N=0时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足：
1）有且仅有一个特定的称为根的结点。
2）当N>1时，其余结点可分为m（m>0）个互不相交的有限集合T1，T2，…，Tm，其中每一个集合本身又是一棵树，并且称为根结点的子树。
- 图G由顶点集V和边集E组成，记为G=(V，E)
  - V(G)表示图G中顶点的有限非空集。
    用|V|表示图G中顶点的个数，也称为图G的阶
  - E(G)表示图G中顶点之间的关系（边）集合。
    用|E|表示图G中边的条数。
分类
- 有向图
  - 有向边（弧）的有限集合
    - 弧是顶点的有序对
    - <v,w>
    - v是弧尾，w是弧头
    - v邻接到w或w邻接自v
- 无向图
  - 无向边的有限集合
    - 边是顶点的无序对
    - （v,w）
    - （v,w）=(w,v)
    - w，v互为邻接点
简单图
- 1.不存在顶点到自身的边
- 2.同一条边不重复出现
多重图
- 若图G中某两个结点之间的边数多于一条，又允许顶点通过通过同一个边和自己关联
完全图
- 无向完全图
  - 如果任意两个顶点之间都存在边
- 有向完全图
  - 如果任意两个顶点之间都存在方向相反的两条弧
子图
连通图：图中任意两个顶点都是连通的
连通分量：无向图中的极大连通子图
- 连通
  - 顶点A到顶点B有路径
- 极大
  - 1.顶点足够多
  - 2.极大连通子图包含这些依附这些顶点的所有边
- 结论1:如果一个图有n个顶点，并且有小于n-1条边，则此图必是非连通图。
- 概要: 找连通分量的方法：
  从选取一个顶点开始，以这个顶点作为一个子图，然后逐个添加与这个子图相连的顶点和边直到所有相连的顶点都加入该子图
强连通：顶点V到顶点W和顶点W到顶点V都有路径
强连通图：图中任一对顶点都是强连通的
连通图的生成树：包含图中全部n个顶点，但是只有n-1条边的极小连通子图
- 结论2:生成树去掉一条边则变成非连通图，加上一条边就会形成回路。
度：以该顶点为一个端点的边数目
- 无向图中顶点V的度是指依附于该顶点的边的条数，记为TD(v)
- 有向图中顶点V的度分为出度和入度
  - 入度（ID）是以顶点v为终点的有向边的数目
  - 出度（OD）是以顶点V为起点的有向边的数目
简单路径和简单回路：顶点不重复出现的路径称为简单路径。对于回路，除了第一个和最后一个顶点其余顶点不重复出现的回路称为简单回路
权和网：图中每条边考研赋予一定意义的数值，这个数值叫做这条边的权，有权值得图称为带权图，也叫做网
路径和路径长度：顶点p到q之间的路径是指顶点序列怕保存的，p,a,b,c,d,……q。路径上边的数目就是路径长度
回路（环）：第一个和最后一个顶点相同的路径称为回路或者环
距离：从顶点u到v的最短路径长度。不存在路径则为无穷

图的存储结构

邻接矩阵（顺序存储）
邻接表（链式存储）
- 十字链表（有向图）
- 邻接多重表（无向图）

图的遍历

深度优先遍历
- 深度优先搜索(DFS:Depth-First-Search):深度优先搜索类似于树的先序遍历算法
  - 空间复杂度：由于DFS是一个递归算法，递归是需要一个工作栈来辅助工作，最多需要图中所有顶点进栈，所以时间复杂度为O(|V|)
  - 时间复杂度：1)邻接表：遍历过程的主要操作是对顶点遍历它的邻接点，由于通过访问边表来查找邻接点，所以时间复杂度为O(|E|),访问顶点时间为O(|V|),所以总的时间复杂度为O(|V|+|E|)
    2)邻接矩阵：查找每个顶点的邻接点时间复杂度为O(|V|),对每个顶点都进行查找，所以总的时间复杂度为O(|V|2)
广度优先遍历
- 广度优先搜索(BFS:Breadth-First-Search):广度优先搜索类似于树的层序遍历算法
  - 空间复杂度：BFS需要借助一个队列，n个顶点均需要入队一次，所以最坏情况下n个顶点在队列，那么则需要O(|V|)的空间复杂度。
  - 时间复杂度：
    1)邻接表：每个顶点入队一次，时间复杂度为O(|V|),对于每个顶点，搜索它的邻接点，就需要访问这个顶点的所有边，所以时间复杂度为O(|E|)。所以总的时间复杂度为O(|V|+|E|)
    2)邻接矩阵：每个顶点入队一次，时间复杂度为O(|V|),对于每个顶点，搜索它的邻接点，需要遍历一遍矩阵的一行，所以时间复杂度为O(|V|),所以总的时间复杂度为O(|V|2)

图的应用

最小生成树
- 普利姆（Prlm）
  - ①从图中找第一个起始顶点v0，作为生成树的第一个顶点，然后从这个顶点到其他顶点的所有边中选一条权值最小的边。然后把这条边的另一个顶点v和这条边加入到生成树中。
  - ②对剩下的其他所有顶点，分别检查这些顶点与顶点v的权值是否比这些顶点在lowcost数组中对应的权值小，如果更小，则用较小的权值更新lowcost数组。
  - ③从更新后的lowcost数组中继续挑选权值最小而且不在生成树中的边，然后加入到生成树。
  - ④反复执行②③直到所有所有顶点都加入到生成树中。
  - 概要:
    - 双重循环，外层循环次数为n-1，内层并列的两个循环次数都是n。故普利姆算法时间复杂度为O(n2)
      而且时间复杂度只和n有关，所以适合稠密图
- 克鲁斯卡尔（Kruskal）
  - 将图中边按照权值从小到大排列，然后从最小的边开始扫描，设置一个边的集合来记录，如果该边并入不构成回路的话，则将该边并入当前生成树。直到所有的边都检测完为止。
  - 概要:
    *
    *
    - 概要: 克鲁斯卡尔算法操作分为对边的权值排序部分和一个单重for循环，它们是并列关系，由于排序耗费时间大于单重循环，所以克鲁斯卡尔算法的主要时间耗费在排序上。排序和图中边的数量有关系，所以适合稀疏图
最短路径
- 迪杰斯特拉
  - 一个源点到其余顶点的最短路径
    - 该算法设置一个集合S记录已求得的最短路径的顶点，可用一个数组s[]来实现，初始化为0，当s[vi]=1时表示将顶点vi放入S中，初始时把源点v0放入S中。此外，在构造过程中还设置了两个辅助数组：
      dist[]：记录了从源点v0到其他各顶点当前的最短路径长度，dist[i]初值为arcs[v0][i]。
      path[]：path[i]表示从源点到顶点i之间的最短路径的前驱结点，在算法结束时，可根据其值追溯得到源点v0到顶点vi的最短路径。

假设从顶点0出发，也就是顶点0为源点，集合S最初只包含顶点0，邻接矩阵arcs表示带权有向图，arcs[i][j]表示有向边<i，j>的权值，若不存在有向边<i，j>，则arcs[i][j]为∞。Dijkstra算法的步骤如下：
1）初始化：集合S初始为0，dist[]的初始值dist[i]=arcs[0][i]，i=1，2，…，n-1。
2）找出dist[]中的最小值dist[j]，将顶点j加入集合S，即修改s[vj]=1。
3）修改从v0出发到集合V-S上任一顶点vk可达的最短路径长度：如果dist[j] + arcs[j][k]< dist[k]，则令dist[k]=dist[j] + arcs[j][k]。另外更新path[k]=j(也就是顶点j加入集合之后如果有新的路径使得到顶点k路径变短的话就将到顶点k的路径长度修改成较短的)
4）重复2）～3）操作共n-1次，直到所有的顶点都包含在S中。
* 弗洛伊德
* 所有顶点到所有顶点的最短路径
* 算法思想：
递推产生一个n阶方阵序列A(−1)，A(0)，…，A(k)，…，A(n−1)
其中A(k)[i][j]表示从顶点vi到顶点vj的路径长度，k表示绕行第k个顶点的运算步骤。初始时，对于任意两个顶点vi和vj，若它们之间存在边，则以此边上的权值作为它们之间的最短路径长度；若它们之间不存在有向边，则以∞作为它们之间的最短路径长度。以后逐步尝试在原路径中加入顶点k(k=0，1，…，n-1)作为中间顶点。如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径
* 非带权图
* 两点之间经过边数最少的路径
* 带权图
* 两点之间经过的边上权值之和最小的路径

拓扑排序
- AOV
  - 如果我们把每个环节看成图中一个顶点，在这样一个有向图中，用顶点表示活动，用弧表示活动之间的优先关系，那么这样的有向图称为AOV网(Activity On Vertex)
- 拓扑排序就是对一个有向图构造拓扑序列的过程，构造会有两种结果：
  如果此图全部顶点都被输出了，说明它是不存在回路的AOV网；
  如果没有输出全部顶点，则说明这个图存在回路，不是AOV网。
- 拓扑排序算法：
  从AOV网中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为弧尾的弧。重复这个步骤直到输出图中全部顶点，或者找不到入度为0的顶点为止。
关键路径
- AOE(Activity On Edge):在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网称为AOE网。

第六章：查找

查找的基本概念和顺序查找

查找定义：在数据集合中寻找满足某种条件的数据元素的过程称为查找
关键字：数据元素中某个可以以唯一标识该元素的数据项
平均查找长度（ASL：Average Search Length）:在查找的过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值
顺序查找(线性查找)，主要用于在线性表中进行查找。从查找表的一端开始，顺序扫描查找表，依次将扫描到的关键字和待查找的值key进行比较。如果相等，则查找成功。如果扫描结束仍然没有发现相等的数据元素，则查找失败。
- 1
- 2
- 3
- 4
- 时间复杂度为O(n)

折半查找

算法思路：
- 首先将给定值key与表中中间位置元素的关键字比较，若相等，则查找成功，返回该元素的存储位置；若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分中。然后在缩小的范围内继续进行同样的查找，如此重复直到找到为止，或者确定表中没有所需要查找的元素，则查找不成功，返回查找失败的信息。
折半查找分析
- 折半查找判定树
  - 对于折半查找，查找的比较次数就是从根结点到该结点经历的结点数
  - 时间复杂度为O(logn)
  - 概要: 具有N个（N>0）结点的完全二叉树的高度为 [log2(N+1)] 或 [log2N] +1。

分块查找

分块查找又称为索引顺序查找
分块查找思想：
- ①确定待查找值在哪个块（折半查找）

②在确定的块中查找待查找值（顺序查找）

分块查找分析
- 由于分块查找实际是进行两次查找，所以整个算法的平均查找长度是两次查找的平均查找长度之和。
  即ASL分块=ASL折半+ASL顺序
  *

二叉排序树

二叉排序树(Binary Search Tree 也叫二叉搜索树)或者是一棵空树，或者是具有以下性质的二叉树
①若左子树不空，则左子树上所有结点的值均小于它的根结点的值。
②若右子树不空，则右子树上所有结点的值均大于它的根结点的值。
③它的左右子树也是一棵二叉排序树。
算法思想
- 由于二叉排序树的特点(左子树<根结点<右子树),所以每次查找一个关键字，需要先和根结点进行比较：
  如果这个关键字小于根结点的值，则再到这个根结点的左子树进行同样的比较操作一直进行下去直到找到该关键字，表示查找成功，或者是空指针，表示查找失败。
  如果这个关键字大于根结点的值，则再到这个根结点的右子树进行同样的比较操作一直进行下去直到找到该关键字，表示查找成功，或者是空指针，表示查找失败。
  - 查找关键字代码
    - 1
    - 2
  - 插入关键字代码
    - 1)空树：直接插入新结点返回成功
      2)树不空：检查是否存在关键字重复的结点：
      ①存在：返回插入失败
      ②不存在：检查根结点的值和待插入关键字值的大小关系递归插入左右子树
  - 构造代码
    *
  - 删除结点
    - ①删除的是叶子结点
      - 方法：直接删去该结点即可
    - ②删除的是仅有左子树或者右子树的结点
      - 方法：“子承父业”
    - ③删除的是左右子树都有的结点
      - 仿照②类型，先将一个孩子“继承父业”，另一个孩子“归顺”于这个孩子
        方法：找到待删除结点的直接前驱或者直接后继结点，用该结点来替换待删除结点，再删除该结点。
二叉排序树分析
- 查找时间复杂度是O(n)
概要: “左小右大”

平衡二叉树(AVL树)

平衡二叉树(AVL树)是特殊的二叉排序树，特殊的地方在于左右子树的高度之差绝对值不超过1，而且左右子树又是一棵平衡二叉树。
平衡因子
- 定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是−1、0或1。
平衡调整
- 平衡二叉树的建立过程和二叉排序树的建立过程是相似的，都是从一棵空树开始陆续插入结点。不同的地方在于对于平衡二叉树的建立过程中，由于插入结点可能会破坏结点的平衡性，所以需要进行平衡调整。
  - LL调整(左孩子的左子树上插入结点导致)
    - 最小不平衡子树根结点的平衡因子为2>0
      它的左孩子结点平衡因子为1>0
      两个都大于0，所以直接右旋就可以调整
    - 概要: “正则右旋”
  - RR调整(右孩子的右子树上插入结点导致)
    - 最小不平衡子树根结点的平衡因子为-2<0
      它的右孩子结点平衡因子为-1<0
      两个都小于0，所以直接左旋就可以调整
    - 概要: “负则左旋”
  - LR调整(左孩子的右子树上插入结点导致)
  - RL调整(右孩子的左子树上插入结点导致)
  - 概要: 先局部转换为LL或RR，最后进行调整
分析
- 含有n个结点平衡二叉树的最大深度为O(log2n)，因此，平衡二叉树的平均查找长度为O(log2n)

B树和B+树

2-3树
- 2-3树是一种多路查找树：2和3的意思就是2-3树包含两种结点
  - 1)2结点包含一个元素和两个孩子(或者没有孩子)。
    ①左子树包含的元素小于该结点的元素值，右子树包含的元素大于该结点的元素值
    ②2结点要不有两个孩子，要不就没有孩子，不允许有一个孩子
  - 2)3结点包含一大一小两个元素和三个孩子(或者没有孩子)。(两个元素按大小顺序排列好)
    ①左子树包含的元素小于该结点较小的元素值，右子树包含的元素大于该结点较大的元素值，中间子树包含的元素介于这两个元素值之间。
    ②3结点要不有三个孩子，要不就没有孩子，不允许有一个或两个孩子
  - 3)2-3树所有叶子结点都在同一层次
2-3-4树
- 2-3-4树也是一种多路查找树：2和3和4的意思就是2-3-4树包含三种结点
  - 1)2结点包含一个元素和两个孩子(或者没有孩子)。
    ①左子树包含的元素小于该结点的元素值，右子树包含的元素大于该结点的元素值
    ②2结点要不有两个孩子，要不就没有孩子，不允许有一个孩子
  - 2)3结点包含一大一小两个元素和三个孩子(或者没有孩子)。
    ①左子树包含的元素小于该结点较小的元素值，右子树包含的元素大于该结点较大的元素值，中间子树包含的元素介于这两个元素值之间。
    ②3结点要不有三个孩子，要不就没有孩子，不允许有一个或两个孩子
  - 3)4结点包含小中大三个元素和四个孩子(或者没有孩子)。
    ①左子树包含的元素小于该结点最小的元素值，第二个子树包含大于最小的元素值小于中间元素值的元素，第三个子树包含大于中间元素值小于最大元素值的元素，右子树包含的元素大于该结点最大的元素值。
    ②4结点要不有四个孩子，要不就没有孩子，不允许有一个或两个或三个孩子
  - 4)2-3-4树所有叶子结点都在同一层次
B树
- B树也是一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例，我们把树中结点最大的孩子数目称为B树的阶。通常记为m。
  一棵m阶B树或为空树，或为满足如下特性的m叉树：
  - 1）树中每个结点至多有m棵子树。（即至多含有m-1个关键字) ("两棵子树指针夹着一个关键字")
  - 2）若根结点不是终端结点，则至少有两棵子树。(至少一个关键字)
  - 3）除根结点外的所有非叶结点至少有 ⌈m/2⌉棵子树。（即至少含有⌈m/2⌉-1个关键字）
  - 4）所有非叶结点的结构如下：
  - 5）所有的叶子结点出现在同一层次上，不带信息。(就像是折半查找判断树中查找失败的结点)
- 1.B树的查找操作
  - 查找过程：①先让待查找关键字key和结点的中的关键字比较，如果等于其中某个关键字，则查找成功。
    ②如果和所有关键字都不相等，则看key处在哪个范围内，然后去对应的指针所指向的子树中查找。
    Eg:如果Key比第一个关键字K1还小，则去P0指针所指向的子树中查找，如果比最后一个关键字Kn还大，则去Pn指针所指向的子树中查找。
- 2.B树的插入操作
  - 分裂的方法：取这个关键字数组中的中间关键字(⌈n/2⌉)作为新的结点，然后其他关键字形成两个结点作为新结点的左右孩子。
- 3.B树的删除操作
  - B树中的删除操作与插入操作类似，但要稍微复杂些，要使得删除后的结点中的关键字个数≥⌈m/2⌉-1 ，因此将涉及结点的“合并”问题。由于删除的关键字位置不同，可以分为关键字在终端结点和不在终端结点上两种情况。
    - 1）如果删除的关键字在终端结点上（最底层非叶子结点）：
      ①结点内关键字数量大于⌈m/2⌉-1 ，这时删除这个关键字不会破坏B树的定义要求。所以直接删除。
      ②结点内关键字数量等于⌈m/2⌉-1 ，并且其左右兄弟结点中存在关键字数量大于⌈m/2⌉-1 的结点，则去兄弟阶段中借关键字。
      ③结点内关键字数量等于⌈m/2⌉-1 ，并且其左右兄弟结点中不存在关键字数量大于⌈m/2⌉-1 的结点，则需要进行结点合并。
    - 2）如果删除的关键字不在终端结点上（最底层非叶子结点）：需要先转换成在终端结点上，再按照在终端结点上的情况来分别考虑对应的方法。
      - 相邻关键字：对于不在终端结点上的关键字,它的相邻关键字是其左子树中值最大的关键字或者右子树中值最小的关键字。
      - 第一种情况：存在关键字数量大于⌈m/2⌉-1 的左子树或者右子树，在对应子树上找到该关键字的相邻关键字，然后将相邻关键字替换待删除的关键字。
      - 第二种情况：左右子树的关键字数量均等于⌈m/2⌉-1 ，则将这两个左右子树结点合并，然后删除待删除关键字。
B+树
- B+树是常用于数据库和操作系统的文件系统中的一种用于查找的数据结构
- m阶的B+树与m阶的B树的主要差异在于：
  1）在B+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树；而在B树中，具有n个关键字的结点含有(n+1)棵子树。
  2）在B+树中，每个结点（非根内部结点）关键字个数n的范围是 ⌈m/2⌉≤n≤m（根结点1≤n≤m），在B树中，每个结点（非根内部结点）关键字个数n的范围是⌈m/2⌉ -1≤n≤m-1（根结点：1≤n≤m-1）。
  3）在B+树中，叶结点包含信息，所有非叶结点仅起到索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。
  4）在B+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中；而在B树中，叶结点包含的关键字和其他结点包含的关键字是不重复的。

散列表

散列表：根据给定的关键字来计算出关键字在表中的地址的数据结构。也就是说，散列表建立了关键字和存储地址之间的一种直接映射关系。
散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash(key)=Addr。
散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为“冲突”，这些发生碰撞的不同关键字称为同义词。
构造散列函数的tips：
- 1）散列函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于散列表的大小或地址范围。
- 2）散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间，从而减少冲突的发生。
- 3）散列函数应尽量简单，能够在较短的时间内就计算出任一关键字对应的散列地址。
1.常用Hash函数的构造方法：
- 1.开放定址法：直接取关键字的某个线性函数值为散列地址，散列函数为H(key)=a×key+b。式中，a和b是常数。这种方法计算最简单，并且不会产生冲突
- 2.除留余数法：假定散列表表长为m，取一个不大于m但最接近或等于m的质数p，利用以下公式把关键字转换成散列地址。散列函数为H(key)=key % p
  除留余数法的关键是选好p，使得每一个关键字通过该函数转换后等概率地映射到散列空间上的任一地址，从而尽可能减少冲突的可能性
- 3.数字分析法：设关键字是r进制数（如十进制数），而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，则应选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合
- 4.平方取中法：顾名思义，取关键字的平方值的中间几位作为散列地址。具体取多少位要看实际情况而定。这种方法得到的散列地址与关键字的每一位都有关系，使得散列地址分布比较均匀。
- 5.折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以短一些），然后取这几部分的叠加和作为散列地址，这种方法称为折叠法。关键字位数很多，而且关键字中每一位上数字分布大致均匀时，可以采用折叠法得到散列地址。
2.常用Hash函数的冲突处理办法：
- 1.开放定址法：将产生冲突的Hash地址作为自变量，通过某种冲突解决函数得到一个新的空闲的Hash地址。
  - 1）线性探测法：冲突发生时，顺序查看表中下一个单元（当探测到表尾地址m-1时，下一个探测地址是表首地址0），直到找出一个空闲单元（当表未填满时一定能找到一个空闲单元）或查遍全表。
  - 2）平方探测法：设发生冲突的地址为d,平方探测法得到的新的地址序列为d+12，d-12，d+22，d-22......
    平方探测法是一种较好的处理冲突的方法，可以避免出现“堆积”问题，它的缺点是不能探测到散列表上的所有单元，但至少能探测到一半单元。
  - 3）再散列法：又称为双散列法。需要使用两个散列函数，当通过第一个散列函数H(Key)得到的地址发生冲突时，则利用第二个散列函数Hash2(Key)计算该关键字的地址增量。
  - 4）伪随机序列法：当发生地址冲突时，地址增量为伪随机数序列，称为伪随机序列法。
- 2.拉链法：对于不同的关键字可能会通过散列函数映射到同一地址，为了避免非同义词发生冲突，可以把所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识。拉链法适用于经常进行插入和删除的情况。
- 3.散列表的查找过程：类似于构造散列表，给定一个关键字Key。
  先根据散列函数计算出其散列地址。然后检查散列地址位置有没有关键字。
  1)如果没有，表明该关键字不存在，返回查找失败。
  2)如果有，则检查该记录是否等于关键字。
  ①如果等于关键字，返回查找成功。
  ②如果不等于，则按照给定的冲突处理办法来计算下一个散列地址，再用该地址去执行上述过程。
- 4.散列表的查找性能：和装填因子有关。
  *
  - α越大，表示装填的记录越“满”，发生冲突的可能性就越大，反之发生冲突的可能性越小

第七章：排序

排序的基本知识

定义：排序就是将原本无序的序列重新排列成有序的序列。
排序的稳定性
- 如果待排序表中有两个元素Ri、Rj，其对应的关键字keyi=keyj，且在排序前Ri在Rj前面，如果使用某一排序算法排序后，Ri仍然在Rj的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。

插入类排序

直接插入排序
- 直接插入排序：首先以一个元素为有序的序列，然后将后面的元素依次插入到有序的序列中合适的位置直到所有元素都插入有序序列。
- 时间复杂度为O(n)
- 直接插入排序是稳定性是稳定的。
折半插入排序
- 折半插入排序将比较和移动这两个操作分离出来，也就是先利用折半查找找到插入的位置，然后一次性移动元素，再插入该元素。
- 折半插入排序的时间复杂度为O(n^2)
- 稳定性：和直接插入排序稳定性相同，是稳定的。
希尔排序
- 希尔排序的基本思想：希尔排序本质上还是插入排序，只不过是把待排序序列分成几个子序列，再分别对这几个子序列进行直接插入排序。
  - ①先以增量5来分割序列，也就是下标为0,5,10,15...的关键字分成一组，下标为1,6,11,16..分成一组,然后对这些组分别进行直接插入排序，这就完成了一轮希尔排序。
  - ②缩小增量(d1=n/2，di+1= [di/2]，比如10个数据序列，第一次增量d1=10/2=5,第二次增量d2= [d1/2]= [5/2]=2,并且最后一个增量等于1),所以第二轮以增量为2进行类似的排序过程。
  - ③接下来的第三轮，第四轮...都是类似的过程，直到最后一轮以增量为1。此时就是前面所说的直接插入排序。
  - 概要:
- 时间复杂度：... 希尔排序的时间复杂度约为O(n^1.3) 在最坏情况下希尔排序的时间复杂度为O(n^2)
- 空间复杂度：希尔排序的空间复杂度为O(1)
- 稳定性：不稳定，由于不同的增量可能就会把相等的关键字划分到两个直接插入排序中进行排序，可能就会造成相对顺序变化。

交换类排序

冒泡排序
- 假设待排序表长为n，从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A[i]），则交换它们，直到序列比较完。我们称它为一趟冒泡，结果将最小的元素交换到待排序列的第一个位置。下一趟冒泡时，前一趟确定的最小元素不再参与比较，待排序列减少一个元素，每趟冒泡的结果把序列中的最小元素放到了序列的最终位置，……，这样最多做n-1趟冒泡就能把所有元素排好序。
- 空间复杂度：交换时开辟了存储空间来存储中间变量，所以空间复杂度为O(1)
- 时间复杂度
- 稳定性：当两个关键字相等，if判断条件不成立，所以不会发生数据移动。所以是稳定的。
快速排序
- 快速排序是一种基于分治法的排序方法。
  每一趟快排选择序列中任一个元素作为枢轴(pivot)(通常选第一个元素)，将序列中比枢轴小的元素都移到枢轴前边，比枢轴大的元素都移到枢轴后边。
  - 1
  - 2
- 时间复杂度：
  最好情况下时间复杂度为O(nlogn) ,待排序序列越无序，算法效率越高。
  最坏情况下时间复杂度为O(n^2)，待排序序列越有序，算法效率越低。
- 空间复杂度：
  由于快速排序是递归的，需要借助一个递归工作栈来保存每一层递归调用的必要信息，其容量应与递归调用的最大深度一致。
  最好情况下为 ⌈log2(n+1)⌉(每次partition都很均匀)递归树的深度O(logn)
  最坏情况下，因为要进行n-1次递归调用，所以栈的深度为O(n)；
- 稳定性：快速排序是不稳定的，是因为存在交换关键字。

选择类排序

简单选择排序
*
- 空间复杂度：需要额外的存储空间仅为交换元素时借助的中间变量，所以空间复杂度是O(1)
- 时间复杂度：
  关键操作在于交换元素操作，整个算法由双重循环组成，外层循环从0到n-2一共n-2+1=n-1次，
  对于第i层外层循环，内层循环执行n-1-(i+1)+1=n-i-1次。
  当i=0,内层循环执行n-1次，当i=n-2,内层循环执行1次，所以是一个等差数列求和,一共为(1+n-1)(n-1)/2=n(n-1)/2 ,所以时间复杂度为O(n^2)
- 稳定性：不稳定原因就在于交换部分会打破相对顺序
堆排序
- 什么是堆？
  - 堆是一棵完全二叉树，而且满足任何一个非叶结点的值都不大于(或不小于)其左右孩子结点的值。
    - 如果是每个结点的值都不小于它的左右孩子结点的值，则称为大顶堆。
    - 如果是每个结点的值都不大于它的左右孩子结点的值，则称为小顶堆。
- 什么是堆排序？
  - 我们知道对于一个堆来说，它的根结点是整个堆中所有结点的值的最大值(大顶堆)或者最小值(小顶堆)。所以堆排序的思想就是每次将无序序列调节成一个堆，然后从堆中选择堆顶元素的值，这个值加入有序序列，无序序列减少一个，再反复调节无序序列，直到所有关键字都加入到有序序列。
    *
    *
  - 时间复杂度：
    堆排序的总时间可以分为①建堆部分+②n-1次向下调整堆
  堆排序的时间复杂度为O(n)+O(nlog2n)=O(nlog2n)
  - 堆排序不稳定

归并排序

假定待排序表含有n个记录，则可以看成是n个有序的子表，每个子表长度为1，然后两两归并，得到 ⌈n/2⌉个长度为2或1的有序表；再两两归并，……如此重复，直到合并成一个长度为n的有序表为止，这种排序方法称为2-路归并排序。
例如：49 38 65 97 76 13 27
①首先将整个序列的每个关键字看成一个单独的有序的子序列
②两两归并，49和38归并成38 49 ，65和97归并成65 97，76和13归并成13 76，27没有归并对象
③两两归并，38 49和65 97归并成38 49 65 97，13,76和27归并成13 27 76
④两两归并，38 49 65 97和13 27 76归并成13 27 38 49 65 76 97
时间复杂度：O(nlog2n)
空间复杂度:因为需要将这个待排序序列转存到一个数组，所以需要额外开辟大小为n的存储空间，即空间复杂度为O(n)
稳定性：稳定

基数排序

基数排序(也叫桶排序)是一种很特别的排序方法，它不是基于比较进行排序的，而是采用多关键字排序思想（即基于关键字各位的大小进行排序的），借助“分配”和“收集”两种操作对单逻辑关键字进行排序。基数排序又分为最高位优先（MSD）排序和最低位优先（LSD）排序。
例子：53, 3, 542, 748, 14, 214, 154, 63, 616
- 补充位数：053, 003, 542, 748, 014, 214, 154, 063, 616
- 桶实际是一个队列，先进先出(从桶的上面进，下面出)
- 关键字数量为n,关键字的位数为d,比如748 d=3，r为关键字的基的个数，就是组成关键字的数据的种类，比如十进制数字一共有0至9一共10个数字，即r=10
空间复杂度：需要开辟关键字基的个数个队列，所以空间复杂度为O(r)
时间复杂度：需要进行关键字位数d次"分配"和"收集"，一次"分配"需要将n个关键字放进各个队列中，一次"收集"需要将r个桶都收集一遍。所以一次"分配"和一次"收集"时间复杂度为O(n+r)。d次就需要O(d(n+r))的时间复杂度。
稳定性：由于是队列，先进先出的性质，所以在分配的时候是按照先后顺序分配，也就是稳定的，所以收集的时候也是保持稳定的。即基数排序是稳定的排序算法。

外部排序

需要将待排序的记录存储在外存上，排序时再把数据一部分一部分的调入内存进行排序。在排序过程中需要多次进行内存和外存之间的交换，对外存文件中的记录进行排序后的结果仍然被放到原有文件中。这种排序的方法就叫做外部排序。
如何得到初始的归并段
- 置换选择排序：解决排序段放入内存的问题
如何减少多个归并段的归并次数
- 最佳归并树：最少的归并次数（I/O次数）
如何每次m路归并快速得到最小的关键字
- 败者树：减少比较次数
概要: 内存容量无法容纳大量数据

二叉树与树与森林

树与二叉树

如何将一棵树转化成二叉树？
- 树的孩子兄弟表示法与二叉树的二叉链表表示法都是用到两个指针
  - 将孩子兄弟表示法理解成二叉链表
- 树转换成二叉树的手动模拟方法：
  - ①将同一结点的各个孩子用线串连起来
  - ②将每个结点的子树分支，从左往右，除了第一个以外全部删除
  - 概要: 例子
如何将一棵二叉树转化成树？
- 二叉树转换成树的手动模拟方法：
  - ①将二叉树从上到下分层，并调节成水平方向。
    (分层方法：每遇到左孩子则为一层)
  - ②找到每一层的双亲结点，方法为它的上一层相连的那个结点就是双亲结点。
    例如bcd这一层，与它相连的上一层结点即为a,所以bcd这三个结点的双亲结点都是a.
  - ③将每一层结点和其双亲结点相连，同时删除该双亲结点各个孩子结点之间的联系。
  - 概要: 例子

森林与二叉树

森林：森林是m（m≥0）棵互不相交的树的集合
如何将森林转换成二叉树？
- 森林转换成树的手动模拟方法：
  - ①将森林中每棵树都转换成二叉树
  - ②将第二棵树作为第一棵树的根结点的右子树，将第三棵树作为第二棵树的根结点的右子树..依次类推
  - 概要: 例子
如何将二叉树转换成森林？
- 二叉树转换成森林的手动模拟方法：
  - 反复断开二叉树根结点的右孩子的右子树指针，直到不存在根结点有右孩子的二叉树为止。
  - 概要: 例子