数据结构学习笔记

考点
1、数据结构
2、算法

绪论

数据结构的研究内容

1、数据的各种逻辑结构和物理结构，以及他们之间的相应关系
2、存储结构的方法，对每种结构定义相适应的各种运算
3、设计出相应的算法
4、分析算法的效率

上述内容了解过一遍即可

数据结构的基本概念

1、数据（D）：能够输入到计算机并被计算机程序处理的信息（文字表格图像等）
2、数据元素（DE）：数据的基本单位没在计算机程序中通常作为一个整体进行考虑和处理。
3、一个数据元素包含若干个数据线（DI） （构成数据元素不可分割的最小单位）
4、DE、DI和D的逻辑结构在计算机中的表示又称为结点、数据域和存储（物理）结构

以这两张表为例
这两张表就是数据
单独一张表就是数据对象。
每张表中的每一行就是 数据元素
姓名，性别，身高，课程代号，课程名这样的一列（列名）就是数据项

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

数据结构包括逻辑结构和存储结构两个层次
逻辑结构分为四种类型：集合结构，线性结构，舒心结构，图形结构。
物理结构又叫存储结构，分为两种结构，顺序结构、链式存储结构。

逻辑结构

集合结构：数据元素同属一个集合，单个数据结构之间没有关系

线性结构：类似线性关系，线性结构中的数据元素是一对一的关系。
（这里的一对一关系我的理解是每两条数据结构之间的每个元素都有一个对应的关系）

树形结构：树形机构中的数据元素之间存在一对多的关系。（各元素以及元素之间的

2.0版

因为上面的教学视频概念有点不清楚+和上课的教材有点不一样，所以换了一套体系重新学起。

数据结构和算法

数据结构

数据：对客观事物的符号表示图像声音等

数据元素：数据的基本单位 （一行信息）

数据项：构成数据元素的不可分割的最小单位，一个数据元素可由若干个数据项组成学号姓名性别等（列名）

数据对象：具有相同性质的数据元素的集合

数据结构：相互之间存在一种或多种特定关系的数据元素的集合。
由逻辑结构，存储结构和数据的运算组成
数据结构一般定义成二元组的形式

Data_Structure = (D,S)
其中括号中的D是数据元素的有限集 S的意思是数据关系的有限集
数据集结构包括三方面的内容：逻辑结构、存储结构和数据运算

逻辑结构

再重新理一下，首先逻辑结构分为线性结构和非线性结构
线性结构肯定是1v1的关系
对于非线性结构分成集合、树形结构和图形（网状）结构三种
集合就是一个域内有若干个元素这些元素可能有一些共同点，但是元素之间没有关系
树形结构的特点就是可以归一所以是一对多的结构由一派生多
图形结构和网状结构就是比较混乱的多对多关系

存储结构

存储结构也可以叫物理结构，指的是数据结构在计算机中的表示
存储结构可以分成四类：顺序存储、链式存储、索引存储、散列存储

顺序存储
逻辑上相邻的元素存储在物理位置相邻的存储单元中
类似学校里按照学号排队，学号相邻的同学物理上也是相邻的
链式存储
借助指示元素存储地址的指针，不但存储数据，还存储下一个数据的地址相当于游戏中接连锁任务，做完任务之后告诉你下一个任务的位置
索引存储
索引存储会先建立一个索引表
索引表中的每一项是索引项
索引项包括关键字和地址
如果我们要找某个关键字我们只需要到索引表中去检索地址，然后去地址的位置找到关键字。
我个人的理解就是相当于一个通讯录，我们要去电话簿中找到我们要找的人的名字，然后根据名字对应的电话号码找到人。
散列存储
哈希（hash）存储
对于关键字，我们根据散列函数，直接计算出存储地址。
所以说存储地址和散列函数有关系

最常用的是顺序存储和链式存储

算法

算法是对特定问题求解步骤的一种描述

算法特性

算法的五个特性
1、有穷性步骤有穷时间有穷
2、确定性指令确切，没有二义性，相同输入有相同输出
3、可行性必须是可以执行的
4、输入一个算法必须有0或多个输入
5、输出一个算法有一个或多个输出

算法目标

通常设计一个“好”的算法应考虑达到以下目标

正确性正确求解问题
可读性便于理解
健壮性输入非法数据的时候可以处理
高效性效率与低存储量需求

效率度量

算法效率的度量是通过时间复杂度和空间复杂度来描述的

频度该语句在算法中被重复执行的次数
算法中所有语句的频度之和

T(n)指的就是频度之和
f(n)指的是基本运算的频度
O指的是f(n)的数量级

算法分析的目的：分析效率以求改进

重点：计算时间复杂度

顺序表

线性表的定义

线性表：具有相同数据类型的n(n>=0)个数据元素的有限序列

对于这n个元素是有顺序的，对于a1而言前面没有元素，而a2的前面是a1
所以我们可以说a1是a2的直接前驱
得到规律：除了第一个元素外，每个元素有且仅有一个直接前驱
除了最后一个元素外，每个元素有且仅有一个直接后继

线性表的基本操作

顺序表的结构

顺序表：顺序存储的线性表

上文提到顺序存储要求逻辑上相邻的两个元素物理位置也相邻，
所以要用一组地址连续的存储单元依次存储线性表中的数据元素，
所以一般存储的时候使用数组来存储的。（之前在学C++的时候多次验证数组中的地址是连续的）

数组下表表内元素内存地址之间的关系

线性表的顺序存储类型描述为

静态分配

动态分配

顺序表的特点：

顺序表最主要的特点就是随机存取，即通过首地址和元素序号可在时间O(1)内找到指定的元素
顺序表的存储密度高，每个结点只存储数据元素（相对于链表而言，链表还要存储下一个元素指针）
顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量的元素

我个人的理解就是之前C++的数组

然后关于的O（1）的时间简单来说不管找数组中的哪个元素需要的时间都是这个O(1)
然后顺序表最重要的特点就是随机存取，反而链表是没有随机存取这个特点的

顺序表的实现

插入操作

假设要把上图的50插入到16的位置，就需要从16开始把每一位都往后移一位，最后再把50插入到16的位置进行覆盖

相关代码

时间复杂度

插入算法的平均时间复杂度 O(n)

删除操作

删除算法的平均时间复杂度 O(n)

小结：顺序表的特点是可以在O(1)的时间内找到数据增加和删除的时间复杂度都是O(n)

按值查找操作

按位查找

链表

单链表的结构

单链表：链式存储的线性表

单链表中的每个属性如下图，分为两个部分，data域为属性的值，next指针域为下个元素的地址

单链表结点类型的描述如下

图中data表示存储的数据
下面的指针表示下个元素地址
对于下面的两种写法，LNode强调结点，*LinkList强调的是链表

L1L2是头指针是用来标识某个单链表的
带头结点就是最终前面多一个没有数据的元素，只用来指向第一个有数据的元素
这样可以方便运算的实现
如果对于一个不带头结点的单链表操作，就需要把第一个元素结点和后面的元素结点进行分类
如果有头结点，就不需要分类

单链表的实现

按序号查找结点值

按序号查找结点值，实际上对应的就是按位查找，
假设在如图中的带头结点的单链表中
查找过程需要从第一个头结点开始逐个往下搜索，
直到找到第i个结点为止，否则就返回最后一个指针域，
说明这个单链表中是没有这个结点的。

按值查找结点值

第二种，按值查找表结点的，
具体实现：在查找的过程中依旧是从第一个元素结点开始，
从前往后依次比较表中各个结点数据域的值。
如果某个结点数据域的值等于给定值，就返回该节点的指针。
如果直到最后都没有找到这样的结点，就返回一个null

插入结点操作

将值为x的新结点插入到单链表的第i个位置上，
在插入的过程中先判断i是否是合法值
如果不合法return一个null
在合法的情况下，我们要找到第i个结点的前驱结点p
在这个结点之后插入一个新的结点，定义为s
先进行上面的查找操作，找到p，然后修改p和s的指针域
让p指向s，让s指向p原本指向的结点
对于前插操作，我们转换为上述的后插操作后执行即可

删除结点操作

假设abc三个节点我们要删除b
然后还是先找到前驱结点a，然后把a的指针指向c就行
即让b的后驱结点变成a的后期结点，再把b删除

双链表

双链表结点中有两个指针prior和next,分别指向其前驱结点和后继结点。
只是在定义的时候有一些区别

双链表的操作

双链表的操作分为增加结点和删除结点，基本上都是和单链表一样的，都是修改前驱和后继结点的指针域来实现，唯一的不同的是因为双链表有两个指针，所以修改的时候得把两个指针都改了，只要注意这一点就行

循环链表

循环链表分为循环单链表和循环双链表

简单来说就是最后一个结点的next指向第一个结点，第一个结点的prior指向末尾，类似一个环

栈和队列

栈的基本概念

栈：只允许在一段进行插入或删除操作的线性表
如下图，可以插入的一段称为栈顶，不可以插入的一端称栈底，插入和删除成为出入栈

空栈：不含任何元素的空表
特性：先进后出，后进先出

栈的基本操作

栈的存储结构

*栈的实现

对于顺序存储，我们还是用数组来进行考虑，对于下图左边的空栈，top指针会指向当前栈顶元素的位置
由于当前式空栈，所以就指向了数组为空情况下的下标，即-1
所以栈为空的情况下 top指向-1
注意：这个指针类似数组的下标，而不是代码中的指针
对于第二种情况，A进栈了，所以top指针指向A

*顺序栈的基本运算

下面的代码抽象的惹人发笑
说是只要让top指针指向-1就是初始化了
然后判断是不是空栈也是判断一下top指针是不是指向-1

进栈
进栈的操作基本上就是先判断栈是不是满的
不满的情况下先把下标指针+1 ，再在这个元素中赋值

出栈

读栈顶元素

首先还是判断栈是不是空的，如果是空的就不用读栈顶元素了

共享栈

共享栈是两个顺序栈共用一个数组空间
对于第一个0号栈，最左边作为栈底，第二箭头作为栈顶
对于另一个栈，则相反，即两个栈的栈顶相对

对于0号栈，只需要判断top0是否等于-1就能判空
对于另一栈，只需要判断top1和maxSize-1的关系
如果是相等的，那就说明这个栈是空的。
如果不是说明不为空

判满的条件：由于top0和top1分别都是指向当前栈顶元素的位置，当两者相差1的时候，就说明这两个栈都满了。
栈满条件：top0+1 = top1

栈的链式结构

和单链表类似，多了一个栈顶的结点，一个栈底的结点
插入和删除的时候，只能在栈顶进行插入和删除
考的不多

链栈的有点是便于多个共享存储空间和提高其效率，且不存在栈满上溢的情况
栈能适用于递归算法，表达式求值以及括号匹配等问题

队列的基本概念

队列：只允许在表的一端进行插入，而在表的另一段进行删除。

和栈类似的地方：只能在一段进行插入和删除

入队或进队
出队或离队
特性：

插入的这一端称为队尾，删除的这一端称为队首
类似羽毛球桶

特性：先进先出

队列的基本操作

队列的存储结构

队列的顺序存储

对于空的队列，有两个下标指针
front是队头指针，指向对头元素
rear是队尾指针，指向队尾元素的下一个位置。（注意是下一个位置）

初始状态：front = rear = 0
判空状态：front == rear ==0
进队操作：队不满时，先送值到队尾元素，再将队尾指针+1
出队操作：队不空时，先取队头元素值，再将队头指针+1

该情况会出现上溢出的情况，这种情况是一种假溢出，由于这个队列不能出现判满的条件，所以我们就产生了一个新的队列

*循环队列

把存储队列逻辑的表从逻辑上视为一个环

同样有front和rear两个指针
front指向队头元素，rear指向队尾元素的下一个位置
初始状态： front = rear =0
队首指针进1： front = （ front +1）% maxsize
队尾指针进1：rear = （rear+1） %maxsize
队列长度：（rear+maxsize - front）%maxsize

队空条件：front = =rear

牺牲一个单元来区分队空和队满，入队时少用一个队列单元

队满条件： （rear+1）%maxsize ==front

队列中元素个数：（rear - front + maxsize）%maxsize

队列的链式存储结构

关于删除就是把front结点指向下一个结点

串

*串的基本概念

串：由零个或者多个字符组成的有限序列

其中S是串名，’a1-an’就是串的值，其中a1-an可以是字母，数字，也可以是其他字符，空格括号这些也可以

串的长度：串中字符的个数n 如果串中没有字符，长度为0 那么就是空串

子串：串中任意个连续的字符组成的子序列
类似子集，这里需要强调的是连续，对于子串，原本的串就叫主串。

字符在串中的位置：该字符在串中的序号。字串在主串中的位置以字串的第一个字符在主串中的位置来表示。

如图，B串在A串中的位置为7，C串在A串中的位置为1。

当两个串的长度相等并且每个对应位置的字符都相等时，称这两个串是相等的。

空格串：由一个或多个空格组成的串。

从数据结构来看，串是一种特殊的线性表，其特殊性体现在：数据元素可以是一个字符

这里开始都不要求）串的基本操作

几种不同的功能要大致知道

串的简单模式匹配算法

模式匹配：子串的定位操作，它求的是子串在主串中的位置

如下图开始匹配，不匹配的话就往后移动一位继续匹配。

矩阵的压缩存储

压缩存储：为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间。

目的：为了节省存储空间。

特殊矩阵：具有许多相同矩阵元素或者零元素，并且相同元素或零元素分布有一定规律性的矩阵。

常见的特殊矩阵有对称矩阵、上下三角矩阵、稀疏矩阵等

对称矩阵

对称矩阵，关于对角线对称，对角线上面的称为上三角，下面的称为下三角。

在这个矩阵中至少可以找到2个值相同的元素（a12和a21）

第一行存1个元素，第二行存2个第n行存n个
一共要存储

这么多元素

如图，假设有一个aij，然后求下标k
然后第一列有一个数据第二列有两个数据一直到第i-1列都是全加，然后第i列的第j个数据就是 aij
然后数据的个数就是 1+2+3+…+j 然后又因为数组下标从0开始，所以要-1 就是前面的-1 就是上图的结果

三角矩阵

三角矩阵的存储，如图所示三角形的部分，和对称矩阵一样，没什么好说的，在这个基础上，这个位置之外的所有元素看成一个整体，需要存储一次，占用一个单位的长度，所以总的存储次数如下图

然后如果在一维数组中

所以最后的公式就是算下标的公式

*稀疏矩阵

矩阵中非零元素的个数远小于矩阵元素的个数

将非零元素及其行和列构成一个三元组（行标、列标、值）

稀疏矩阵的三元组既可以采用数组存储，也可以采用十字链表法存储。

树和二叉树

树的基本概念

树：n个结点的有限集（n大于等于0）
当n为0的时候，这个树就是空树

研究一棵树的时候，从上往下研究，如上图的A，我们就称为根节点。
对于下面的三个分支，看成三个子树，
对于第一颗子树，根节点为B。
对于根节点B有两棵子树。树是递归定义的。
根节点A是BCD的前驱。BCD对应的就是A的后继。
对于根节点而言只有后继没有前驱。
这棵树除了根节点外的节点都有唯一的前驱。
对于所有的节点可以有零个或者多个后继。

基本术语

祖先、双亲、孩子

还是看上图，比如ABEK，ABE都可以看作是K 的祖先，E可以看作K的双亲，K可以看作E的孩子
结点的度：该结点孩子的个数
树的度：树中结点的最大度数
分支结点（非终端结点）：度大于0
叶子结点（终端结点）：度为0
兄弟：具有相同双亲的结点
深度、高度

如图深度是从上往下逐层累加的，高度是从下向上累加的，方向相反
有序树、无序树
这棵树结点的各子树从左到右有顺序可以互换，就是有序树，没有顺序不能互换，就是无序树。
路径、路径长度
两个结点经过的序列
比如A到K 的路径是ABEK
路径长度指的是经过的边的条数，这里是3

树的性质（验算未完成）待证明

1、树中的结点数等于所有结点的度数加1
2、度为m的树中第i层上之多有m i-1个结点
3、高度为h的m叉树至多有（mh-1）l（m-1）个结点
4、具有n个结点的m叉树的最小高度为

二叉树

二叉树是n个结点的有限集合：

1、或者为空二叉树

2、或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成，左右子数又分别是一棵二叉树。

特殊的二叉树

1、满二叉树

对于高度为h的二叉树，含有 2的h次方-1个结点
那么他就是满二叉树。

对于上图的二叉树，如2和3除以2 向下取整都是1，所以都可以求出根节点

所以通过上面这个公式可以由编号求得双亲结点

如果结点的编号是i，那么他的左孩子就是2i，右孩子就是2i+1

2、完全二叉树

如图可以看出，完全二叉树是在满二叉树的基础上，在最下面一层，从右往左减去一些结点。对于这样的树，就是完全二叉树。

当编号i如何这个条件，就是分支结点，如果不是，就是叶子结点

3、二叉排序树

4、平衡二叉树

树上任一结点的左子树和右子树的深度之差绝对值不超过1

*二叉树的性质

1、非空二叉树的上的叶子阶段数等于度为2的结点数加1，即

2、非空二叉树上第k层上至多有2的k-1次方个结点。
3、高度为h的二叉树至多有2的h次方-1个结点
4、完全二叉树
对于结点i的双亲，可以用这样的式子表示，i/2向下取整

5、具有n个结点的完全二叉树的高度为

二叉树的存储结构

1、顺序存储结构
指用一组地址连续的存储单元一次自上而下、自左而右存储完全二叉树的结点元素，即将完全二叉树上编号为i的结点元素存储再一维数组下标i-1的分量中。

没有值的地方标记为0，存储前需要构造。

说白了也是用数组存储

2、链式存储结构

用链表结点来存储二叉树中的每个结点。

链表结点有三个域，中间的是存储数据的data域，左右分别是指向左右孩子的指针。

如图是二叉树对应的链表结构
两者是非常类似的，只是把结点换成了链表结点，如果一个指针域没有指向孩子，就加上上图那样的符号。

再含有n个结点的二叉链表中，含有n+1个空链域，n-1个非空链域

**二叉树的遍历

二叉树的遍历：按某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。

按照先遍历左子树再遍历右子树的原则，常见的遍历次数有先序（NLR）、中序（LNR）和后序（LRN）三种遍历算法。

先序遍历

若二叉树为空，则说明也不做；否则，
1、访问根节点
2、先序遍历左子树
3、先序遍历右子树

三个字，根左右按这个顺序访问

比如这个图，访问的顺序就是124635

中序遍历

还是先判空，不为空才能执行遍历

1、中序遍历左子树
2、访问根结点
3、中序遍历右子树

如果上图按照中序遍历的顺序遍历，那么顺序就是
246135

还有一种快速的办法，就是左右位置不变，把高度看成同一行，如果有相同的就按高的在左的位置排，这样可以直接看出中序遍历

后序遍历

若二叉树为空，则说明也不做，否则：

1、后续遍历左子树
2、后续遍历右子树
3、访问根结点

再回到上图，后序遍历的顺序就是642531

层次遍历

层次遍历需要借助队列的结构。

先把二叉树的根节点入队，然后再出队
然后访问出队的结点。
如果出队的结点有左子树，就将左子树的根节点入队。
如果有右子树，就将右子树的根节点入队，然后再进行出队。
之后访问出队的结点。如此反复，直到这个队列为空。

结合该例子说明
先将1入队，然后将1出队，然后访问出队的结点1发现有左子树和右子树
然后将23入队，然后将2出队，发现2 也有左右结点，就将45入队。
再将3出队，发现3也有左右结点，再将67入队
然后将4出队，发现4有左右结点，就将89入队。
同理将5出队，将10、11入队。
然后将6出队，将12入队，再将7出队
然后再将8、9、10、11、12依次出队。

二叉树的先序序列和后序序列，无法唯一确定一棵二叉树。

树和森林

*树的存储结构

考下面两个双亲表示法和孩子兄弟表示法

树的存储结构：双亲表示法、孩子表示法、孩子兄弟表示法

双亲表示法：用一组连续的空间来存储每个结点，在每个结点后增设一个尾指针用来指向双亲结点在数组中的位置
孩子表示法：同理，除了存储每个结点之外，设立一个尾指针，来指向孩子
孩子兄弟表示法：除了存储结点值之外，设立两个指针，一个指向该节点的孩子，另一个指向该节点的兄弟结点

**树转换成二叉树的画法：

在兄弟结点之间加一条线
对每个结点，只保留它与第一个孩子的连线，抹去与其他孩子的连线
以树根为轴心，顺时针旋转45°

森林

森林就是多棵树的集合

多棵树之间是没有线段连接的

**森林转换成二叉树的画法

将森林的每棵树转化成相应的二叉树
每棵树的根也可视为兄弟结点，在每棵树之间加一根连线
以第一棵树的根为轴心顺时针旋转45°。

除了第一棵树之外，其余剩下的所有树都在右子树上

*树的遍历

用某种方式访问树种的每个结点，且仅访问一次

1、先根遍历

先根后子树

访问顺序：ABEFCDG

2、后根遍历

先子树后根

访问顺序：EFBCGDA

先根遍历序列和二叉树中的先序遍历序列结果一致

后根遍历序列和二叉树中的中序遍历序列一致。

（不要求）森林的遍历：

1、先序遍历先根后子树

先访问森林中第一棵树的根节点，然后先序遍历第一棵树的子树森林。

再来先序遍历第一棵树之后剩余的树构成的森林。

2、中序遍历先子树后根

先中序遍历森林中第一棵树的子树森林，然后再访问第一棵树的根节点

然后访问剩余的树

如图，先序遍历的顺序为：ABCDEFGHI
后序遍历的顺序为：BCDAFEHIG

将上图转化为对应的二叉树

可以发现，上图中二叉树的遍历序列。

先序遍历序列为：ABCDEFGHI
中序遍历顺序为：BCDAFEHIG

发现和上面的对应

先对先后对中

二叉排序树

*基本定义

二叉排序树（二叉查找树）或者是一棵空树，或者是具有以下特性的二叉树

1、若左子树非空，则左子树上所有结点的值均小于根结点的值
2、若右子树非空，则右子树上所有结点的值均大于根结点的值
3、左、右子树也分别是一棵二叉排序树

如上图，根节点的值是6，左子树上的结点值全都小于6，右节点上的值全都大于6

对一棵二叉排序树采用中序遍历，可以得到升序结果。

二叉排序树的插入

若原二叉排序树为空，则直接插入结点；否则，若关键字小于根节点的值，则插入到左子树，若关键字大于根节点值，则插入到右子树。

简单来说就是不断比较，小于就往左，大于就往右。

向二叉排序树插入一个新结点时，新结点一定会成为二叉排序树的一个叶子结点。

二叉排序树的构造

从一棵空树出发，一次输入元素，将它们插入二叉排序树的合适位置。

二叉树的删除（不要求）

1、若被删除的结点是叶子结点，则直接删除
2、若结点只有一棵左子树或右子树，则让该节点的子树成为其父结点的子树
3、若结点有左、右两颗子树，则令该结点的直接后继（直接前驱）代替该结点，然后从二叉排序树删去这个直接后继（直接前驱），这样就转换成了前两种情况。

这里主要说一下第三种情况，如图，用中序遍历找到78的直接后继是87，然后用87代替78，

哈夫曼树

权：树中结点常被赋予一个代表某种意义的数值

结点带权路径长度：从树的根到任意节点的路径长度与该结点上权值的乘积

树的带权（外）路径长度：树中所有叶结点的带权路径长度之和

哈夫曼树：带权路径长度最小的二叉树（树的带权路径长度）也叫最优二叉树。

构造哈夫曼树的步骤

1、将所有结点分别作为仅含一个结点的二叉树
2、构造一个新节点，从中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新节点的权值置为左、右子树上根结点的权值之和
3、从中删除刚才选出的两棵树，同时将新的到的树加入森林中
4、重复步骤2和3，直至剩下一棵树为止。

哈夫曼编码就是在哈夫曼树的基础上，左孩子的路径标为0，右孩子的路径标为1

图

图的基本概念

有向图

如上图，每条边都是有方向的，这样的图就是有向图

每条边表现成这样的形式：其中v和w表示顶点。

这个有向边表示顶点v到顶点w的一条有向边

无向图

对于上图，图中的每一条边都是没有方向的
对于图中的每一条边，我们表现成这样的形势(v,w)
又因为是没有方向的，所以v和w可以换顺序写成（w,v)
这两种形式表示的是同一条边。

简单图

不存在重复边
不存在顶点到自身的边

多重图

同时满足上面简单图的两个条件
如果一张图既存在重复边，也存在顶点到自身的边

那么就称这张图为多重图。

*完全图（简单完全图）

对于无向图，任意两个顶点之间都存在边
对于有n个顶点的无向图来说，存在边=

对于有向图，任意两个顶点之间都存在方向相反的两条弧。也就是方向相反的两条边

计算边数公式

*子图、生成子图

假设有如上两张图，发现下面的图顶点集合是第一幅图顶点集合的子集。
同时第二幅图边的集合也是第一幅图的子集。
所以我们就把下图就做上图的子图

再假设我们现在引入了第三幅图（如上）现在发现第三幅图有五个顶点。
并且他的顶点集合和第一幅图的顶点集合是相等的。
而他的边集则是第一幅图的子集。
在这种情况下第三幅图称为第一幅图的生成子图

总结一下边和顶点都是子集就是子图
顶点相同边是子集就是生成子图

*连通连通图

如上题第二张图的1和3 其中13是连通的，因为1可以到达4 4可以到达3 所以13就是连通的

连通图：如果图中的任意两个顶点都是连通的，就称之为连通图。

极小连通子图：既要保持图连通又要使得边数最小的子图。

在这种情况下边数=顶点数-1

生成树

生成树：包含图中全部顶点的一个极小连通子图

性质：包含全部顶点，边数=顶点数-1

顶点的度、入度和出度

如上图，顶点1由2条边依附，所以顶点1的度数就为2
顶点2有三条边依附，所以顶点2的度就为3

无向图的全部顶点的度的和等于边数的两倍。

对于有向图，入度是以顶点v为重点的有向边的数目。
出度是以顶点v为起点的有向边的数目。

理解：出入度是对于有向图的，入是进入顶点的边数，出是顶点出去的边数

顶点的度等于入度和出度之和
有向图的全部顶点的入读之和与出度之和相等，等于边数。

边的权和网

对于上图，我们在每条边上都加上数值，这个数值就相当于权值。
如果边上带有权值的图，我们就称为带权图或者称为网

路径、路径长度和回路

再拿上图来看

比如顶点1通过顶点3到达顶点4
路径就是顶点134
对于路径长度，我们只需要数一数顶点1到4经过了几条边所以1-4的路径长度就为2

回路：如果顶点1通过顶点3到达顶点4再回到顶点1，那这样的路径就称为回路，或者环。

图的存储结构

图的存储结构有四种：邻接矩阵法、邻接表法、十字链表法、邻接多重表法

*邻接矩阵法

假设有如下图的图

写邻接矩阵的条件：

如果边是存在的，那值就是1，如果不存在就是0

这幅图有5个顶点，所以构造的邻接矩阵是5x5

先找第一个顶点到自身的边，发现没有这样的边，那么这个值就是0
再来看1-2的边，发现存在，那么值就是1
再看1-3 是0
以此类推，最后变成下表格

所有的无向表的邻接矩阵都是这样
然后观察可以发现这个矩阵关于对角线对称
对于无向图来说，他的邻接矩阵都是对称矩阵。

接下来看有向图的画法

对于这个有向图来说，一共有四个顶点。
所以他的矩阵应该是4x4
然后来看第一个顶点。
对于1来说没有指向自己的边，所以第一个是0
有一个指向2的一个指向3的边，所有第一列是0110
同理可得第二列0000
以此类推，得到最后的结果

对于一个有向图来说，这他的邻接矩阵不关于对角线对称。
这个性质需要和无向图区别开来

接下来看如下带权图的邻接矩阵

带权图的邻接矩阵有点不同

在边存在的情况下，结果相同，在边不存在的情况下，既可以写成0 也可以写成无穷。

首先来看这个带权图，发现有六个顶点，那么他的行列就是6x6
然后再来看和刚才一样的
先看结点1，到自身是没有边的，这里我们写成无限
然后看1-2是有边，且值为5，那么现在就是∞5∞∞∞
再来换个方式观察一下2，发现2只有一条出去的边就是出度
这条出度是指向4的那么其他的直接都用无穷填进去就是∞∞4∞∞∞
以此类推结果如下

行列的数目只跟顶点有关，和边无关

n个顶点的无向连通图用邻接矩阵表示时，该矩阵至少有2(n-1)个非零元素

*邻接表法

下面是两个结点

左边的是顶点表结点
这个表中存储的都是顶点由两部分组成，第一部分是顶点域
第二部分是边表头指针。

右边的是边表的结点，这个节点里面存储的都是相应的边。
它也是由两部分组成，第一部分是邻接点域，第二部分是指针域。

简单来说就是一个用来存储顶点，一个用来存边

先来看无向图

这个无向图有五个顶点，所以我们要用五个顶点表结点分别表示顶点1-5。

最后做出来是上图这样的。
对于这个无向图有五个顶点，所以在最前面先存储五个结点，后面是用链式存储来存储结点对应的边。
最前面的结点是顶点表结点，后面的结点是边表结点。

这个无向图有七条边，有14个边表结点，所以对于每个边我们存储了两次，顶点只存储了一次

所以需要的存储空间

这里的V表示顶点，E表示边

问：那么这个顶点表结点是顺序存储吗？

再来看有向图

比如这里同样有五个顶点。
所以顶点表结点也是有五个。

先来看顶点1，顶点1到2、5都有有向边。

以上就是有向图的结点表。对于这个有向图的结点表。
首先对于这个有向图，有五个顶点，七条边。
而五个顶点，则是在顶点表里面存储了一次。
他的边表结点也一共是7个。7正好对应边数。
所以边数正好存储了1次。因此他需要的存储空间就是

这里有一点需要注意，就是上面的结点表中，比如对于1这个顶点结点，后面的2和5的边结点顺序是无所谓的，可以是2在前面，也可以是5在前面。
这个性质回导致得到的结点表可能不唯一。

特点

图的邻接表存储表示法具有以下特点：

若G为无向图，则所需的存储空间为O(|V|+2|E|)
若G为有向图，则所需的存储空间为O(|V|+|E|)
对于稀疏图，采用邻接表能极大地节省存储空间
如果是稠密图，则是和采用邻接矩阵
图的邻接表表示并不唯一
在有向图的邻接表表示中，求一个给定顶点的出度秩序计算邻接表中的结点个数。

*图的遍历

从途中的某一顶点出发，按照某种搜索方法沿图中的所有顶点访问一次且仅访问一次。

图的遍历算法主要有两种：广度优先搜索和深度优先搜索

实际上是用栈实现的

1、广度优先搜索

类似于树的层序遍历算法

说人话就是先访问第一个顶点，然后把顶点相邻的结点依次访问。

如上图，先访问1，然后在访问与1相邻的2345 然后在访问和2相邻的7 和4相邻的6
所以可能是1234567 1354267

按照广度优先规则遍历，得到的序列不一定是唯一的

2、深度优先搜索

类似树的先序遍历。

深度优先搜索类似于树的先序遍历。

对上图从顶点A出发开始深度优先遍历。就是以某个点为顶点，访问相邻且未被访问过的点。
假设现在从a开始，先把a入队，然后访问与a相邻的ceb中的任意一个
假设访问c，然后以c为顶点，访问ef中任意一个，假设方位e，那么就是访问bdf任意一个
假设访问d，那么就是访问b，f任意一个，假设访问f
那么现在没有相邻且未被访问过的顶点了，就返回d，访问b。

进行深度优先搜索得到的顶点序列也是不唯一的。

如果从一个无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是连通图。

图的应用

**最小生成树

带权连通无向图中，所有生成树中权值之和最小的生成树。

、

如图，上图是一个带权连通无向图

*prim算法

首先先让我们来了解一下prim算法：

任取一顶点，去掉所有边
选择一个与当前顶点集合距离最近的顶点，并将该顶点和相应的边加入进来，同时不能形成回路
重复2，直至途中所有顶点都并入。

代入上图，首先我们选择1这个点，然后现在的顶点集合就是1
然后对于1，最近的点（权值最小）就是3，然后现在的集合就是13
然后对于13集合，最近的点就是6，形成集合136
对于136集合最近的点是4，形成1346
对于1346 最近的点是2 然后是5
结果

**Kruskal算法

去掉所有边
选边（权最小，且不构成回路）
重复2，知道途中所有的顶点都并入

同样带入上图，首先连接13
然后发现权值最小的是2，然后我们连接46
然后权值最小的是25，连接
然后连接36（权值为4）
最后连接23结果还是和上图一样。

对于这张图，所有边的权值有相同的也有不相同的
思考，如果所有的边权值都是相等的，这个时候就可以构造出不同的最小成员树
对应的，不同的成员树的树形肯定是不唯一的。
反过来说，当这个带权连通无向图的权值都是不相等的，这个时候产生的最小成员树肯定是唯一的。
树形也是唯一的。

唯一可以保证的是不管怎么样，最小成员是的边的权值之和肯定是最小的。
因为这个就是定义。

最小成员树的边数=顶点数-1

最短路径

dijkstra算法

首先我们数出顶点的个数7
然后画出下面这样的表

然后我们构造两个集合

第一个集合中存放已经求得最短路径的顶点，第二个集合求没有求得最短路径的顶点。

上面是一个定义，一个顶点到自身的距离为0。

这个推理结果必须是动态推理的，结果我已经自己推导过了，下次复习只能重新推导一遍，正常的结果如上图。

Floyd算法

这一部分这个视频里面没交，但是明显更加重要，同时这次作业都做到了，所以肯定要学习一下。

存储图片

这个算法主要利用邻接矩阵来存图片，邻接矩阵在上面存储机构已经说了。
当然这个图基本上都是以有向带权图为主。

上图为例
其中对角线还是自己到自己的，所以是0，无穷的部分就是没有边。

算法主旨
用一句话来概括：一次将每个点作为“中间点”去做更新。

具体实现

我们需要有两个二位数组

如上图
左边的二维数组用来保存任意两个点之间最短路径的长度，-1是最开始的状态
右边的数组表示任意两个点之间的最短路径本身。

D数组最开始是比较简单的，最开始的情况下就是上面求出的邻接矩阵。
直接把邻接矩阵的数值拿过来用就行。

然后再来看右边的path，其中对角线的部分就是自己到自己，自己到自己肯定是不用走的，所以对角线可以先标成-1

现在如上图
直接存路径的话会比较麻烦，所以我们一般会采用存终点的前驱点
比如0-1 有边，并且边前面的点是0，同理 0-2也是
所以第一行就是-1，0，0
同理1-0，前驱结点是1，1-2，前驱结点也是1
所以第二行就是1，-1，1
第三行是2，-1，0，一位内2-1没有直接的边。

然后开始第二部，依次将每个点作为中间点去更新。

以0作为中间点，去更新上面的数据
简单来说，比如第一行，原先是从0开始，现在是通过0
第一列现在的意思就是0这个点，通过0点，然后分别到达0，1，2三个位置的路径
因为0和0是同一个点，所以这三个数据不变。
同理再来看第一列，第一列的意思现在是0通过0到0，1通过0到0，2通过0到0
说白了0的这一行和这一列是不需要更新的。那么path也不会变。
同时对角线也还是不会变

所以现在先变成这样，发现只有两个位置需要更新
其中两个需要更新的地方，一个从1-2变为1-0-2
其中看上面的图，1-0=10 0-2=13 所以1-0-2 = 23 明显大于4 所以这里还是4
但是下面就变成了2-0=5 0-1=6 2-0-1=11 < ∞，所以下面的2-1要更新为11 同理path的结点要更新为0

然后通过递推，推出1和2作为中间点的状态。

关于path表如何看：

拓扑排序

AOV网：顶点表示活动就是一个顶点表示一个活动或者一个事件
对于有向边指活动Vi一定是在活动Vj之前进行的
对于这种有向图称为AOV网

拓扑排序：

每个顶点出现且只出现一次
若存在一条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后面。

求上图拓扑排序的序列

拓扑排序算法步骤：

从AOV网中先择一个没有前驱的顶点并输出
从网中删除该顶点和所有以它为七点的有向边
重复1和2的步骤直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。

代入上图，首先观察发现1和5都没有前驱。
然后假设我们选择1，就把1和出度都删除
再观察发现5没有前驱，然后就把5和出度都删除，现在的顺序是15
然后依次152364

拓扑排序的序列是不唯一的。

关键路径

只要求基本概念

*基本概念

AOE网：以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销

关键路径：从开始顶点到结束顶点的所有路径中，具有最大长度的路径。

关键活动：关键路径上的活动

最早发生时间

1、事件Vk的最早发生时间ve（k）

事件对应的就是顶点
求一个顶点的最早发生时间。

指的是从源点v1到顶点Vk的最长路径长度。

通过上面的公式计算。

顶点Vk是顶点Vj的任意后续，后面的weight（vj，vk）指的是这两个顶点的权值。
这里还有一个max一定求的是最长的那一个。

比如说这里有一张图，要求第二个顶点的最早发生时间
那么我们就要从1-3-2 发生时间就是12

提问：为什么最早发生时间是最长的路径而不是最短的路径？

在计算最早发生时间时，我们考虑的是从项目开始到达某个事件的时间。因为每个事件可能有多个路径（依赖关系），这些路径的持续时间不一样。
为了确保所有路径都能够按时完成，最早发生时间选择的是最长的路径，因为最长路径是最慢的路径，它限制了整个项目的最早完成时间。
如果只考虑最短路径，可能会导致其他路径上的任务因为延迟而影响整个项目进度，导致后续的任务冲突或延误。

最迟发生时间

2、事件vk的最迟发生事件vl(k)

指的是不推迟整个工程完成的前提下

小结：

说人话，前面的最早发生时间，首先我们要从起始点开始找。然后找到最长的路径，因为可能有多条路径，然后可能有时间冲突的情况，所以选择最长的路径可以确保前面的事件都已经完成。
所以最早发生事件就是最长路径。
最迟发生时间，就不一样了，首先最迟发生事件要从汇点，也就是结束点开始找，然后找到目标点的最短路径就是聊聊，前面晦涩难懂的概念就可以不记了。

最早/最迟开始时间

活动的最早开始时间：指的是活动弧的起点所表示的事件的最早发生时间。

活动就是边，所以就是有一条边，然后这条边有一个起点，然后找原点到这条边的起点的最长路径。

最迟开始时间：指该活动胡的终点所表示的最迟发生时间与该活动所需时间之差。

首先还是活动就是边，求变的最迟发生时间，先找到边靠近汇点的那个点B，然后找出点B的最迟发生时间。
然后再用这个时间减去这条边的权值。

一个活动的最迟开始时间和最早开始时间的差额

如果上面的差额为0，那么这个活动就是关键活动。

求关键路径的步骤

令源点=0，求最早发生时间
令vl汇点=ve汇点，求最迟发生时间
根据ve值求所有弧的最早开始时间e
根据vl值求所有弧的最迟开始时间l
求AOE网中所有活动的差额d，找出所有d = 0的活动构成关键路径。

假设有这样一张图，然后让我们求关键路径。

先求出所有顶点的最早开始时间和最晚开始时间，这个也必须手动推导，用语言文字很难解释清楚。
但是理一遍流程就会。

上面的是差额同样需要自己推导一遍就能算出。

查找

*查找的概念

查找：在数据集合中，寻找满足某种条件的数据元素的过程

查找表（查找结构）：用于查找数据集合
被查找的对象

关键字：数据元素中某个数据项的值，用它可以标识一个数据结构
主关键字：可以唯一标识一个记录

（要求）平均查找长度：所有查找过程中进行关键字的比较次数的平均值
其中Pi是概率 ,就是查找第i个元素的概率，一般我们认为每个元素的查找概率都是相等的。
如果有n个元素，即：Pi=1/n
Ci是找到第i个元素所需要进行的比较次数。

*顺序查找

平均查找长度要考

基本思想

从线性表的一段开始，逐个检查关键字是否满足给定的条件。若查找到某个元素的关键字满足条件，则查找成功，返回该元素在线性表中的位置。若查找到表的另一端，仍未找到符合给定条件的元素，则返回查找失败的信息。

如同上面这张表，从下标为0的位置开始往右查找，一直到结尾，如果找到某个符合要求的元素，就把下标返回
如果一直找到最右边都没有符合要求的元素，就返回失败信息。

数据结点和线性表代码

如上图，建表的时候第一个成员变量是一个指针。
建表的时候是按实际的长度进行分配的。
0号单位进行了一个留空，不存放数据。

上面是线性表的代码。
第一个参数ST就是被查找的表，第二个参数key就是要查找的关键字。
第一行是把key存放到下标为0的数组元素中，因为前面说了0号单元留空了。
所以可以把key存放到这里。
然后通过一个for循环，从后往前进行查找，查看key 的知道是否相同。

在这个算法中把0的位置称为哨兵。
引用哨兵的目的是不需要判断数组是否会越界。因为根据循环条件
到哨兵的位置时注定会跳出循环。

注意：对线性链表只能进行顺序查找。

要求会算平均查找长度。

*折半查找

1、平均查找长度

折半查找（二分查找），仅适用于有序的顺序表。（一定要是有序的）

对于折半查找而言，我们需要设置三个变量

low,high,mid
low表示表的下界，high表示上界。

最初始的情况

low和high一开始分别表示最高或者最低。
然后mid就在表格中间的位置（取整）
接下来判断mid和关键字的大小，如图，关键字小于key，此时high的值需要改变
新high的值=mid-1
然后重复上面的判断过程。
直到low=0 high=1 此时mid取整=0，发现key大于mid
那么就要在mid的右边进行查找 low= mid+1，此时low=high mid = 1 最后比较发现key大于mid。
然后再次执行low=mid+1 但是执行完之后就不满住low小于等于high了，查找结束。

相关代码

根据mid的值，可以写出二叉树

查找成功的平均查找长度

Pi一直是1/n，这里的Li则是指每个元素查找的次数。

如上图，Pi 不变，来看Li 对于一次查找成功的情况有一种，对于两次查找成功的情况有两种，以此类推。

其中h是层数，把H带入可以求得这样的结果

对于这个结果最后化简成

如果题目中遇到了折半查找求具体的关键字序列，我们可以构造相应的判定树，然后用判定树求查找成功平均查找长度。
从平均查找长度

然后就可以求出时间复杂度

*散列表

散列函数： Hash(key) = Addr

同义词：散列函数可能会把两个或两个以上的不同关键字映射到同一地址。
比如3%4 = 3 7%4 = 3

几种常见的散列函数

直接定址法：H(key)=key H(key) = a X key + b

直接定址法就是直接取关键字的某个线性的函数值作为地址。
除留余数法：

假设散列表的表长为m 取一个不大于但最接近或等于m的质数p
然后用关键字key对p进行一个取余
H(key) = key%p
数字分析法
平方取中法
前两种方法学一下就行，后面两种方法暂时只做了解，要展开就之后再展开。

解决冲突的方法

*开放定址法

开放定址法：可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。
其数学递推公式为：Hi = (H(key)+di)%m
比如上面的3和7是同义词，然后对应的同一地址就是3
但是3这个地址只能存其中的一个。
让我们把地址3中写入3的时候，7就不能存放在3的位置。
比如现在我们把7存在0 的位置，但是7%4明显不为0，而0%4为0
这个时候0和7就是非同义词。
那么0这个地址就像非同义词7开放了。

在上面的递推公式中，H(key)指的是散列函数，m表示散列表的表长。
di表示增量的序列。通过这个递推序列，我们就可以产生新的地址。

对于增量序列有下面三种取法

线性探测法

di的值为0，1，2， … m-1
平方探测法

di = 0^2^,1^2^,-1^2^,2^2^,-2^2^,…k^2^,-k^2^ k<=m/2
再散列法

di = Hash2(key)

以这道题为例讲解一下如何处理散列表

不管长度是多少，肯定是从0开始

最后的结果就是这样，还是要自己手动演算一遍。我这边已经

平均查找长度ASL成功

ASL = 查找次数/元素个数
这里的查找次数就是比较次数这一列所有的值相加

图上就是2.5

查找不成功的平均查找长度为ASL不成功

ASL = 查找次数/散列后的地址个数

这里的查找次数不是比较次数
而散列后的地址个数就是取余的值比如这里是13
然后查找次数就是0-12这13个数的比较次数。
第一次查找0这个位置，但是0这里是空，所以查找失败
然后看1这个位置查找不成功的比较次数，
只需要看和后面空着的单元格相聚多少单元，这里最接近1的是13
包含1和13，一共比较了13次。
同理，2比较了12次
所以是 1 13 12 11 10 9 8 7 6 5 4 3 2
对于2对应的就是12 12比较了自己的一次比较了13的一次。
上面的数相加得到查找次数
所以结果为7

到这里用开放地址法和线性探测处理冲突已经结束了

非同义词冲突

*拉链法

为了避免非同义词发生冲突，把所有的同义词存储在一个线性链表中。

同样来看例题

序列和刚才的一样，只是解决方法不同，取余的结果我们已经计算过了。
然后现在我们先创建一个线性表

然后邻接表法，
对于每个结点，都有两部分，一部分存储数据（也就是关键字本身），另一部分存储下一个结点的地址指针
先算出19取余是6，然后把19放到6这个位置，然后留出了一个指针等待存储下一个结点。

最后的结果就是这样，不要忘记加上末尾符号表示后继指针为空。

平均查找长度

对于14、68、19、20、23、11都是查找一次就能成功
所以是1x6
对于01、55、84、10
都是查找两次才能成功，所以是2x4
对于27和79分别要3和4
所以是6+8+7=21/12 = 1.75

失败平均查找长度

不成功的情况，对于024589 12 都是查找一次就不成功了
对于20 11 分别有两次不成功的情况
简单来说就是数一数休止符在每一列的个数
每一列休止符个数x列号
结果就是(1x7+2x2+3x3+5)/13=25/13

散列表的查找长度取决于三个因素

散列函数
处理冲突的方法
填装因子

装填因子a = 表中记录数n/散列表长度m

散列表的平静查找长度依赖于散列表的装填因子a，不直接依赖与n或m
如果表中的记录数越来越接近于列表长度，那么a的值就越来越近1
所以这个时候发生冲突的可能性也就越来越大
所以a越大，表示装填的记录越满，发生冲突的可能性就越大。

排序

排序的基本概念

排序：重新排列表中的元素，使表中的元素满足按关键字有序

稳定性：Ri Rj 相对位置
假设这两个元素的关键字相同，经过某一个排序算法之后
两者的相对位置不变，那我们就可以说这个排序算法是稳定的。

内部排序：指在排序期间元素全部存在内存中的排序比较和移动

插入排序、交换排序、选择排序、归并排序和基数排序
对于前面的四种排序都是基于比较和移动的
最后的基数排序则是特殊的，不基于比较和移动的

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

插入排序

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

直接插入排序

首先看第一个49，假设它已经是拍好的序列
再看第二个元素38 ，此时要插入到49前面
然后把38插入到49之前，后面的元素暂时保持不变。
此时的序列是 38 49 65 97 76 13 27 49
此时i=2（循环次数为2排序次数为2）
排序之后的数据是2个，38 和 49
以此类推
i=3时序列：38 49 65 97 76 13 27 49
i=4时序列：38 49 65 97 76 13 27 49
i=5时序列：38 49 65 76 97 13 27 49
…
i = 8时序列： 13 27 39 49 49 65 76 97

对于n个元素而言，我们只需要进行n-1次排序
就可以求得最后的结果。

参考代码

代码中定义了两个参数
第一个参数是传入的要排序的数组，第二个参数是数组的长度n
下面一个for循环， i作为循环变量值从2到n
i的取值一共有n-1种

空间效率：O（1）

时间效率：O（n^2^)

稳定性：稳定

希尔排序

把间隔某个增量的记录组成一个子表，对各个子表分别进行直接插入排序，当整个表中的元素已呈基本有序时，再对全体记录进行一次直接插入排序。

希尔排序是基于直接插入排序的，是直接插入排序的一个优化。

假设有如上10个元素，我们要让他进行写入排序之后是有序的。
那么我们先要设置一个增量。
这里我们设置增量d = 5
按照思想我们先从第一个元素开始。
先从第一个元素开始，我们找到49
然后再往后5个元素，找到13
然后再往后5个元素发现找不到了，那么49和13就是一个子表
排序之后的结果就是13 49
同理，从第二个元素出发，找到38和27
排序之后的结果就是13 27 49 38
全部排序完的结果就是
13 27 49 53 04 49 38 65 97 76
这里是经过了一套希尔排序之后的结果
然后我们需要对d的值进行改变取一个小于刚才的值假设我们取3
第一个子表就是13 53 38 76
第一个子表排序之后的结果就是 13 38 53 76
同理最后的结果就是 13 04 49 38 27 49 53 65 97 76
最后把d变成1
重新排序之后的结果是 04 13 27 38 49 49 53 65 76 97
此时已经是有序的了希尔排序也结束了

这里不用担心的d的问题，考试的时候会把d给出。

空间效率：O(1)
时间效率：依赖于分量d 不考虑。
稳定性：不稳定

后续还会学习更多的排序算法，对于初始的排序算法，一般来说是稳定的
对于优化的排序算法，一般来说是不稳定的。
偶尔还是有例外。

补充一张希尔排序图

交换排序

冒泡排序

基本思想：从后往前（或者从前往后）两两比较相邻元素的值，若为逆序，则进行交换，直到序列比较完，第一趟冒泡结束，结果是将最小的元素交换到待排序的第一个位置（或将最大的元素交换到待排序列的最后一个位置）

这个已经是老朋友了，就不用多说，直接上例子

第一趟结束之后就是13在最前面。

最后的结果

快速排序

基本思想是：在待排序表L[1…n]中认取一个元素pivot作为枢轴（通常取首元素），
通过一趟快速排序将待排序表划分为独立的两部分L[1…k-1]和L[k+1…n],
pivot放在了最终位置的L[k]中

例

如上面的例子，首先我们先把关键字写下来

一般都以第一个元素作为枢轴，这里就是49
作为枢轴之后我们会把他扣出来。
接下来我们会设两个指针，i和j
分别指向头和尾元素，

现在的样子就是这样。

然后我们会让j指向的元素跟枢轴进行比较，如果是小于的，就放到i指向的位置。
现在49不小于49，所以不需要交换。
然后j指针往前移动
此时j指向27，27小于49，那么就把27交换到i所在的位置，同时27处的值为空
此时我们要交换移动的指针。

此时的状态是这样，j指向的位置为空，然后i往后移动，将38和枢轴进行比较，发现38小于枢轴49，所以不移动
以此类推

直到这个状态，i和j的值相等了，就不需要进行交换了，我们先把49的值存放到i和j指向的位置。
此时i和j相等。对于前面的元素都比49小。后面的元素都是大于等于49
此时49存放的位置就是排序之后的最终位置。
到这里一趟排序才结束。
再用同样的方法对前面的序列进行快速排序和后面的序列进行快速排序。

先把前面的序列写出来，然后取首元素27作为枢轴，然后再用同样的方法对它进行快速排序

同理对后面的序列一样进行排序

最后的结果如上

空间效率：O(log2n)
时间效率：O(nlog2n)
稳定性：不稳定

快速排序是所有内部排序算法中平均性能最优的排序算法

快速排序兵器不适用于原本有序或基本有序的记录序列进行排序

选择排序

简单选择排序

基本思想：假设排序表为L[1…n],第i趟排序即从L[i…n]中选择关键字最小的元素与L[i]交换

简单来说就是比如我们要找到最小的元素，放到当前排序的第一个位置
第一趟排序找出最小的元素09 放到第一个位置，就是87和09交换位置
第二趟排序就是把17交换到第二个。
第三趟排序就是把32放到第三个位置。
同理最后的结果

同理也是只需要进行n-1次排序

实例代码

参数还是一个数组和一个变量表示长度
里面通过两个for循环找出最小值，然后赋值给下标最小的数

空间效率：O（1）
时间效率： O(n^2^)
稳定性：不稳定

堆排序算法

什么是堆？
观察上面两个例子
先来看左边的，发现是一颗二叉树，即下面的关键字序列以顺序存储的方式构造的一棵二叉树。
观察一下这棵二叉树。发现根节点为2，比左孩子和右孩子都要小。
而以4为结点的这棵二叉树，4是比85和9都小的
得出结论，双亲都是比孩子要小，最小的结点存放在根节点上。
对于这棵二叉树就称为堆
左边的堆称为小根堆，因为最小的元素存放在根节点。
同理我们也可以得出大根堆的概念。

构造大根堆