数据结构基础概念知识点
date
May 28, 2021
Last edited time
May 31, 2021 12:47 PM
status
Published
slug
DataStructureOverView
tags
DataStructure
summary
自己用来复习用的数据结构概述..
type
Post
origin
Field
Plat
本文由 简悦 SimpRead 转码
为准备推免保研面试，对数据结构基础概念知识点作了如下总结。
参考书籍：《数据结构 (C 语言版)》 严蔚敏等 清华大学出版社
参考网页：https://blog.csdn.net/qq_31196849/article/details/78529724
以上引用侵删。
在参考网页基础上修正了错误的地方，增加了一些自己的理解和做题的笔记，删减了重复的地方。
若有错误欢迎交流修正。
1. 基本概念2. 线性结构2.1 线性表2.2 栈2.3 队列2.4 串2.5 数组和广义表3. 树形结构3.1 树3.2 二叉树3.3 树和森林3.4 霍夫曼树及其应用4. 图状结构4.1 图4.2 图的存储形式4.3 图的遍历4.4 生成树和最小生成树4.5 最短路径4.6 重连通图和关节点4.7 有向无环图及其应用5. 查找5.1 静态查找表5.2 动态查找表5.2.1 二叉排序树 / 二叉查找树 / 二叉搜索树5.2.2 平衡二叉树 / AVL 树5.2.3B - 树 / B 树5.2.4 哈希表5.3 查找总结6. 内部排序 6.1 插入排序6.2 交换排序6.3 选择排序6.4 归并排序6.5 基数排序6.6 枚举排序6.7 排序算法的一些特点7. 其他部分外部排序动态存储管理文件有效的算法设计
1. 基本概念
数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。
数据 ：所有能被输入到计算机中，且能被计算机处理的符号的集合。是计算机操作的对象的总称。
数据元素 ：数据(集合)中的一个 “个体”，数据及结构中讨论的基本单位
数据项 ：数据的不可分割的最小单位。一个数据元素可由若干个数据项组成。
数据类型 ：在一种程序设计语言中，变量所具有的数据种类。整型、浮点型、字符型等等
数据结构 ：指相互之间存在一定关系的数据元素的集合，即数据结构是一个二元 DataStructure=(D,R)，其中 D 是数据元素的集合，R 是 D 上关系的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。数据结构的基本操作的设置的最重要的准则是, 实现应用程序与存储结构的独立。实现应用程序是 “逻辑结构”，存储的是 “物理结构”。
逻辑结构 ：数据之间的相互关系。从逻辑上可以将其分为线性结构和非线性结构
集合 结构中的数据元素除了同属于一种类型外，别无其它关系。
线性结构 数据元素之间一对一的关系。包括：线性表、栈与队列、串。其特点是：
- 存在唯一一个被称作第一个的数据元素
- 存在唯一一个被称作最后一个的数据元素
- 除第一个外，每个元素有且只有一个前驱
- 除最后一个外，每个元素有且只有一个后继
树形结构 数据元素之间一对多的关系
图状结构或网状结构 结构中的数据元素之间存在多对多的关系
物理结构 / 存储结构 ：数据在计算机中的表示。物理结构是描述数据具体在内存中的存储(如： 顺序结构、链式结构、索引结构、哈希结构 )等
顺序存储结构 ：用元素在存储器中的相对位置来表示数据元素间的逻辑关系
链式存储结构 ：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系是用指针来表示的。
索引存储结构 ：采用附加的索引表的方式来存储节点信息的一种存储方式。索引表由若干索引项组成。索引存储方式中索引项的一般形式为 (关键字、地址)。其中，关键字是能够唯一标识一个节点的数据项。
散列存储方式 ：根据节点的关键字直接计算出该节点的存储地址
算法的五个特性 ： 有穷性、确定性、可行性、输入、输出
- 输入：一个算法有零个或多个输入（即算法可以没有输入），这些输入通常取自于某个特定的对象集合。
- 输出：一个算法有一个或多个输出（即算法必须要有输出），通常输出与输入之间有着某种特定的关系。
- 有穷性：一个算法必须总是（对任何合法的输入）在执行有穷步之后结束，且每一步都在有穷时间内完成。
- 确定性：算法中的每一条指令必须有确切的含义，不存在二义性。并且，在任何条件下，对于相同的输入只能得到相同的输出。
- 可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。
算法设计要求 ：正确性、可读性、健壮性、高效率与低存储量需求。
算法效率的度量 ：
时间复杂度 ：一个算法是由控制结构（顺序、分支与循环）和原操作构成，二者综合决定算法时间。为便于比较，选择基本的原操作，以原操作的重复执行次数为算法的时间度量。大 O 记号：渐进上界。
算法的执行时间与原操作执行次数之和成正比。时间复杂度有小到大：
O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)、O(n^n)。幂次时间复杂度有小到大 O(n^2)、O(n!)、O(n^n)。一般考虑最坏情况下的时间度量。
时间复杂度只是一种估计，实际耗时取决于：采取的策略、问题的规模、程序语言、编译质量、机器执行指令速度等空间复杂度 ：若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。
时间复杂度与空间复杂度之间没有必然联系。可以用时间换空间或者空间换时间
2. 线性结构
2.1 线性表
线性表指 n 个具有相同特性的数据元素元素的有限序列，是一种典型的线性结构。头结点无前驱有一个后继，尾节点无后继有一个前驱。
链表只能顺序查找，定位一个元素的时间为 O(N)，删除一个元素的时间为 O(1)
顺序表 ：线性表的顺序存储结构，数组。内存连续，构造简单，可随机存取 O(1)，按下标访问。插入和删除需平移节点，时间复杂度 O(n)。表的容量需事先确定，容易造成内存碎片。
线性链表 ：单链表。用一组任意的不一定连续的存储单元来依次存放线性表的结点。
每个结点包含两个域：
data 域是数据域，用来存放结点的值。next 是指针域，用来存放结点的直接后继的地址。不需要事先估计存储空间大小。第一个节点无前驱，用头指针
HEAD 指向开始节点 / 第一个节点。最后节点无后继，指向空指针
NULL。建表：头插法建表 (逆序)、尾插法建表 (顺序)。
查找 ：从 head 出发直到第 i 个节点。链表不是随机存取结构。
插入 ：先找到表的第 i-1 的存储位置，然后插入。新结点先连后继再连前驱。O(n)
删除 ：先找前驱 p。然后令 p–>next 指向 ai 的直接后继结点，即把 ai 从链上摘下。最后释放结点 ai 的空间. r=p->next; p->next=r->next; delete r。
静态链表 ：用一维数组来实现线性链表。容量是一定的。静态链表中指针表示的是下一元素在数组中的位置。是顺序的存储结构。静态链表在插入、删除时也是通过修改指针域来实现的。
循环链表 ：是一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。
判断一个单向链表中是否存在环的最佳方法是 快慢指针 。
涉及遍历操作时，其终止条件变为判断它们是否等于某一指定指针，如头指针或尾指针等。
双向链表 : 在单链表的每个结点里再增加一个指向其直接前趋的指针域 prior。这样就形成的链表中有两个方向不同的链。双链表一般由头指针唯一确定的，将头结点和尾结点链接起来构成循环链表，并称之为双向链表。在有序双向链表中定位删除一个元素的平均时间复杂度为 O(n), 但是若指定节点，则可以直接删除当前指针所指向的节点。而不需要像单向链表中，删除一个元素必须找到其前驱。
2.2 栈
栈 (Stack) 是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。后进先出。
顺序栈 ：顺序存储结构。top= -1 时为空栈，top=0 只能说明栈中只有一个元素，并且元素进栈时 top 应该自增
链栈 ：链式存储结构。插入和删除操作仅限制在链头位置上进行。栈顶指针就是链表的头指针。通常不会出现栈满的情况。 不需要判断栈满但需要判断栈空。
基本操作：删除栈顶元素、判断栈是否为空以及将栈置为空栈等
对于 n 各元素的入栈问题，可能的出栈顺序有 个。（卡特兰数）
判定出栈顺序是否成立：在某个数字后，所有比此数字小的数字应降序排列
堆栈溢出一般是循环的递归调用、大数据结构的局部变量导致的
经典应用 ：进制转换、括号匹配、迷宫求解、表达式求解：用于求解中缀表达式或者在前缀、中缀、后缀表达式间进行转换。
利用栈实现中缀转后缀：从左向右扫描中缀，遇到数字则加入后缀表达式，遇到运算符：
1. 若是（则入栈
2. 若是）则从栈中弹出运算符直到（
3. 若是其他，则从栈中依次弹出优先级大于等于他的运算符，若遇到（则停止，然后将他入栈。
在后缀表达式中()不出现
实现递归：多个函数嵌套调用的规则是：后调用先返回。
不是所有的递归程序都需要栈来保护现场，比方说求阶乘的，是单向递归，直接用循环去替代从 1 乘到 n 就是结果了，另外一些需要栈保存的也可以用队列等来替代。不是所有的递归转化为非递归都要用到栈。转化为非递归主要有两种方法：对于尾递归或单向递归，可以用循环结构算法代替
2.3 队列
队列 (Queue) 也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。先进先出。
顺序队列 ：顺序存储结构。当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头前一个位置，而尾指针始终指向队尾元素的实际位置
循环队列：在循环队列中进行出队、入队操作时，头尾指针仍要加 1，朝前移动。只不过当头尾指针指向向量上界(MaxSize-1)时，其加 1 操作的结果是指向向量的下界 0。除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列。故队空和队满时头尾指针均相等。因此，我们无法通过 front=rear 来判断队列 “空” 还是 “满”
链队列：链式存储结构。限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。
设尾指针的循环链表表示队列, 则入队和出队算法的时间复杂度均为 O(1)。也可以用循环链表，也是 O(1)
队空条件 ：rear==front，但是一般需要引入新的标记来说明栈满还是栈空，比如每个位置布尔值。
或者约定少用一个元素空间（似乎一般采取这种方法，此时对队列长度 = 空间数 - 1）
队满条件 ：(rear+1) % QueueSize==front，其中 QueueSize 为循环队列的最大长度
计算队列长度 ：(rear-front+QueueSize)% QueueSize
入队 ：(rear+1)% QueueSize
出队 ：(front+1)% QueueSize
假设以数组 A[N] 为容量存放循环队列的元素, 其头指针是 front, 当前队列有 X 个元素, 则队列的尾指针值为 (front+X mod N)
2.4 串
串 (String) 是零个或多个字符组成的有限序列。长度为零的串称为空串(Empty String)，它不包含任何字符。通常将仅由一个或多个空格组成的串称为空白串(Blank String) 注意：空串和空白串的不同，例如 "" 和"" 分别表示长度为 1 的空白串和长度为 0 的空串。
串的数据元素是单个字符
串的表示和实现 ：
定长顺序存储表示 ：静态存储分配的顺序表。可以以’\0’终结串，或者可以在 0 号单元记录串的长度
堆分配存储表示 ：存储空间是在程序执行过程中动态分配而得。所以也称为动态存储分配的顺序表
链式存储结构 ：使用固定大小的结点块组成链。例如每块节点有 4 个字符 + next。存储密度 = 串值所占的存储位 / 实际分配的存储位。
串的模式匹配 ：将主串称为目标串，子串称之为模式串。
暴力法：O（n*m），一般情况下 O（n+m）
KMP 算法匹配：利用模式串本身的自我重复性生成模式串每个位置的 next 函数值。匹配时，两个指针滑动，i 在主串，j 在子串。失配时 j 变为 next[j]，i 不变继续匹配，所以 i 只需要扫描一遍主串，复杂度为 O(n+m)
next 含义: 在第 1 到第 j-1 的字符串中，前缀和后缀相同的最长长度。（第一个元素对应 next[0] 为 - 1）
nextval: 在 next 的基础上，令 k=next[j], 若第 k 个字符与第 j 个相同，则令 next[j]=next[k]，否则，维持原来的不变
(注：书中定义字符串从 1 开始，所以都 + 1)
2.5 数组和广义表
数组和广义表可看成是一种特殊的线性表，其特殊在于: 表中的元素本身也是一种线性表。内存连续。根据下标在 O(1) 时间读 / 写任何元素。
二维数组，多维数组，广义表、树、图都属于非线性结构
数组
数组的顺序存储：行优先顺序（先把第一行存入，再存第二行）；列优先顺序。
数组是随机存取结构。
关联数组 (Associative Array)，又称映射(Map)、字典( Dictionary)是一个抽象的数据结构，它包含着类似于 (键，值) 的有序对。不是线性表。
矩阵的压缩 ：
对称矩阵、三角矩阵：直接存储矩阵的上三角或者下三角元素。注意区分
i>=j 和 i稀疏矩阵：三元顺序表存储、（行逻辑链接的顺序表、十字链表）
广义表
广义表（Lists，又称列表）是线性表的推广。广义表是 n(n≥0)个元素 的有限序列，其中 或者是原子项，或者是一个广义表。若广义表 LS（n>=1)非空，则 a1 是 LS 的表头，其余元素组成的表 (a2,…an) 称为 LS 的表尾。
广义表的元素可以是广义表，也可以是原子，广义表的元素也可以为空。
表头可以为表或单元素值
表尾是指除去表头后剩下的元素组成的表，所以表尾不可以是单个元素值。注意 Tail 操作。
例子：
A=( )——A 是一个空表，其长度为零。B=(e)——表 B 只有一个原子 e，B 的长度为 1。C=(a,(b,c,d))——表 C 的长度为 2，两个元素分别为原子 a 和子表 (b,c,d)。D=(A，B，C)——表 D 的长度为 3，三个元素都是广义 表。显然，将子表的值代入后，则有 D=((),(e),(a,(b,c,d)))。E=(a,E)——这是一个递归的表，它的长度为 2，E 相当于一个无限的广义表 E=(a,(a,(a,(a,…)))).三个结论：
- 广义表的元素可以是子表，而子表的元素还可以是子表。由此，广义表是一个多层次的结构，可以用图形象地表示
- 广义表可为其它表所共享。例如在上述例 4 中，广义表 A，B，C 为 D 的子表，则在 D 中可以不必列出子表的值，而是通过子表的名称来引用。
- 广义表的递归性
考点：
- 广义表是 0 个或多个单因素或子表组成的有限序列，广义表可以是自身的子表，广义表的长度
n>=0，所以可以为空表。广义表的同级元素 (直属于同一个表中的各元素) 具有线性关系
- 广义表的表头为空，并不代表该广义表为空表。广义表
()和(())不同。前者是长度为 0 的空表，对其不能做求表头和表尾的运算；而后者是长度为 l 的非空表(只不过该表中惟一的一个元素是空表)，对其可进行分解，得到的表头和表尾均是空表()
- 已知广义表
LS＝((a,b,c),(d,e,f)), 运用head和tail函数取出LS中原子e的运算是head(tail(head(tail(LS)))。根据表头、表尾的定义可知：任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表，而其表尾必定是子表。也就是说，广义表的 head 操作，取出的元素是什么，那么结果就是什么。但是 tail 操作取出的元素外必须加一个表——“（）”。tail(LS)＝((d,e,f))；head(tail(LS))=(d,e,f)；tail(head(tail(LS)))=(e,f)；head(tail(head(tail(LS))))=e。
二维以上的数组其实是一种特殊的广义表
在（非空）广义表中：
- 表头 head 可以是原子或者一个表
- 表尾 tail 一定是一个表
- 广义表难以用顺序存储结构
- 广义表可以是一个多层次的结构
3. 树形结构
3.1 树
一种非线性结构。树是递归结构，在树的定义中又用到了树的概念。数据元素间有明显的层次关系。
树 ：n(n) 个结点的有限集。在任意一颗非空树中：
- 有且仅有一个特定的成为根的节点
- 当
n>1时，其余节点可分为m个互不相交的有限集，每个集合又是一棵树。
基本术语 ：
树结点：包含一个数据元素及若干指向子树的分支；
孩子结点：结点的子树的根称为该结点的孩子；
双亲结点：B 结点是 A 结点的孩子，则 A 结点是 B 结点的双亲；
兄弟结点：同一双亲的孩子结点；
堂兄结点：同一层上结点；
结点层次 ：
根结点的层定义为 1 ；
根的孩子为第二层结点，依此类推；
树的高（深）度：树中最大的结点层
结点的度 ：结点子树的个数
树的度 ： 树中最大的结点度。
叶子结点：也叫终端结点，是度为 0 的结点；
分枝结点：度不为 0 的结点(非终端结点)；
森林：互不相交的树集合；
有序树：子树有序的树，如：家族树；
无序树：不考虑子树的顺序
计算：分支数量 = 总的结点数量 - 1 = 结点 * 度
3.2 二叉树
二叉树可以为空。二叉树结点的子树要 区分左子树和右子树 ，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。
二叉树不是树的一种特殊形式 ！！！(二叉树与树是不同的，二叉树不等价于分支树最多为二的有序树。当一个结点只包含一个子节点时，对于有序树并无左右孩子之分，而对于二叉树来说依然有左右孩子之分，所以二叉树与树是两种不同的结构。)
满二叉树 ：深度为 ⁍ 且具有 ⁍ 个结点的二叉树
完全二叉树 ：每个结点的编号与满二叉树的结点编号一一对应。(不一定满)
注意区分：二叉树、二叉查找树 / 二叉排序树 / 二叉搜索树、二叉平衡 (查找) 树
二叉平衡树肯定是一颗二叉排序树。堆不是一颗二叉平衡树。
平衡二叉树: 左右子树的高度相差不大于1
二叉树性质 ：
- 在二叉树的第 层上至多有 个结点。（归纳法）
- 深度为 的二叉树上至多含 个结点（k≥1） （求和）
- 对任何一棵二叉树，若它含有 个叶子结点、 个度为 2 的结点，则必存在关系式： 。
证明：总结点 ⁍ 又 ⁍ 所以 ⁍
完全二叉树性质 ：
- 具有 个结点的完全二叉树的深度为 。
- 叶子节点只可能在层次最大的两层上出现。
- 对任一节点，若其右子树深度为 ，则左子树深度必为 或
- 个结点的二叉树中，完全二叉树具有最小的路径长度，最多叶节点和最小深度
- 如果对一棵有 个结点的完全二叉树的结点按层序编号, 则对任一结点 , 有：
如果 ，则结点 无双亲，是二叉树的根；
如果 ，则其双亲的编号是 向下取整。
如果 ，无左孩子；否则，其左孩子是结点 。
如果 ，则结点 无右孩子；否则，其右孩子是结点 。
二叉树的存储结构
顺序存储结构 ：仅仅适用于满或完全二叉树，结点之间的层次关系由性质 5 确定。
链式存储结构 ： 三叉链表 ：左子树、右子树、父节点
二叉链表 ：每个节点存储左子树和右子树。
在有 个结点的二叉链表中，值为非空的链域的个数为 。在有 个结点的二叉链表中必定有 个链域。除根结点外，其余 个结点都有一个父结点。所以，一共有 个非空链域，其余 个为空链域。
遍历二叉树 ：使得每一个结点均被访问一次，而且仅被访问一次。非递归的遍历实现要利用栈。
先序遍历 DLR：根节点 -> 左子树 -> 右子树
中序遍历 LDR：左子树 -> 根节点 -> 右子树。必须要有中序遍历才能得到一棵二叉树的正确顺序。根据顺序可分左右。（先后序可以分上下）
后续遍历 LRD：左子树 -> 右子树 -> 根节点。需要栈的支持。
层次遍历 ：用一维数组存储二叉树时, 总是以层次遍历的顺序存储结点。层次遍历应该借助队列。
若一颗二叉树的先序和后序序列正好相反，则该二叉树高度等于其节点数，即不存在双分支节点。
对于一个表达式，前中后序遍历分别对应其前缀表示(波兰式)、中缀表示(正常表示)和后缀表示(逆波兰式)
线索二叉树 ：对二叉树所有结点做某种处理可在遍历过程中实现；检索(查找)二叉树某个结点，可通过遍历实现；如果能将二叉树线索化，就可以简化遍历算法，提高遍历速度，目的是加快查找结点的前驱或后继的速度。将非线性结构线性化。
线索化 ：
以中序遍历为例，若能将中序序列中每个结点前趋、后继信息保存起来，以后再遍历二叉树时就可以根据所保存的结点前趋、后继信息对二叉树进行遍历。对于二叉树的线索化，实质上就是遍历一次二叉树，只是在遍历的过程中，检查当前结点左，右指针域是否为空，若为空，将它们改为指向前驱结点或后继结点的线索。
加上结点前趋后继信息（结索）的二叉树称为线索二叉树。
n 个结点的线索二叉树上每个结点有 2 个指针域（指向左孩子和右孩子），总共有 2n 个指针域；一个 n 个结点的树有 n-1 条边，那么空指针域 = 2n - (n-1) = n + 1，即线索数为 n+1。指针域 tag 为 0，存放孩子指针，为 1，存放(左)前驱 / (右)后继节点指针。线索树下结点 x 的前驱与后继查找：设结点 x 相应的左（右）标志是线索标志，则
lchild(rchild) 就是前驱 (后继），否则：LDR–前驱：左子树中最靠右边的结点；后继：右子树中最靠左边的结点
LRD–前驱：右子树的根，若无右子树，为左子树跟。后继：x 是根，后继是空；x 是双亲的右孩子、x 是双亲的左孩子，但双亲无右孩子，双亲是后继；x 是双亲的左孩子，双亲有右孩子，双亲右子树中最左的叶子是后继
DLR–对称于 LRD 线索树—将 LRD 中所有左右互换，前驱与后继互换，得到 DLR 的方法。
为简化线索链表的遍历算法，仿照线性链表，为线索链表加上一头结点，约定：
头结点的 lchild 域：存放线索链表的根结点指针；
头结点的 rchild 域: 中序序列最后一个结点的指针；
中序序列第一结点 lchild 域指向头结点;
中序序列最后一个结点的 rchild 域指向头结点;
中序遍历的线索二叉树以及线索二叉树链表示意图
一棵左右子树均不空的二叉树在前序线索化后, 其中空的链域的个数是 1。前序和后续线索化后空链域个数都是 1，中序是 2。二叉树在线索化后，仍不能有效求解的问题是前序求前序先驱，后序求后序后继。
中序遍历的顺序为：左、根、右，所以对于每一非空的线索，左子树结点的后继为根结点，右子树结点的前驱为根结点，再递归的执行上面的过程，可得非空线索均指向其祖先结点。在中序线索二叉树中, 每一非空的线索均指向其祖先结点。
在二叉树上加上结点前趋、后继线索后，可利用线索对二叉树进行遍历, 此时，不需栈，也不需递归。
3.3 树和森林
树的存储结构 ：
双亲表示法 ：用连续内存存储树，同时在每个结点附设指示器指示双亲位置
孩子表示法 ：多重链表，每个节点有多个指针域指向多个子树。
孩子兄弟表示法 （ 二叉树 / 二叉链表表示法 ）： 树转换成二叉树 。链表中每个结点的两指针域分别指向其第一个孩子结点和下一个兄弟结点。将树转化成二叉树：右子树一定为空。步骤：
加线：在兄弟之间加一连线
抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系
旋转：以树的根结点为轴心，将整树顺时针转 45°
树与转换后的二叉树的关系 ：左孩子，右兄弟
转换后的二叉树的先序对应树的先根遍历；
转换后的二叉树的中序对应树的后根遍历。
- 设树有
m个叶子节点，n个非叶子节点。转换为二叉树后，公有n+m个节点，每个节点有一个左指针域和一个右指针域，所有共有n+m个左指针域和n+m个右指针域，有关系式： - 空的右指针域 + 不空的右指针域 =
n+m - 不空的右 + 不空的左 = 总的不空（分支数）=
m+n-1（节点数 - 1） n个非叶子节点n个不空左m-1个不空右n+1个空右
森林转换成二叉树 ：
1. 将各棵树分别转换成二叉树
2. 将每棵树的根结点用线相连
3. 以第一棵树根结点为二叉树的根
树的遍历
先根遍历过程：
（1）访问根结点；
（2）按照从左到右的次序先根遍历根结点的每一棵树。
后根遍历过程：
（1）按照从左到右的次序后根遍历根结点的每一棵子树；
（2）访问根结点。
3.4 霍夫曼树及其应用
路径 ：从一个祖先结点到子孙结点之间的分支构成这两个结点间的路径；
路径长度 ：路径上的分支数目称为路径长度；
树的路径长度 ：从根到每个结点的路径长度之和。
结点的权 ：根据应用的需要可以给树的结点赋权值；
结点的带权路径长度 ：从根到该结点的路径长度与该结点权的乘积；
树的带权路径长度 = 树中所有叶子结点的带权路径之和；通常记作
哈夫曼树 / 最优二叉树 ：假设有 n 个权值 ，构造有 个叶子结点的二叉树，每个叶子结点有一个 作为它的权值。则带权路径长度最小的二叉树称为哈夫曼树。
前缀编码 ：在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。
霍夫曼编码 就是前缀编码，可用于快速判断霍夫曼编码是否正确。
霍夫曼树没有度为
1 的节点，一颗有 n 个叶子节点的霍夫曼树共有 2n-1 个节点，度为 2 的节点有 n-1 个，可以存储在一个大小为 2n-1 的一维数组中。霍夫曼树节点个数必为奇数。构造霍夫曼树 ：每次选权值最低的合并为为一起，权重为两者之和。
霍夫曼树的特征 / 判断是否是赫夫曼树：
是二叉树，没有度为
1 的节点，且节点值为子节点的值的和，子节点的值必然小于父节点的值，必然不小于下一层任一节点的权值4. 图状结构
4.1 图
结点之间的关系可以是任意的，图中的任意两个元素都可能相关。图中的元素具有相同特性，数据元素通常称为顶点。
简单图 ：在无向图中，关联一对顶点的无向边如果多于 1 条，则称这些边为平行边，平行边的条数称为重数。在有向图中，关联一对顶点的有向边如果多于 1 条，并且这些边的始点与终点相同 (也就是它们的的方向相同)，称这些边为平行边。含平行边的图称为多重图，既不含平行边也不包含自环的图称为简单图
无向图 ：顶点间的边为无序对
(a,b)有向图 ：顶点间的弧为有序对。
<a,b> a->b, a 为弧尾 / 初始点，b 为弧头 / 终止点网 ：每条边或弧具有与之相关数值。
度 ：与顶点 相关联的边或弧的数目称为顶点 的度 。有向图中，入 的弧数目成为入度 ，出 的弧数量称为出度 。度 = 出度 + 入度。
对于有 个顶点 条边的图，有 ，也即所有顶点的度的和必为偶数。
完全图 ：具有 个顶点和 条边的无向图，必定是连通图。
有向完全图 ：具有 个顶点和 条边的有向图，每两个顶点之间都有两条方向相反的边连接的图。
回路或环 ：第一个顶点和最后一个顶点相同的路径。
简单回路或简单环 ：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路
连通 ：顶点 至 之间有路径存在
连通图 ：无向图图 的任意两点之间都是连通的，则称 是连通图。
连通分量 ：极大连通子图，子图中包含的顶点个数极大
强连通图 ：有向图 的任意两点之间都是连通的，则称 是强连通图。各个顶点间均互相有向可达。
强连通分量 ：极大连通子图
一个无向图 是连通的，则：，而反之不成立。
一个有向图 是是强连通图，则：，而反之不成立。
没有回路的无向图是连通的当且仅当它是树，即等价于：。
子图 ：一个图的结点集和边集都是另一个图的子集，称这个图为另一个图的子图
支撑子图 / 生成子图 ：由一个图的全部顶点及连结这些顶点的部分边构成的连通图称为原图的支撑子图。
支撑树 ：形状为树的支撑子图，往往不唯一
最小支撑树 / 生成树 ：极小连通子图。包含图的所有 个结点，但只含图中足以构成树的 条边。性质：有 个顶点的生成树必有 条边，如少则不连通，多则必成环。但有 条边不一定是树。
4.2 图的存储形式
邻接矩阵： 用
01 表示是否有边或者弧无权有向图：出度:
i 行之和；入度: j 列之和。无权无向图：
i 结点的度: i 行或 i 列之和。加权邻接矩阵：相连为
w，不相连为 无向图邻接矩阵的
m 幂次（矩阵乘法）中非零元素的意义是图中从 i 到 j 长度为 m 的路径的条数。邻接表： 链式存储结构。每个顶点有一条单链表，链上的结点表示与该顶点相关联的边，或者从该顶点出发的弧。
n 个顶点的无向图的邻接表最多有 n(n-1) 个边表结点。在边稀疏的情况下，使用邻接表表示比邻接矩阵省空间
（十字链表表示、邻接多重表表示）
4.3 图的遍历
深度优先搜索
DFS 利用栈，广度优先搜索 BFS 利用队列求一条从顶点
i 到顶点 s 的简单路径 使用深度优先搜索求两个顶点之间的一条长度最短的路径 使用广度优先搜索
当各边上的权值均相等时,
BFS 算法可用来解决单源最短路径问题。4.4 生成树和最小生成树
每次遍历一个连通图将图的边分成遍历所经过的边和没有经过的边两部分，将遍历经过的边同图的顶点构成一个子图，该子图称为生成树。因此有 DFS 生成树和 BFS 生成树。
最小生成树 ：生成树中边的权值 (代价) 之和最小的树。最小生成树问题是构造连通网的最小代价生成树。
避圈法（Kruskal 算法） ：令最小生成树集合 T 初始状态为空，在有 n 个顶点的图中选取代价最小的边并从图中删去。若该边加到 T 中有回路则丢弃，否则留在 T 中；依此类推，直至 T 中有
n-1 条边为止。在边较少时适用Prim 算法 ：先加入最小的边作为开始, 然后加入与当前结构联通的最小边.
4.5 最短路径
最短路径—Dijkstra 算法和 Floyd 算法Prim 算法、Kruskal 算法和 Dijkstra 算法均属于贪心算法。
Dijkstra 算法解决的是带权重的有向图上单源最短路径问题，该算法要求所有边的权重都为非负值。时间复杂度为 O（N*N）
(Bellman-Ford 算法，边的权重可以为负值。)
4.6 重连通图和关节点
若从一个连通图中删去任何一个顶点及其相关联的边，它仍为一个连通图的话，则该连通图被称为重（双）连通图。
若连通图中的某个顶点和其相关联的边被删去之后，该连通图被分割成两个或两个以上的连通分量，则称此顶点为关节点 / 割点。
没有关节点的连通图为双连通图
深度优先生成树的关节点特性：
若生成树的根结点，有两个或两个以上的分支，则此顶点 (生成树的根) 必为关节点；
对生成树上的任意一个非叶 “顶点”，若其某棵子树中的所有 “顶点” 没有和其祖先相通的回边，则该 “顶点” 必为关节点。
4.7 有向无环图及其应用
无环的有向图称作有向无环图，简称 DAG 图 。
偏序与全序
拓扑排序 ：由一个集合上的偏序得到该集合上的一个全序，得到的全序称为拓扑有序
AOV 网 (Activity On Vertex)：用顶点表示活动，边表示活动的优先关系的有向图称为 AOV 网。AOV 网中不允许有回路，因为回路这意味着某项活动以自己为先决条件。
拓扑有序序列 ：把 AOV 网络中各顶点按照它们相互之间的优先关系排列一个线性序列的过程。若 是 前驱，则 一定在 之前；对于没有优先关系的点，顺序任意。
AOE 网（activity on edge） ：用边表示活动，用于估算工程完成的时间。工程完成的时间是从启示点到终止点的最长路径的长度。这条路径最长的路径称为关键路径
5. 查找
顺序查找、折半查找、索引查找、分块查找是静态查找，动态查找有二叉排序树查找，最优二叉树查找，键树查找，哈希表查找
平均查找长度 ASL：在成功查找的前提下，需要和被查找值进行比较的关键字的个数的期望值。（也可以在不成功查找的情况下讨论）
5.1 静态查找表
只实现查找，不实现插入和删除
顺序查找 ：从表的一端开始逐个进行记录的关键字和给定值的比较。适用于无序的顺序表或线性链表
折半查找 / 二分查找 ：用于顺序有序表。平均查找时间约为。用顺序方式存储且结点按关键字有序排序。每次查找 (low+high)/2，向下取整（不是向上）
（静态树表的查找：根据元素被查找的概率构建查找数）
分块查找 ：将表分成几块，块内无序，块间有序，即前一块中的最大值小于后一块中的最小值。并且有一张有序索引表，每一项存放每一块的最大值和指向该块第一个元素的指针。块间查找用二分查找，块内用顺序查找，效率介于顺序和二分之间；
当每块含有的数据量 s 为 sqrt(n) 时, ASL 最小。在分块查找时，先查找索引表，再查找块表。
比较 ：
时间：顺序查找最差，二分最好，分块介于两者之间
空间：分块最大，需要增加索引数据的空间
分块时数据块之间在物理上可不连续。所以可以达到插入、删除数据只涉及对应的块；另外，增加了索引的维护。
5.2 动态查找表
5.2.1 二叉排序树 / 二叉查找树 / 二叉搜索树
空树或具有以下性质的二叉树：
若其左子树非空，则左子树上所有节点的值均小于根节点的值
若其右子树非空，则右子树上所有节点的值均大于根节点的值
其左右子树也为二叉排序树
二叉排序树的插入和删除： 插入可查找位置后直接插入（不考虑平衡）
删除：
x 为叶子结点，则直接删除
x 只有左子树
xL 或只有右子树 xR , 则令 xL 或 xR 直接成为双亲结点 f 的子树；x 即有左子树
xL 也有右子树 xR，在 xL 中选值最大的代替 x，该数据按二叉排序树的性质应在最右边。平衡因子 ：该节点的左子树深度 - 右子树深度
5.2.2 平衡二叉树 / AVL 树
每个结点的平衡因子都为 1、－1、0 的二叉排序树。
平衡二叉树的平衡 ：
左调整 (新结点插入在左子树上的调整)：
LL(插入在结点左子树的左子树上)：旋转前后高度都为 h+1
LR(新插入结点在左子树的右子树上)：旋转前后高度仍为 h+1
右调整 (新结点插入在右子树上进行的调整):
RR(插入在的右子树的右子树上)：处理方法和 LL 对称
RL(插入在的右子树的左子树上)：处理方法和 LR 对称
规律：找到上图合适的 ABC 节点进行变化，其他节点顺序不变，位置再放入
在平衡二叉树上查找，时间复杂度仅为
O(log n)红黑树：一种二叉平衡树的实现
定义与性质：
节点是红色或黑色。
根是黑色。
所有叶子都是黑色（叶子是 NIL 节点）。
每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
从任一节点到其每个叶子的所有简单路径 都包含相同数目的黑色节点。
红黑树和 AVL 树查找、插入、删除的时间复杂度相同；包含 n 个内部结点的红黑树的高度是 ;
TreeMap 是一个红黑树的实现，能保证插入的值保证排序5.2.3B - 树 / B 树
m 阶B树满足或空，或为满足下列性质的m叉树：
- 树中每个结点最多有 m 棵子树，最多有 m-1 个关键字
- 根结点在不是叶子时，至少有两棵子树
- 除根外，所有非终端结点至少有 （向上取整）棵子树
- 有
s个子树的非叶结点具有n = s-1个关键字，结点的信息组织为:(n,A0,K1,A1,K2,A2 … Kn，An)。这里：n为关键字的个数，ki（i=1,2,…,n)为关键字，且满足Ki小于Ki+1，Ai(i=0,1,…n)为指向子树的指针。
- 所有的叶子结点都出现在同一层上，不带信息（可认为外部结点或失败结点）。
性质 ：
- 关键字集合分布在整颗树中
- 任何一个关键字出现且只出现在一个结点中
- 搜索有可能在非叶子结点结束
- 其搜索性能等价于在关键字全集内做一次二分查找
- 只适用于随机检索，不适用于顺序检索。
- 所有结点的平衡因子都为零
M 阶 B - 树中含有 N 个关键字，最大深度为 l：
2-3 树 ：3 阶 B_树的插入。每个结点最多 3 棵子树，2 个数据；最少 2 棵子树，1 个数据。所以 3 阶 B_树也称为 2-3 树。
B_树中结点的插入
m 代表 B_树的阶，插入总发生在最低层
插入后关键字个数小于等于 m-1, 完成。
插入后关键字个数等于 m, 结点分裂，以中点数据为界一分为二，中点数据放到双亲结点中。这样就有可能使得双亲结点的数据个数为 m, 引起双亲结点的分裂，最坏情况下一直波及到根，引起根的分裂——B_树长高。
B_树中结点的删除
- 删除发生在最底层
被删关键字所在结点中的关键字数目大于等于 m/2 ，直接删除。
删除后结点中数据为⎡m/2⎤-2，而相邻的左（右）兄弟中数据大于⎡m/2⎤-1，此时左（右兄弟）中最大（小）的数据上移到双亲中，双亲中接（靠）在它后（前）面的数据移到被删数据的结点中
其左右兄弟结点中数据都是⎡m/2⎤-1，此时和左（右）兄弟合并，合并时连同双亲中相关的关键字。此时，双亲中少了一项，因此又可能引起双亲的合并，最坏一直到根，使 B - 树降低一层。
- 删除不在最底层
在大于被删数据中选最小的代替被删数据，问题转换成在最底层的删除
B + 树
在实际的文件系统中，用的是 B + 树或其变形。有关性质与操作类似与 B_树。
差异：
有 k 个子树的节点含有 k 个关键字
所有叶子结点中包含全部关键字信息，且叶子结点本身依关键字的大小自小而大的顺序链接。(而 B 树的叶子节点并没有包括全部需要查找的信息)
所有非叶子为索引，结点中仅含有其子树根结点中最大（或最小）关键字。 (而 B 树的非终节点也包含需要查找的有效信息)
非叶最底层顺序联结，这样可以进行顺序查找
在 B+ 树上，既可以进行缩小范围的查找，也可以进行顺序查找；
在进行缩小范围的查找时，不管成功与否，都必须查到叶子结点才能结束；
若在结点内查找时，给定值≤Ki， 则应继续在 Ai 所指子树中进行查找
B+tree 的磁盘读写代价更低，查询效率更加稳定
B 树和 B + 树都是平衡的多叉树。B 树和 B + 树都可用于文件的索引结构。B 树和 B + 树都能有效的支持随机检索。B + 树既能索引查找也能顺序查找.
5.2.4 哈希表
哈希函数 ：在记录的关键字与记录的存储位置之间建立的一种对应关系。是从关键字空间到存储位置空间的一种映象。
哈希表 ：应用哈希函数，由记录的关键字确定记录在表中的位置信息，并将记录根据此信息放入表中，这样构成的表叫哈希表。
Hash 查找适合于关键字可能出现的值的集合远远大于实际关键字集合的情形。更适合查找，不适合频繁更新
Hash 表等查找复杂依赖于 Hash 值算法的有效性，在最好的情况下，hash 表查找复杂度为
O(1)。只有无冲突的 hash_table 复杂度才是 O(1)。一般是 O(c)，c 为哈希关键字冲突时查找的平均长度。插入，删除，查找都是 O(1)。平均查找长度不随表中结点数目的增加而增加, 而是随负载因子的增大而增大由于冲突的产生，使得哈希表的查找过程仍然是一个给定值与关键字比较的过程。
根据抽屉原理，冲突是不可能完全避免的，所以应考虑选择好的散列函数和冲突处理方法。
常用的哈希函数
直接定址法：仅适合于：地址集合的大小 == 关键字集合的大小
数字分析法：对关键字进行分析，取关键字的若干位或其组合作哈希地址。仅适合于：能预先估计出全体关键字的每一位上各种数字出现的频度。
平方取中法：以关键字的平方值的中间几位作为存储地址。
折叠法：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址。移位叠加 / 间界叠加。适合于: 关键字的数字位数特别多，且每一位上数字分布大致均匀情况。
除留余数法：取关键字被某个不大于哈希表表长 m 的数 p 除后所得余数作哈希地址，即
H(key)=key%p，p<=m。随机数法：取关键字的伪随机函数值作哈希地址，即 H(key)=random(key)，适于关键字长度不等的情况。
冲突解决
开放定址法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中。即
Hi=(H(key)+di) % m，i=1,2,……k(k<=m-1)，H(key) 哈希函数，m 哈希表长，di 增量序列。缺点：删除：只能作标记，不能真正删除；溢出；载因子过大、解决冲突的算法选择不好会发生聚集问题。要求装填因子α较小，故当结点规模较大时会浪费很多空间。线性探测再散列：
二次探测再散列：
伪随机探测再散列: 为伪随机数序列
链地址法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针。拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间。一旦发生冲突，在当前位置给单链表增加结点就行。
其他方法：再哈希法、建立公共溢出区
在用拉链法构造的散列表中，删除结点的操作易于实现。拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间。由于拉链法中各链表上的结点空间是动态申请的, 故它更适合于造表前无法确定表长的情况。拉链法解决冲突时，需要使用指针，指示下一个元素的存储位置
开哈希表–链式地址法; 闭哈希表–开放地址法. 开哈希和闭哈希主要的区别在于，随着哈希表的密集度提高，使用闭哈希时，不仅会与相同哈希值的元素发生冲突，还容易与不同哈希值的元素发生冲突；而开哈希则不受哈希表疏密与否的影响，始终只会与相同哈希值的元素冲突而已。所以在密集度变大的哈希表中查找时，显然开哈希的平均搜索长度不会增长。
Hash 查找效率：装填因子 = 表中记录数 / 表容量
5.3 查找总结
既希望较快的查找又便于线性表动态变化的查找方法是哈希法查找。
二叉排序树查找，最优二叉树查找，键树查找，哈希法查找是动态查找。
分块、顺序、折半、索引顺序查找均为静态。
分块法应该是将整个线性表分成若干块进行保存，若动态变化则可以添加在表的尾部（非顺序结构），时间复杂度是 O(1)，查找复杂度为 O(n)；若每个表内部为顺序结构，则可用二分法将查找时间复杂度降至 O(logn)，但同时动态变化复杂度则变成 O(n)；
顺序法是挨个查找，这种方法最容易实现，不过查找时间复杂度都是 O(n)，动态变化时可将保存值放入线性表尾部，则时间复杂度为 O(1)；
二分法是基于顺序表的一种查找方式，时间复杂度为 O(logn)；通过哈希函数将值转化成存放该值的目标地址，O（1）
二叉树的平均查找长度为 O(log2n)——O(n). 二叉排序树的查找效率与二叉树的高度有关，高度越低，查找效率越高。二叉树的查找成功的平均查找长度 ASL 不超过二叉树的高度。二叉树的高度与二叉树的形态有关，n 个节点的完全二叉树高度最小，高度为 [log2n]+1,n 个节点的单只二叉树的高度最大，高度为 n，此时查找成功的 ASL 为最大 (n+1)/2，因此二叉树的高度范围为 [log2n]+1——n.
链式存储不能随机访问，必须是顺序存储
6. 内部排序
内部排序：全部数据可同时放入内存进行的排序。
外部排序：文件中数据太多，无法全部调入内存进行的排序。
稳定的排序方法：对于相同的值，排序前后其相对位置不变，则为稳定，若反了为不稳定
6.1 插入排序
直接插入排序 ：最坏情况是数据递减序，数据比较和移动量最大，达到
O(n^2)，最好是数据是递增序，比较和移动最少为 O(n)。每次从后向前比较
折半插入排序：由于插入第 i 个元素到 r[1] 到 r[i-1] 之间时，前 i 个数据是有序的，所以可以用折半查找确定插入位置，然后插入 。减少了比较次数但是没减少移动次数，复杂度仍为 O（n^2）
希尔排序: 缩小增量排序。5-3-1。在实际应用中，步长的选取可简化为开始为表长 n 的一半（n/2），以后每次减半，最后为 1。插入的改进，最后一趟已基本有序，比较次数和移动次数相比直接插入最后一趟更少。在每一趟中使用直接插入排序。
6.2 交换排序
冒泡排序： 通常认为冒泡是比较差的，可以加些改进，比如在一趟中无数据的交换（序列是递增的），则结束等措施，所以比较次数和初始序列顺序有关。在数据已基本有序或数据量较少时可以使用。
快速排序： 通过一趟排序将记录分割为两部分，一部分的关键字均比另一部分小。
特点： 在第 i 趟完成后，会有 i 个以上的数出现在它最终要出现的位置，也就是说它左边的数都比他小，右边的数都比他大。
时间复杂度。最好情况：每次支点总在中间，O(nlog2n)，平均 O(nlog2n)。最坏，数据已是递增或递减，O(n2)。pivotkey 的选择越靠近中央，即左右两个子序列长度越接近，排序速度越快。越无序越快。
空间复杂度。需栈空间以实现递归，最坏情况：S(n)=O(n)；一般情况：S(n)=O(log2n)
在序列已是有序的情况下，时间复杂度最高。原因：支点选择不当。改进：随机选取支点或最左、最右、中间三个元素中的值处于中间的作为支点，通常可以避免最坏情况。所以，快速排序在表已基本有序的情况下不合适。在每次划分后分区较为平衡时，递归次数较少。
J 往回走找到第一个比枢纽小的，i 往前走找到第一个比枢纽大的。然后进行交换
6.3 选择排序
简单选择排序 ：O(n^2)。总比较次数 n(n-1)/2。
树形选择排序 / 竞标赛排序 ：2 个一组选出较小的一个，然后在较小的中又 2 个组选出较小的一个，直到选出最小的。还可以输出次小值。时间复杂度 O（nlogn），需要的辅助空间大。
堆排序：
若将序列对应为完全二叉树，则有性质：对于最小堆，所有非叶子节点的值均小于等于其左右孩子节点的值，其根值 / 堆顶元素为序列的最小者。
在输出堆顶元素后，将最后一个元素放于堆顶，再使得剩余的 n-1 个元素序列又可以重建成一个堆，得到次小值，如此反复执行可以得到有序序列，就是堆排序。
“筛选”：重建堆的过程。从一个元素开始下沉。
最大的元素输出后， 用最后一个元素代替之放在堆顶，然后向下比较交换，维持堆的性质，直到沉入叶子节点 。
建堆：对无序序列，从第 n/2（向下取整）个元素，向前知道堆顶元素，进行反复下沉操作。
建堆 O(n)，筛选排序 O(nlogn)。找出若干个数中最大 / 最小的前 K 个数，用堆排序是最好。
6.4 归并排序
归并 ：将两个有序表和为一个有序表。归并排序：将 n 个元素视为 n 个有序表，先两两合并，再两两合并，直到全部合并。
归并时间 ：与表长成正比，若一个表表长是 m，另一个是 n，则时间是 O(m+n)。
单独一个数组归并，时间：O(nlogn)，空间：O(n)，归并排序算法比较占用内存，但却是效率高且稳定的排序算法。一般在外排序中使用。归并的趟数是 logn。
6.5 基数排序
在一般情况下，每个结点有 d 位关键字，必须执行 t = d 次分配和收集操作。分配的代价：O(n)；收集的代价：O(rd) （rd 是基数）；总的代价为：O( d ×(n + rd))。适用于以数字和字符串为关键字的情况。
6.6 枚举排序
通常也被叫做秩排序，比较计数排序。对每一个要排序的元素，统计小于它的所有元素的个数，从而得到该元素在整个序列中的位置，时间复杂度为 O(n2)
比较法 分类的下界：O(nlogn)
6.7 排序算法的一些特点
堆排序、冒泡排序、快速排序在每趟排序过程中, 都会有一个元素被放置在其最终的位置上。
在文件 “局部有序” 或文件长度较小的情况下, 最佳内部排序的方法是直接插入排序。（归并排序要求待排序列已经部分有序，而部分有序的含义是待排序列由若干有序的子序列组成，即每个子序列必须有序，并且其时间复杂度为 O(nlog2n)；直接插入排序在待排序列基本有序时，每趟的比较次数大为降低，即 n-1 趟比较的时间复杂度由 O(n^2) 降至 O(n)。在待排序的元素序列基本有序或者每个元素距其最终位置不远也可用插入排序，效率最高的排序方法是插入排序）
排序趟数与序列的原始状态有关的排序方法是优化冒泡和快速排序法。(插入排序和选择排序不管序列的原始状态是什么都要执行 n-1 趟，优化冒泡和快排不一定。仔细理解排序的次数和比较次数的区别)
不稳定的排序方法：快排，堆排，希尔，选择
高效稳定的算法：归并
要与关键字的初始排列次序无关, 那么就是最好、最坏、一般的情况下排序时间复杂度不变, 总共有堆排序, 归并排序, 选择排序, 基数排序
快速排序、Shell 排序、归并排序、直接插入排序的关键码比较次数与记录的初始排列有关。折半插入排序、选择排序无关。(直接插入排序在完全有序的情况下每个元素只需要与他左边的元素比较一次就可以确定他最终的位置；折半插入排序，比较次数是固定的，与初始排序无关；快速排序，初始排序不影响每次划分时的比较次数，都要比较 n 次，但是初始排序会影响划分次数，所以会影响总的比较次数，但快排平均比较次数最小；归并排序在归并的时候，如果右路最小值比左路最大值还大，那么只需要比较 n 次，如果右路每个元素分别比左路对应位置的元素大，那么需要比较 2*n-1 次，所以与初始排序有关)
精俭排序，即一对数字不进行两次和两次以上的比较，插入和归并是 “精俭排序”。插入排序，前面是有序的，后面的每一个元素与前面有序的元素比较，比较过的就是有序的了，不会再比较一次。归并每次合并后，内部都是有序的，内部的元素之间不用再比较。选择排序，每次在后面的元素中找到最小的，找最小元素的过程是在没有排好序的那部分进行，所有肯定会比较多次。堆排序也需比较多次。
7. 其他部分
外部排序
外部排序的总时间 = 内部排序（产出初始归并段）所需时间 + 外存信息读取时间 + 内部归并所需的时间
（……）
动态存储管理
……
文件
……
有效的算法设计
回溯法
分支限界法
分治法。分割、求解、合并。二分查找、归并排序、快速排序。
动态规划。Floyd-Warshall 算法求解图中所有点对之间最短路径时间复杂度为 O(n3)
动态规划解题的方法是一种高效率的方法，其时间复杂度通常为 O(n2)，O(n3) 等，可以解决相当大的信息量。（数塔在 n<=100 层时，可以在很短的时间内得到问题解）
动态规划比穷举法具有较少的计算次数
递归算法需要很大的栈空间，而动态规划不需要栈空间
P 问题，如果它可以通过运行多项式次 (即运行时间至多是输入量大小的多项式函数的一种算法获得解决），可以找到一个能在多项式的时间里解决它的算法。—- 确定性问题
NP 问题，虽然可以用计算机求解，但是对于任意常数 k，它们不能在 O(nk) 时间内得到解答，可以在多项式的时间里验证一个解的问题。所有的 P 类问题都是 NP 问题。
NP 完全问题，知道有效的非确定性算法，但是不知道是否存在有效的确定性算法，同时，不能证明这些问题中的任何一个不存在有效的确定性算法。这类问题称为 NP 完全问题。