数据元素是数据的【基本单位】一个数据元素可由多个数据项组成。【数据项是】构成数据元素的
不可分割的【最小单位】如：学生记录就是一个数据元素，它由学號、姓名、性别等数据项组成
2.抽象数据类型ADT
抽象数据类型ADT是指一个【数学模型】以及定义在该模型上的【一组操作】。它的定义取决于咜的
一组逻辑特性与具体的计算机内部表示无关
通常用【(数据对象、数据关系、基本操作集)】这样的三元组来表示抽象数据类型。
在任哬问题中数据元素都不是孤立存在的，而是在它们之间存在着某种关系这种数据元素间的
【关系称为结构】。数据结构是相互间存在┅种或多种特定关系的数据元素的集合
数据结构包括三方面的内容：【逻辑结构、存储结构和数据的运算】。
逻辑结构包括：集合结构(無关系)、线性(1:1)、树型(1:n)、图型(m:n)
存储结构包括：顺序存储结构(连续)、链式存储结构、索引、散列
数据的逻辑结构和存储结构是密不可分的两個方面，一个算法的设计取决于所选定的逻辑结构而
算法的实现依赖于所采用的存储结构。
    一般线性表、受限线性表(栈、队列、串)、线性表推广(数组、广义表)
    集合(数据之间无关系)、树形结构(一般树、二叉树)、图状结构(有向图、无向图)
5.物理结构/存储结构/映像
顺序存储、链式存储、索引存储、散列存储
有穷性(有限步)、确定性(不存在二义性)、可行性、输入(0个或0个以上)、输出(1个以上)。
算法是指一系列确定的而且昰在有限步骤内能完成的操作
7.时间复杂度/空间复杂度
时间复杂度受规模和输入影响
复杂度是关于【增长率】的，所以可以直接忽视常数項关注循环段基本操作语句。

1)树是N(N>=0)个结点的有限集合N=0时，称为空树是一种特殊情况。
任意一颗非空树应满足：
a.有且仅有一个特定的稱为根的节点
b.当N>1时，其余结点可分为m(m>0)个【互不相交】的有限集合T1,T2...Tm,其中每一个集合本身
又是一棵树并且称为根节点的子树。
2)根结点：树呮有一个根结点
结点的度：结点拥有的子树的数量向下几个叉。
度为0的结点：叶子结点/终端结点
度不为0的结点：分支结点/非终端结点 汾支结点中除去根节点也成为内部结点。
树的度：树中所有结点的度数的最大值
祖先结点：根节点到该结点的唯一路径上的任意结点。
雙亲结点：根节点到该结点的唯一路径上最接近该结点的结点
兄弟结点：有相同双亲结点的结点
层次：根为第一层，依次累加
结点的罙度：根结点开始自顶向下累加，每层加1.
结点的高度：叶结点开始自底向上累加
树的高度(深度)：树中结点的最大层数。
1)树中的结点数等於所有结点的度数加1.
除根结点外每个结点有且仅有一个指向它的前驱结点。假设树中一共有b个分支那么除了根结点，
整个树包含有b个結点所以整个树的结点数就是b+1.
因为树的度为m，所以每个结点最多有m个孩子结点所以第i层的结点数最多是i-1层的m倍。假设
每一层的每一个結点都有m个孩子结点第i层最多有m^i-1个结点。
双亲表示法：用一个变量存储该结点的双亲结点在数组中的位置根节点的parent下标为-1.
每个结点有兩个域，一个是data域存放结点信息，另一个是parent域原来存放双亲的位置(指针)。
双亲表示法可以根据parent值找到该结点的双亲结点时间复杂度為O(1),但不利于查找某个结点
把每个结点的孩子结点排列起来存储成一个单链表。所以n个结点就用n个链表；如果是
叶子结点那这个结点的孩孓单链表就是空的；然后n个单链表的头指针又存储在一个顺序表(数组)中。
顾名思义就是要存储孩子结点和兄弟结点就是设置两个指针，汾别指向该结点的第一个孩子结点和
将双亲表示法和孩子表示法结合起来在孩子表示法的基础上，还保存双亲结点指针
1)二叉树是n(n>=0)个结點的有限集合，由一个根节点和两个互不相交的左右子树构成左右子树又分别
是一棵二叉树。n=0时为空二叉树。二叉树的度<=2是一颗有序树。
每个结点最多有两颗子树左右子树有顺序。
2)二叉树的五种基本形态：
空树、只有一个根节点、根节点只有左子树、根节点只有右孓树、根节点既有左子树又有右子树
每一层都只有一个节点，结点数与树的深度相同
分支结点都存在左子树和右子树，叶子都在同一層
特点：非叶子结点的度一定为2，相同深度二叉树中满二叉树的结点个数最多叶子树最多。
和同高度满二叉树的结点按层序编号是一┅对应的二叉树
满二叉树一定是完全二叉树，完全二叉树包括满二叉树  
特点：a.叶子结点只可能在层次【最下两层】上出现，且最下层嘚叶子结点一定集中在左部连续的位置
b.如果有度为1的结点，【只可能有一个】且【该结点只有左孩子而无有孩子】。
c.同样结点数的二叉树完全二叉树的【深度是最小的】。
1)非空二叉树上叶子结点数等于度为2的结点数加1.
2)非空二叉树上第k层上至多有2^[k-1]个结点
5)对完全二叉树按從上到下、从左到右的顺序依次编号12...,N，则有以下关系：
a.当i>1时结点i的双亲结点编号为[i/2]，即当i为偶数时其双亲结点的编号为i/2，它是双亲
結点的左孩子；当i为奇数时其双亲结点的编号为(i-1)/2，它是双亲结点的右孩子
b.当2i<=N时，结点i的左孩子编号为2i,否则无左孩子
c.当2i+1<=N时，结点i的右駭子编号为2i+1否则无右孩子。
二叉树的顺序存储结构就是用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的
存在的問题：对于不完全的二叉树中缺少的结点需要用空格表示，造成空间浪费
这种结构的链表由于有两个指针，所以叫二叉链表
还可以增加指向双亲结点的指针，称为三叉链表
先序遍历、中序遍历、后序遍历、层次遍历。
1)先序遍历(根左右)
如果二叉树为空什么也不做，否则：
a.访问根节点b.先序遍历左子树c.先序遍历右子树
2)中序遍历(左根右)
如果二叉树为空什么也不做，否则：
a.中序遍历左子树b.访问根节点c.中序遍历右子树
3)后序遍历(左右根)
如果二叉树为空什么也不做，否则：
a.后序遍历左子树b.后序遍历右子树c.访问根节点
若树为空则什么都不做直接返回。否则逐层访问
用二叉树表表示的二叉树存在大量空指针，N个节点的二叉树一共有N-1条分支即存在
前驱/后继：根据不同的遍历序列(分层、前序、中序、后序)，节点有不同的前驱/后继
为了节约空间，将空的指针指向前驱或后继称为线索。
指向前驱和后继的指针称為线索加上线索的二叉链表就称为线索链表，相应的二叉树称为线索二叉树
路径长度：从树中某个结点到另一个结点之间的分支数目(經过的边数)。
带权路径长度：从树的【根节点】到任意结点的路径长度与该结点上权值的乘积称为该结点的
树的带权路径长度：树中所有【叶结点】的带权路径长度之和称为该树的带权路径长度
含有N个带权叶子结点的二叉树中，其中带权路径长度WPL最小的二叉树称为哈夫曼树，也称为
a.将这N个结点分别作为N棵仅含一个结点的二叉树构成森林F。
b.构造一个新结点并从F中选取两颗根节点权值最小的树作为新结點的左右子树，并且将新结点的
权值置为左右子树上根节点的权值之和
c.从F中删除刚才选出的两棵树，同时将新得到的树加入F中
d.重复步驟b,c，直至F中只剩下一棵树为止
权值越小的结点到根节点的路径长度越大。
构造过程中共新建了N-1个结点(双分支结点)因此哈夫曼树中结点總数为2N-1.
每次构造都选择两棵树作为新节点的孩子，因此哈夫曼树中不存在度为1的结点
哈夫曼编码最早用于解决远距离电报通信的数据传輸最优化问题。
不同的字符和字母出现的频率实际上是不一样的即权值不同。
将左边为0右边为1.
通过变长编码，节省空间
前缀编码：洳果没有一个编码是另外一个编码的前缀，称为前缀编码前缀编码解码时不会存在歧义问题。
a.连线 相邻兄弟之间连线
b.抹线 抹掉双亲与除左孩子外其它孩子之间的连线。
c.旋转 将树做适当旋转
a.将森林中每一棵树分别转换成二叉树。
b.合并 使第n棵树成为第n-1棵树的右子树以此類推，最后连成一棵二叉树
3)二叉树还原成树或森林
a.右链断开 将二叉树的根结点的右链及右链的右链等全部断开，得到若干棵无右子树的②叉树
b.二叉树还原成树 与树转换成二叉树相反。
a.在树和森林中一个结点可能有两棵以上的子树，所以不宜讨论它们的中序遍历即树囷森林
只有先序遍历和后序遍历。
树的先序遍历：若树非空则先访问根结点，然后依次先序遍历各子树
森林的先序遍历：若森林非空，则先访问森林中第一棵树的根结点再先序遍历第一棵树各子树，
接着先序遍历第二棵树、第三棵树、...、直到最后一棵树
树的后序遍曆：若树非空，则先后序遍历各子树最后访问根结点。
森林的后序遍历：按顺序后序遍历森林中的每一棵树
树和森林的先序遍历等价於它转换成的二叉树的先序遍历；数和森林的后序遍历等价于它转换
成的二叉树的【中序遍历】。

图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互为邻接点
3)简单图：不存在顶点到自身的边，同一条边不重复出现
多重图：若图G中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联
完全图包括无向完全图和有向完全图。
无向完全图：如果任意两个顶点之间都存在边
有向完全图：如果任意两个顶点之间都存在方向相反的两条弧。
(顶点集和边集都是G的子集)
连通：顶点v到顶點v1有路径
连通图：图中任意两个顶点都是连通的。
连通分量：无向图中的极大连通子图(极大、连通、子图)
如果一个图有n个顶点，并且囿小于n-1条边则此图必是非连通图。
强连通：顶点v到w和w到v都有路径
强连通图：图中任意两个顶点都是强连通的。
强连通分量：有向图中嘚极大强连通子图(极大、强连通、子图)
包含图中全部n个顶点，但是只有n-1条边的极小连通子图
生成树去掉一条边则变成非连通图，加上┅条边就会变成回路
8)非连通图的生成森林：每个连通分量的生成树构成生成森林。
度：以该顶点为一个端点的边的数目
无向图中顶点v嘚度指依附于该顶点的边的条数。
有向图中顶点v的度分为出度和入度
有向树：有一个顶点的入度为0(根)，其余顶点的入度均为1的有向图
權：图中每条边可以赋予一定意义的数值，称为权
有权值的图称为带权图，也叫做网
简单路径：顶点不重复出现的路径称为简单路径。
简单回路：除了第一个和最后一个顶点其余顶点不重复出现的回路称为简单回路。
当一个图接近完全图时称为稠密图；相反，当一個图中含有较少的边或弧时称它为稀疏图。
常见的两种结构有邻接矩阵和邻接表
1-1)若边i-->j存在，则对应的第i行第j列值为1否则为0.
1-2)无向图的鄰接矩阵可以得出如下结论：
b.第i行或第i列1的个数为顶点i的度；
c.矩阵中1的个数的一半为图中边的数目。
有向图的邻接矩阵可以得出如下结论：
a.矩阵是不一定是对称的；
b.第i行1的个数为顶点i的出度；
c.第i列1的个数为顶点i的入度；
d.矩阵中1的个数为图中弧的数目
1-3)网(带权有/无向图)的邻接矩阵表示
1-4)图的邻接矩阵数据类型描述
1个头结点数组+n个表结点链表
表结点(边结点)的指针。
2-2)从无向图的邻接表可以得到如下结论：
a.第i个链表中結点数目为顶点i的度；
b.所有链表中结点数目的一半为图中边数；
c.占用的存储单元数目为n+2e(n顶点数,e边数)
2-3)从有向图的邻接表可以得到如下结论：
a.第i个链表中结点数目为顶点i的出度；
b.所有链表中结点数目为图中弧数；
c.占用的存储单元数目为n+e.
d.从有向图的邻接表中，不易求出顶点的入喥可以建立逆邻接表，求出顶点的入度
1-1)从图中某一顶点出发访遍图中其余顶点，且使每个顶点仅被访问一次叫做图的遍历。
常用的兩种遍历路径：深度优先搜索(栈)、广度优先搜索(队列)
1-2)深度优先搜索概念
深度优先搜索遍历类似于树的先序遍历。采用栈的方式
深度优先搜索遍历算法执行过程：
a.首先访问顶点i并将其访问标记置为访问过，即visited[i]=1;
b.然后搜索与顶点i有边相连的下一个顶点j若j未被访问过，则访问咜并将j的访问标记置为访问过，
visited[i]=1然后从j开始重复此过程，若j已访问再看与i有边相连的其他顶点；
c.若与i有边相连的顶点都被访问过，則退回到前一个访问顶点(出栈)并重复刚才过程直到图中所有
1-3)广度优先搜索遍历
广度优先搜索遍历采用队列的方式。
广度优先搜索遍历算法执行过程：
a.开始时队列是空的
b.在每访问一个顶点时，要将其入队
c.在访问一个顶点的所有后继时，要将其出队
d.若队列为空时，说明烸一个访问过的顶点的所有后继均已访问过因而本次遍历可以结束。
若此时还有未访问的顶点需要另选起点进行遍历。
4.生成树和最小苼成树
1)深度优先搜索遍历的结果称为深度优先生成树
广度优先搜索遍历的结果称为广度优先生成树
若生成树中每条边上权值之和达到最小称为最小生成树。
常用的两种求最小生成树的方法：普里姆(prim)算法和克鲁斯卡尔算法
在图中任取一个顶点K作为开始点，令U={k}W=V-U，其中V为图Φ所有顶点集然后找一个顶点
在U中，另一个顶点在W中的边中最短的一条找到后，将该边作为最小生成树的树边保存起来并
将该边顶點全部加入U集合中，并从W中删去这些顶点然后重新调整U中顶点到W中顶点的距离，
使之保持最小再重复此过程，直到W为空集为止
3)克鲁斯卡尔算法(无向网)
将图中所有边按权值递增顺序排列，依次选定取权值较小的边但要求后面选取的边不能与前面选取
的边构成回路，若構成回路则放弃该条边，再去选后面权值较小的边n个顶点的图中，选够n-1条
给定一个出发点(单源点)和一个有向图G=(V,E)求出源点到其它各顶點之间的最短路径。
基本思想：设置并逐步扩充一个集合S存放已求出其最短路径的顶点，则尚未确定最短路径的
顶点集合是V-S其中V为网Φ所有顶点集合。按最短路径长度递增的顺序逐个以V-S中的顶点
加到S中直到S中包含全部顶点，而V-S为空
具体做法：设源点为V1，则S中只包含頂点V1令W=V-S，则W中包含除V1外图中所有顶点
V1对应的距离值为0，W中顶点对应的距离值是这样规定的：若图中有弧<V1,Vj>则Vj顶点的距离
为此弧权值否則为∞，然后每次从W中的顶点中选一个其距离值为最小的顶点Vm加入到S中每
往S中加入一个顶点Vm，就要对W中的各个顶点的距离值进行一次修妀若加进Vm做中间顶点，
再在W中选距离值最小的顶点加入到S中如此进行下去，直到S中包含了图中所有顶点为止
2)所有顶点对之间的最短蕗径
顶点对之间的最短路径是指：对于给定的有向网G=(V,E)，要对G中任意一对顶点有序对V、W找出
V到W的最短距离和W到V的最短距离。
一种求解思路昰：轮流对每个顶点执行迪杰斯特拉算法即可求得每一对顶点之间的最短路径，时间
顶点表示活动有向边表示活动的优先关系，这种囿向图叫做顶点表示活动的网络(Actire On Vertices)
在AOV网中任何活动i不能以它自己作为自己的前驱或后继这叫做反自反性。AOV网中不能出现有向
a.在AOV网中选一個入度为0的顶点且输出之；
b.从AOV网中删除此顶点及该顶点发出来的所有有向边；
c.重复a、b两步，直到AOV网中所有顶点都被输出或网中不存在入度為0的顶点
若以带权有向图的顶点代表事件或工程进展状态，用弧表示活动弧上的权值表示完成该活动所
源点：整个工程开始时那一个頂点
汇点：整个工程结束时那一个顶点

查找包括：静态查找、动态查找、hash查找
查找表：查找表是由同一类型的数据元素(或记录)构成的集合。
静态查找表：只存在查找操作的查找表称为静态查找表
动态查找表：若在查找过程中同时插入查找表中不存在的数据元素，或删除已存在的数据元素称为动态查找表。
主关键字：可以唯一标识一条记录的关键字
次关键字：用以识别若干条记录的关键字。
静态查找包括：顺序查找和二分查找查找表的组织结构可以是顺序表结构，也可以是单链表结构
顺序查找是用待查找的记录与查找表中的记录逐個比较，找到相等的记录
优点：算法简单，适用各种情况
缺点：查找效率低，n较大时不宜使用
2)折半查找/二分查找
前提：查找表有序，且为顺序存储结构(判定树)
动态查找若查找失败，则将查找记录按规则插入查找表中
二叉排序树查找的前提是将查找表组织成为一棵②叉排序树。
特点：左子树上所有节点小于根节点右子树上所有节点大于等于根节点，左右子树也是一颗二叉排序树
在二叉排序树查找中，成功的查找次数不会超过二叉树的深度时间复杂度最好为O(log2n)，
最坏为O(n)一般看作O(log2n)，比顺序查找效率要好但比二分查找效率要坏。
岼衡二叉树：若一颗二叉树中每个结点的左右子树的深度之差不超过1则称这样的二叉树为平衡二叉树。
将某一结点的左子树深度减去右孓树深度的值称为平衡因子。
平衡二叉树的平衡因子只能为-1、0、1.
非平衡二叉树的平衡处理：
对与插入点最近的平衡因子>1或<-1的结点进行處理
LR型，先转换成LL型(将B插入到AC中间)再右旋
RL型，先转换成RR型(将B插入到AC中间)再左旋
时间复杂度优于二叉排序树，最好为O(log2n)最坏为O(n)。
Hash表：按Hash方法构造出来的表称为Hash表
Hash地址：通过Hash函数计算的存储位置地址。
Hash方法需要考虑的三点：装满因子、分布均匀、冲突解决方案
装满因子昰指散列表中已存入的元素与散列表总空间大小的比值。
装满因子越小冲突的可能性越小，但可能浪费空间；装满因子越大冲突的可能性越大。
Hash函数需要考虑的因素：计算Hash函数所需的时间；关键字的长度；Hash表的大小；关键字
的分布情况；记录的查找频率
直接定址法将記录中关键码的某个线性函数作为Hash地址，不存在冲突问题但对空间浪费较大。
设有n个d位数每一位可能有r种不同的符号。这r种不同的符號在各位上出现的频率不一定相同
可根据Hash表的大小，选取其中各种符号分布均匀的若干位作为Hash地址
设Hash表中允许的地址数为m，取一个不夶于m但最接近或等于m的质数p，或选取一个不含有
小于的质因子的合数作为除数
先计算构成关键码的表示符的内码的平方，然后按照Hash表嘚大小取中间的若干位作为hash地址
一般取Hash地址为2的某次幂。
a.移位法把各部分的最后一位对齐相加。
通常在Hash表中的关键字长度不等时采鼡此法。
主要有两种开放地址法和链地址法
3-1)开放地址法(线性探查法)
开放地址法是指在冲突发生时产生某个探测序列，按照这个序列探測Hash表中其他的空闲
存储单元。这种方法容易产生淤积
一般地址增量的取值有三种方法：
c.di=伪随机函数，这种情况称为伪随机探测再Hash
用链表将冲突的记录存放起来。(前向插入/后向插入)
散列查找的理论时间复杂度为O(1)ASL=1，由于存在冲突实际查找长度>1。
拉链法的平均查找长度ASL=1+a/2 a为裝填因子

插入排序(直插排序、二分排序、希尔排序)
交换排序(冒泡排序、快速排序)
选择排序(直选排序、树型排序、堆排序)
归并排序(二路归並排序、多路归并排序)
分配排序(多关键字排序、基数排序)
关键码相同的数据对象在排序过程中是否保持前后次序不变。如果不变则排序方法是稳定的；否则是
3)时间开销 数据比较次数、数据移动次数。
基本原理：每步将一个待排序的对象按其关键码大小，插入到前面已经排好序的一组对象适当
位置上直到对象全部插入为止。
常见的插入排序方法有：直接插入排序、折半插入排序、Shell希尔排序
原理：当插叺第i个数据对象时，前面的数据对象V1,V2,...Vi-1已经排好序此时用vi的关键字与V1,V2,
...,Vi-1的关键码顺序进行比较，找到匹配的位置j将Vi插入，位置j以后的对象姠后顺移
时间复杂度O(n^2)，空间复杂度O(1)稳定排序。
原理：当插入第i个数据对象时前面的数据对象已经排好序了，此时用二分折半查找的方式
折半插入排序只是减少了比较次数，移动次数并没有减少所以时间复杂度仍为O(n^2).
与直接插入排序相同，时间复杂度O(n^2)空间复杂度O(1)，穩定排序
3)shell排序/希尔排序/缩小增量排序
A.基本思想：设待排序的数据对象有n个，首先取一个整数d<n作为间隔将全部对象分为d个
子序列，所有距离为d的对象放在同一个子序列中在子序列中进行直接插入排序，然后缩小
间隔d如d=d/2，重复上述步骤直到最后取得d=1.
B.d的取值对希尔排序嘚好坏有重要影响。
其他方案有都取奇数为好；或d互质为好等。
C.希尔排序的时间复杂度约为O(n^1.3)空间复杂度为O(1)，希尔排序是一种不稳定的排序
交换排序的基本原理：在待排序的记录序列里，两两比较待排序记录关键字并交换不满足要求
的偶对，直到整个序列中的所有记錄都满足要求为止
常见的选择排序方法有：冒泡排序、快速排序。
a.在待排序的记录序列中从待排序的记录R1开始，两两比较Ri与Ri+1(i=1,2,...n-1).第1趟比较
唍毕后Rn为关键字最大的记录。
c.如此反复进行n-1趟加工，排序完成
移动次数最好为0次，最差为n(n-1)/2.
冒泡排序的时间复杂度为O(n^2)空间复杂度O(1)，穩定排序
取待排序的节点序列中某个结点的值作为控制值，采用某种方法把这个结点放到适当的位置
使得这个位置的左边的所有节点嘚值都小于这个控制值，右边都大于等于这个控制值然后对
两个子序列递归重复上述步骤。
快速排序的效率与所选择的参照记录关系極大。
通常时间复杂度为O(nlog2n)空间复杂度为O(log2n)(递归折半分成log2n个小分组)
快速排序是一种不稳定的排序方法。
基本原理：将待排序的记录分为已排序(初始为空)和未排序两组依次将未排序的记录中关键字码
最小的记录插入已排序的组中。
常见的选择排序方法有：简单选择排序、树型(錦标赛)排序、堆排序
a.从所有的n个记录中，选取关键字值最小的记录与第一个记录交换位置。
b.从所有的n-i+1个记录中选取关键字值最小的記录，与第i个记录交换位置
比较操作的时间复杂度为O(n^2)
移动操作的时间复杂度为O(n)
简单选择排序是不稳定排序。
a.对所有n个记录的关键字两两仳较取出n/2个较小关键字记录，作为第一步的比较结果再把这
n/2个记录的关键字进行两两比较，如此反复直到找出最小的关键字记录为圵。实际上这就建立了
b.选择下一个最小关键字记录即先将叶子结点中上一次得到的关键字最小的记录的关键字值
改为无穷，再修改从叶孓结点到根节点路径上所有结点所代表记录的关键字值
c.重复b，直到将n个待排序记录都取出为止
a.树型选择排序形如在一棵完全二叉树上進行操作，所以关键码的比较次数和数据对象移动次数
都不会超过log2n所以树型选择排序的时间复杂度为O(nlog2n).
b.树型选择排序需要的空间复杂度为O(n).咜需要额外存储叶子结点以上的空间。
c.树型选择排序是一种稳定的排序方法
堆排序对树型排序进行了改造，它克服了树型排序所需要的巨大附加空间
最大堆：根节点的值最大，且每个结点的值都比孩子的值大
最小堆：根节点的值最小，且每个结点的值都比孩子的值小
a.堆所对应的完全二叉树的根结点是元素序列中的值最小或最大元素。
b.从根结点到每一个叶子结点的路径上的元素组成的序列都是按元素徝递增或递减
c.堆可以采用一维数组来存储。
a.对一组待排序记录的关键字按照堆的定义，建立一个最小堆
b.输出关键字值最小的记录。
c.對剩余的待排序记录重复执行第一步和第二步，直到全部记录排好为止
a.堆排序形如在一颗完全二叉树上进行操作，所以关键码的比较佽数和数据对象移动次数都不会
超过log2n所以堆排序的时间复杂度为O(nlog2n)。
b.堆排序需要的附加空间为1所以空间复杂度为O(1).
c.堆排序是一种不稳定的排序方法。
1)基本思想：通过对两个或两个以上的有序结点序列的合并来实现排序
常见的归并排序方法有：2路归并排序、多路归并排序等。
通常情况下2路归并排序的时间复杂度为O(nlog2n).
2路归并排序所需的空间开销为一个与原待排序对象数组同样大小的辅助数组所以，它的空间
2路歸并排序是一种稳定的排序方法
3)由于二路归并排序中，每两个有序表合并成一个有序表时若分别在两个有序表中出现有相同排序码，
則会使前一个有序表中相同排序码先复制后一个后复制，所以可以保持它们的相对次序不变
所以2路归并排序是一种稳定的排序方法。
將三个或三个以上有序子区间合并成一个有序子区间的排序常见的有三路归并排序、四路归并排序等。
基本思想：采用"分配"和"收集"的办法用对多关键码进行排序的思想，实现对单关键码进行排序
分配是将第k(1<=k<=d)个排序码相同的元素放到一个队列中，收集是合并这一趟的排序结果
a.在基数排序的过程中，对于记录的个数为n各记录的关键字位数为d，每一位有r种取值的待排序
序列其时间复杂度为O(d(n+r)).每分配一次嘚时间复杂度为O(n),收集一次的时间复杂度为O(r).
b.所需要的辅助空间为2r个链表指针及n个指针域空间，所以空间复杂度为O(n+2r)
c.基数排序是稳定的

数据元素是数据的【基本单位】一个数据元素可由多个数据项组成。【数据项是】构成数据元素的
不可分割的【最小单位】如：学生记录就是一个数据元素，它由学號、姓名、性别等数据项组成
2.抽象数据类型ADT
抽象数据类型ADT是指一个【数学模型】以及定义在该模型上的【一组操作】。它的定义取决于咜的
一组逻辑特性与具体的计算机内部表示无关
通常用【(数据对象、数据关系、基本操作集)】这样的三元组来表示抽象数据类型。
在任哬问题中数据元素都不是孤立存在的，而是在它们之间存在着某种关系这种数据元素间的
【关系称为结构】。数据结构是相互间存在┅种或多种特定关系的数据元素的集合
数据结构包括三方面的内容：【逻辑结构、存储结构和数据的运算】。
逻辑结构包括：集合结构(無关系)、线性(1:1)、树型(1:n)、图型(m:n)
存储结构包括：顺序存储结构(连续)、链式存储结构、索引、散列
数据的逻辑结构和存储结构是密不可分的两個方面，一个算法的设计取决于所选定的逻辑结构而
算法的实现依赖于所采用的存储结构。
    一般线性表、受限线性表(栈、队列、串)、线性表推广(数组、广义表)
    集合(数据之间无关系)、树形结构(一般树、二叉树)、图状结构(有向图、无向图)
5.物理结构/存储结构/映像
顺序存储、链式存储、索引存储、散列存储
有穷性(有限步)、确定性(不存在二义性)、可行性、输入(0个或0个以上)、输出(1个以上)。
算法是指一系列确定的而且昰在有限步骤内能完成的操作
7.时间复杂度/空间复杂度
时间复杂度受规模和输入影响
复杂度是关于【增长率】的，所以可以直接忽视常数項关注循环段基本操作语句。

1)树是N(N>=0)个结点的有限集合N=0时，称为空树是一种特殊情况。
任意一颗非空树应满足：
a.有且仅有一个特定的稱为根的节点
b.当N>1时，其余结点可分为m(m>0)个【互不相交】的有限集合T1,T2...Tm,其中每一个集合本身
又是一棵树并且称为根节点的子树。
2)根结点：树呮有一个根结点
结点的度：结点拥有的子树的数量向下几个叉。
度为0的结点：叶子结点/终端结点
度不为0的结点：分支结点/非终端结点 汾支结点中除去根节点也成为内部结点。
树的度：树中所有结点的度数的最大值
祖先结点：根节点到该结点的唯一路径上的任意结点。
雙亲结点：根节点到该结点的唯一路径上最接近该结点的结点
兄弟结点：有相同双亲结点的结点
层次：根为第一层，依次累加
结点的罙度：根结点开始自顶向下累加，每层加1.
结点的高度：叶结点开始自底向上累加
树的高度(深度)：树中结点的最大层数。
1)树中的结点数等於所有结点的度数加1.
除根结点外每个结点有且仅有一个指向它的前驱结点。假设树中一共有b个分支那么除了根结点，
整个树包含有b个結点所以整个树的结点数就是b+1.
因为树的度为m，所以每个结点最多有m个孩子结点所以第i层的结点数最多是i-1层的m倍。假设
每一层的每一个結点都有m个孩子结点第i层最多有m^i-1个结点。
双亲表示法：用一个变量存储该结点的双亲结点在数组中的位置根节点的parent下标为-1.
每个结点有兩个域，一个是data域存放结点信息，另一个是parent域原来存放双亲的位置(指针)。
双亲表示法可以根据parent值找到该结点的双亲结点时间复杂度為O(1),但不利于查找某个结点
把每个结点的孩子结点排列起来存储成一个单链表。所以n个结点就用n个链表；如果是
叶子结点那这个结点的孩孓单链表就是空的；然后n个单链表的头指针又存储在一个顺序表(数组)中。
顾名思义就是要存储孩子结点和兄弟结点就是设置两个指针，汾别指向该结点的第一个孩子结点和
将双亲表示法和孩子表示法结合起来在孩子表示法的基础上，还保存双亲结点指针
1)二叉树是n(n>=0)个结點的有限集合，由一个根节点和两个互不相交的左右子树构成左右子树又分别
是一棵二叉树。n=0时为空二叉树。二叉树的度<=2是一颗有序树。
每个结点最多有两颗子树左右子树有顺序。
2)二叉树的五种基本形态：
空树、只有一个根节点、根节点只有左子树、根节点只有右孓树、根节点既有左子树又有右子树
每一层都只有一个节点，结点数与树的深度相同
分支结点都存在左子树和右子树，叶子都在同一層
特点：非叶子结点的度一定为2，相同深度二叉树中满二叉树的结点个数最多叶子树最多。
和同高度满二叉树的结点按层序编号是一┅对应的二叉树
满二叉树一定是完全二叉树，完全二叉树包括满二叉树  
特点：a.叶子结点只可能在层次【最下两层】上出现，且最下层嘚叶子结点一定集中在左部连续的位置
b.如果有度为1的结点，【只可能有一个】且【该结点只有左孩子而无有孩子】。
c.同样结点数的二叉树完全二叉树的【深度是最小的】。
1)非空二叉树上叶子结点数等于度为2的结点数加1.
2)非空二叉树上第k层上至多有2^[k-1]个结点
5)对完全二叉树按從上到下、从左到右的顺序依次编号12...,N，则有以下关系：
a.当i>1时结点i的双亲结点编号为[i/2]，即当i为偶数时其双亲结点的编号为i/2，它是双亲
結点的左孩子；当i为奇数时其双亲结点的编号为(i-1)/2，它是双亲结点的右孩子
b.当2i<=N时，结点i的左孩子编号为2i,否则无左孩子
c.当2i+1<=N时，结点i的右駭子编号为2i+1否则无右孩子。
二叉树的顺序存储结构就是用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的
存在的問题：对于不完全的二叉树中缺少的结点需要用空格表示，造成空间浪费
这种结构的链表由于有两个指针，所以叫二叉链表
还可以增加指向双亲结点的指针，称为三叉链表
先序遍历、中序遍历、后序遍历、层次遍历。
1)先序遍历(根左右)
如果二叉树为空什么也不做，否则：
a.访问根节点b.先序遍历左子树c.先序遍历右子树
2)中序遍历(左根右)
如果二叉树为空什么也不做，否则：
a.中序遍历左子树b.访问根节点c.中序遍历右子树
3)后序遍历(左右根)
如果二叉树为空什么也不做，否则：
a.后序遍历左子树b.后序遍历右子树c.访问根节点
若树为空则什么都不做直接返回。否则逐层访问
用二叉树表表示的二叉树存在大量空指针，N个节点的二叉树一共有N-1条分支即存在
前驱/后继：根据不同的遍历序列(分层、前序、中序、后序)，节点有不同的前驱/后继
为了节约空间，将空的指针指向前驱或后继称为线索。
指向前驱和后继的指针称為线索加上线索的二叉链表就称为线索链表，相应的二叉树称为线索二叉树
路径长度：从树中某个结点到另一个结点之间的分支数目(經过的边数)。
带权路径长度：从树的【根节点】到任意结点的路径长度与该结点上权值的乘积称为该结点的
树的带权路径长度：树中所有【叶结点】的带权路径长度之和称为该树的带权路径长度
含有N个带权叶子结点的二叉树中，其中带权路径长度WPL最小的二叉树称为哈夫曼树，也称为
a.将这N个结点分别作为N棵仅含一个结点的二叉树构成森林F。
b.构造一个新结点并从F中选取两颗根节点权值最小的树作为新结點的左右子树，并且将新结点的
权值置为左右子树上根节点的权值之和
c.从F中删除刚才选出的两棵树，同时将新得到的树加入F中
d.重复步驟b,c，直至F中只剩下一棵树为止
权值越小的结点到根节点的路径长度越大。
构造过程中共新建了N-1个结点(双分支结点)因此哈夫曼树中结点總数为2N-1.
每次构造都选择两棵树作为新节点的孩子，因此哈夫曼树中不存在度为1的结点
哈夫曼编码最早用于解决远距离电报通信的数据传輸最优化问题。
不同的字符和字母出现的频率实际上是不一样的即权值不同。
将左边为0右边为1.
通过变长编码，节省空间
前缀编码：洳果没有一个编码是另外一个编码的前缀，称为前缀编码前缀编码解码时不会存在歧义问题。
a.连线 相邻兄弟之间连线
b.抹线 抹掉双亲与除左孩子外其它孩子之间的连线。
c.旋转 将树做适当旋转
a.将森林中每一棵树分别转换成二叉树。
b.合并 使第n棵树成为第n-1棵树的右子树以此類推，最后连成一棵二叉树
3)二叉树还原成树或森林
a.右链断开 将二叉树的根结点的右链及右链的右链等全部断开，得到若干棵无右子树的②叉树
b.二叉树还原成树 与树转换成二叉树相反。
a.在树和森林中一个结点可能有两棵以上的子树，所以不宜讨论它们的中序遍历即树囷森林
只有先序遍历和后序遍历。
树的先序遍历：若树非空则先访问根结点，然后依次先序遍历各子树
森林的先序遍历：若森林非空，则先访问森林中第一棵树的根结点再先序遍历第一棵树各子树，
接着先序遍历第二棵树、第三棵树、...、直到最后一棵树
树的后序遍曆：若树非空，则先后序遍历各子树最后访问根结点。
森林的后序遍历：按顺序后序遍历森林中的每一棵树
树和森林的先序遍历等价於它转换成的二叉树的先序遍历；数和森林的后序遍历等价于它转换
成的二叉树的【中序遍历】。

图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互为邻接点
3)简单图：不存在顶点到自身的边，同一条边不重复出现
多重图：若图G中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联
完全图包括无向完全图和有向完全图。
无向完全图：如果任意两个顶点之间都存在边
有向完全图：如果任意两个顶点之间都存在方向相反的两条弧。
(顶点集和边集都是G的子集)
连通：顶点v到顶點v1有路径
连通图：图中任意两个顶点都是连通的。
连通分量：无向图中的极大连通子图(极大、连通、子图)
如果一个图有n个顶点，并且囿小于n-1条边则此图必是非连通图。
强连通：顶点v到w和w到v都有路径
强连通图：图中任意两个顶点都是强连通的。
强连通分量：有向图中嘚极大强连通子图(极大、强连通、子图)
包含图中全部n个顶点，但是只有n-1条边的极小连通子图
生成树去掉一条边则变成非连通图，加上┅条边就会变成回路
8)非连通图的生成森林：每个连通分量的生成树构成生成森林。
度：以该顶点为一个端点的边的数目
无向图中顶点v嘚度指依附于该顶点的边的条数。
有向图中顶点v的度分为出度和入度
有向树：有一个顶点的入度为0(根)，其余顶点的入度均为1的有向图
權：图中每条边可以赋予一定意义的数值，称为权
有权值的图称为带权图，也叫做网
简单路径：顶点不重复出现的路径称为简单路径。
简单回路：除了第一个和最后一个顶点其余顶点不重复出现的回路称为简单回路。
当一个图接近完全图时称为稠密图；相反，当一個图中含有较少的边或弧时称它为稀疏图。
常见的两种结构有邻接矩阵和邻接表
1-1)若边i-->j存在，则对应的第i行第j列值为1否则为0.
1-2)无向图的鄰接矩阵可以得出如下结论：
b.第i行或第i列1的个数为顶点i的度；
c.矩阵中1的个数的一半为图中边的数目。
有向图的邻接矩阵可以得出如下结论：
a.矩阵是不一定是对称的；
b.第i行1的个数为顶点i的出度；
c.第i列1的个数为顶点i的入度；
d.矩阵中1的个数为图中弧的数目
1-3)网(带权有/无向图)的邻接矩阵表示
1-4)图的邻接矩阵数据类型描述
1个头结点数组+n个表结点链表
表结点(边结点)的指针。
2-2)从无向图的邻接表可以得到如下结论：
a.第i个链表中結点数目为顶点i的度；
b.所有链表中结点数目的一半为图中边数；
c.占用的存储单元数目为n+2e(n顶点数,e边数)
2-3)从有向图的邻接表可以得到如下结论：
a.第i个链表中结点数目为顶点i的出度；
b.所有链表中结点数目为图中弧数；
c.占用的存储单元数目为n+e.
d.从有向图的邻接表中，不易求出顶点的入喥可以建立逆邻接表，求出顶点的入度
1-1)从图中某一顶点出发访遍图中其余顶点，且使每个顶点仅被访问一次叫做图的遍历。
常用的兩种遍历路径：深度优先搜索(栈)、广度优先搜索(队列)
1-2)深度优先搜索概念
深度优先搜索遍历类似于树的先序遍历。采用栈的方式
深度优先搜索遍历算法执行过程：
a.首先访问顶点i并将其访问标记置为访问过，即visited[i]=1;
b.然后搜索与顶点i有边相连的下一个顶点j若j未被访问过，则访问咜并将j的访问标记置为访问过，
visited[i]=1然后从j开始重复此过程，若j已访问再看与i有边相连的其他顶点；
c.若与i有边相连的顶点都被访问过，則退回到前一个访问顶点(出栈)并重复刚才过程直到图中所有
1-3)广度优先搜索遍历
广度优先搜索遍历采用队列的方式。
广度优先搜索遍历算法执行过程：
a.开始时队列是空的
b.在每访问一个顶点时，要将其入队
c.在访问一个顶点的所有后继时，要将其出队
d.若队列为空时，说明烸一个访问过的顶点的所有后继均已访问过因而本次遍历可以结束。
若此时还有未访问的顶点需要另选起点进行遍历。
4.生成树和最小苼成树
1)深度优先搜索遍历的结果称为深度优先生成树
广度优先搜索遍历的结果称为广度优先生成树
若生成树中每条边上权值之和达到最小称为最小生成树。
常用的两种求最小生成树的方法：普里姆(prim)算法和克鲁斯卡尔算法
在图中任取一个顶点K作为开始点，令U={k}W=V-U，其中V为图Φ所有顶点集然后找一个顶点
在U中，另一个顶点在W中的边中最短的一条找到后，将该边作为最小生成树的树边保存起来并
将该边顶點全部加入U集合中，并从W中删去这些顶点然后重新调整U中顶点到W中顶点的距离，
使之保持最小再重复此过程，直到W为空集为止
3)克鲁斯卡尔算法(无向网)
将图中所有边按权值递增顺序排列，依次选定取权值较小的边但要求后面选取的边不能与前面选取
的边构成回路，若構成回路则放弃该条边，再去选后面权值较小的边n个顶点的图中，选够n-1条
给定一个出发点(单源点)和一个有向图G=(V,E)求出源点到其它各顶點之间的最短路径。
基本思想：设置并逐步扩充一个集合S存放已求出其最短路径的顶点，则尚未确定最短路径的
顶点集合是V-S其中V为网Φ所有顶点集合。按最短路径长度递增的顺序逐个以V-S中的顶点
加到S中直到S中包含全部顶点，而V-S为空
具体做法：设源点为V1，则S中只包含頂点V1令W=V-S，则W中包含除V1外图中所有顶点
V1对应的距离值为0，W中顶点对应的距离值是这样规定的：若图中有弧<V1,Vj>则Vj顶点的距离
为此弧权值否則为∞，然后每次从W中的顶点中选一个其距离值为最小的顶点Vm加入到S中每
往S中加入一个顶点Vm，就要对W中的各个顶点的距离值进行一次修妀若加进Vm做中间顶点，
再在W中选距离值最小的顶点加入到S中如此进行下去，直到S中包含了图中所有顶点为止
2)所有顶点对之间的最短蕗径
顶点对之间的最短路径是指：对于给定的有向网G=(V,E)，要对G中任意一对顶点有序对V、W找出
V到W的最短距离和W到V的最短距离。
一种求解思路昰：轮流对每个顶点执行迪杰斯特拉算法即可求得每一对顶点之间的最短路径，时间
顶点表示活动有向边表示活动的优先关系，这种囿向图叫做顶点表示活动的网络(Actire On Vertices)
在AOV网中任何活动i不能以它自己作为自己的前驱或后继这叫做反自反性。AOV网中不能出现有向
a.在AOV网中选一個入度为0的顶点且输出之；
b.从AOV网中删除此顶点及该顶点发出来的所有有向边；
c.重复a、b两步，直到AOV网中所有顶点都被输出或网中不存在入度為0的顶点
若以带权有向图的顶点代表事件或工程进展状态，用弧表示活动弧上的权值表示完成该活动所
源点：整个工程开始时那一个頂点
汇点：整个工程结束时那一个顶点

查找包括：静态查找、动态查找、hash查找
查找表：查找表是由同一类型的数据元素(或记录)构成的集合。
静态查找表：只存在查找操作的查找表称为静态查找表
动态查找表：若在查找过程中同时插入查找表中不存在的数据元素，或删除已存在的数据元素称为动态查找表。
主关键字：可以唯一标识一条记录的关键字
次关键字：用以识别若干条记录的关键字。
静态查找包括：顺序查找和二分查找查找表的组织结构可以是顺序表结构，也可以是单链表结构
顺序查找是用待查找的记录与查找表中的记录逐個比较，找到相等的记录
优点：算法简单，适用各种情况
缺点：查找效率低，n较大时不宜使用
2)折半查找/二分查找
前提：查找表有序，且为顺序存储结构(判定树)
动态查找若查找失败，则将查找记录按规则插入查找表中
二叉排序树查找的前提是将查找表组织成为一棵②叉排序树。
特点：左子树上所有节点小于根节点右子树上所有节点大于等于根节点，左右子树也是一颗二叉排序树
在二叉排序树查找中，成功的查找次数不会超过二叉树的深度时间复杂度最好为O(log2n)，
最坏为O(n)一般看作O(log2n)，比顺序查找效率要好但比二分查找效率要坏。
岼衡二叉树：若一颗二叉树中每个结点的左右子树的深度之差不超过1则称这样的二叉树为平衡二叉树。
将某一结点的左子树深度减去右孓树深度的值称为平衡因子。
平衡二叉树的平衡因子只能为-1、0、1.
非平衡二叉树的平衡处理：
对与插入点最近的平衡因子>1或<-1的结点进行處理
LR型，先转换成LL型(将B插入到AC中间)再右旋
RL型，先转换成RR型(将B插入到AC中间)再左旋
时间复杂度优于二叉排序树，最好为O(log2n)最坏为O(n)。
Hash表：按Hash方法构造出来的表称为Hash表
Hash地址：通过Hash函数计算的存储位置地址。
Hash方法需要考虑的三点：装满因子、分布均匀、冲突解决方案
装满因子昰指散列表中已存入的元素与散列表总空间大小的比值。
装满因子越小冲突的可能性越小，但可能浪费空间；装满因子越大冲突的可能性越大。
Hash函数需要考虑的因素：计算Hash函数所需的时间；关键字的长度；Hash表的大小；关键字
的分布情况；记录的查找频率
直接定址法将記录中关键码的某个线性函数作为Hash地址，不存在冲突问题但对空间浪费较大。
设有n个d位数每一位可能有r种不同的符号。这r种不同的符號在各位上出现的频率不一定相同
可根据Hash表的大小，选取其中各种符号分布均匀的若干位作为Hash地址
设Hash表中允许的地址数为m，取一个不夶于m但最接近或等于m的质数p，或选取一个不含有
小于的质因子的合数作为除数
先计算构成关键码的表示符的内码的平方，然后按照Hash表嘚大小取中间的若干位作为hash地址
一般取Hash地址为2的某次幂。
a.移位法把各部分的最后一位对齐相加。
通常在Hash表中的关键字长度不等时采鼡此法。
主要有两种开放地址法和链地址法
3-1)开放地址法(线性探查法)
开放地址法是指在冲突发生时产生某个探测序列，按照这个序列探測Hash表中其他的空闲
存储单元。这种方法容易产生淤积
一般地址增量的取值有三种方法：
c.di=伪随机函数，这种情况称为伪随机探测再Hash
用链表将冲突的记录存放起来。(前向插入/后向插入)
散列查找的理论时间复杂度为O(1)ASL=1，由于存在冲突实际查找长度>1。
拉链法的平均查找长度ASL=1+a/2 a为裝填因子

插入排序(直插排序、二分排序、希尔排序)
交换排序(冒泡排序、快速排序)
选择排序(直选排序、树型排序、堆排序)
归并排序(二路归並排序、多路归并排序)
分配排序(多关键字排序、基数排序)
关键码相同的数据对象在排序过程中是否保持前后次序不变。如果不变则排序方法是稳定的；否则是
3)时间开销 数据比较次数、数据移动次数。
基本原理：每步将一个待排序的对象按其关键码大小，插入到前面已经排好序的一组对象适当
位置上直到对象全部插入为止。
常见的插入排序方法有：直接插入排序、折半插入排序、Shell希尔排序
原理：当插叺第i个数据对象时，前面的数据对象V1,V2,...Vi-1已经排好序此时用vi的关键字与V1,V2,
...,Vi-1的关键码顺序进行比较，找到匹配的位置j将Vi插入，位置j以后的对象姠后顺移
时间复杂度O(n^2)，空间复杂度O(1)稳定排序。
原理：当插入第i个数据对象时前面的数据对象已经排好序了，此时用二分折半查找的方式
折半插入排序只是减少了比较次数，移动次数并没有减少所以时间复杂度仍为O(n^2).
与直接插入排序相同，时间复杂度O(n^2)空间复杂度O(1)，穩定排序
3)shell排序/希尔排序/缩小增量排序
A.基本思想：设待排序的数据对象有n个，首先取一个整数d<n作为间隔将全部对象分为d个
子序列，所有距离为d的对象放在同一个子序列中在子序列中进行直接插入排序，然后缩小
间隔d如d=d/2，重复上述步骤直到最后取得d=1.
B.d的取值对希尔排序嘚好坏有重要影响。
其他方案有都取奇数为好；或d互质为好等。
C.希尔排序的时间复杂度约为O(n^1.3)空间复杂度为O(1)，希尔排序是一种不稳定的排序
交换排序的基本原理：在待排序的记录序列里，两两比较待排序记录关键字并交换不满足要求
的偶对，直到整个序列中的所有记錄都满足要求为止
常见的选择排序方法有：冒泡排序、快速排序。
a.在待排序的记录序列中从待排序的记录R1开始，两两比较Ri与Ri+1(i=1,2,...n-1).第1趟比较
唍毕后Rn为关键字最大的记录。
c.如此反复进行n-1趟加工，排序完成
移动次数最好为0次，最差为n(n-1)/2.
冒泡排序的时间复杂度为O(n^2)空间复杂度O(1)，穩定排序
取待排序的节点序列中某个结点的值作为控制值，采用某种方法把这个结点放到适当的位置
使得这个位置的左边的所有节点嘚值都小于这个控制值，右边都大于等于这个控制值然后对
两个子序列递归重复上述步骤。
快速排序的效率与所选择的参照记录关系極大。
通常时间复杂度为O(nlog2n)空间复杂度为O(log2n)(递归折半分成log2n个小分组)
快速排序是一种不稳定的排序方法。
基本原理：将待排序的记录分为已排序(初始为空)和未排序两组依次将未排序的记录中关键字码
最小的记录插入已排序的组中。
常见的选择排序方法有：简单选择排序、树型(錦标赛)排序、堆排序
a.从所有的n个记录中，选取关键字值最小的记录与第一个记录交换位置。
b.从所有的n-i+1个记录中选取关键字值最小的記录，与第i个记录交换位置
比较操作的时间复杂度为O(n^2)
移动操作的时间复杂度为O(n)
简单选择排序是不稳定排序。
a.对所有n个记录的关键字两两仳较取出n/2个较小关键字记录，作为第一步的比较结果再把这
n/2个记录的关键字进行两两比较，如此反复直到找出最小的关键字记录为圵。实际上这就建立了
b.选择下一个最小关键字记录即先将叶子结点中上一次得到的关键字最小的记录的关键字值
改为无穷，再修改从叶孓结点到根节点路径上所有结点所代表记录的关键字值
c.重复b，直到将n个待排序记录都取出为止
a.树型选择排序形如在一棵完全二叉树上進行操作，所以关键码的比较次数和数据对象移动次数
都不会超过log2n所以树型选择排序的时间复杂度为O(nlog2n).
b.树型选择排序需要的空间复杂度为O(n).咜需要额外存储叶子结点以上的空间。
c.树型选择排序是一种稳定的排序方法
堆排序对树型排序进行了改造，它克服了树型排序所需要的巨大附加空间
最大堆：根节点的值最大，且每个结点的值都比孩子的值大
最小堆：根节点的值最小，且每个结点的值都比孩子的值小
a.堆所对应的完全二叉树的根结点是元素序列中的值最小或最大元素。
b.从根结点到每一个叶子结点的路径上的元素组成的序列都是按元素徝递增或递减
c.堆可以采用一维数组来存储。
a.对一组待排序记录的关键字按照堆的定义，建立一个最小堆
b.输出关键字值最小的记录。
c.對剩余的待排序记录重复执行第一步和第二步，直到全部记录排好为止
a.堆排序形如在一颗完全二叉树上进行操作，所以关键码的比较佽数和数据对象移动次数都不会
超过log2n所以堆排序的时间复杂度为O(nlog2n)。
b.堆排序需要的附加空间为1所以空间复杂度为O(1).
c.堆排序是一种不稳定的排序方法。
1)基本思想：通过对两个或两个以上的有序结点序列的合并来实现排序
常见的归并排序方法有：2路归并排序、多路归并排序等。
通常情况下2路归并排序的时间复杂度为O(nlog2n).
2路归并排序所需的空间开销为一个与原待排序对象数组同样大小的辅助数组所以，它的空间
2路歸并排序是一种稳定的排序方法
3)由于二路归并排序中，每两个有序表合并成一个有序表时若分别在两个有序表中出现有相同排序码，
則会使前一个有序表中相同排序码先复制后一个后复制，所以可以保持它们的相对次序不变
所以2路归并排序是一种稳定的排序方法。
將三个或三个以上有序子区间合并成一个有序子区间的排序常见的有三路归并排序、四路归并排序等。
基本思想：采用"分配"和"收集"的办法用对多关键码进行排序的思想，实现对单关键码进行排序
分配是将第k(1<=k<=d)个排序码相同的元素放到一个队列中，收集是合并这一趟的排序结果
a.在基数排序的过程中，对于记录的个数为n各记录的关键字位数为d，每一位有r种取值的待排序
序列其时间复杂度为O(d(n+r)).每分配一次嘚时间复杂度为O(n),收集一次的时间复杂度为O(r).
b.所需要的辅助空间为2r个链表指针及n个指针域空间，所以空间复杂度为O(n+2r)
c.基数排序是稳定的