数据结构（算法）

总结，建议看EXCEL的《算法》页签，不然感觉有点乱

			备注	原理/步骤	时间复杂度	空间复杂度
串的应用	模式匹配	简单/暴力			O(mn)
		KMP			O(m+n)
树的应用	树	哈夫曼树 1、带权路径长度WPL 2、外部排序-最佳归并树	1、哈夫曼树的度，只有0和m（m叉树）（王道P176） 2、哈夫曼编码，是从根结点到叶子结点的路径上的01组合（王道P180.T4） 3、同一组编码/权值，构造出来的哈夫曼树可以不同【自己举个例子就知道了】（王道P180.T6A） 4、路径长度指：Σ(叶子结点的值 x 到根的长度数)，之和【领悟：哈夫曼树的构造，除了第一次用m个数据（如0、2、3），其他每次只用m-1个数据（因为有1个数据是来自下一层的和）】 王道.P359.T07
		并查集 1、Kruskal，克鲁斯卡尔（王道.P182.T10） 2、无向图的连通性判断
	图的存储	邻接矩阵				O( |V|2 )
		邻接表			删除，某个顶点相关的所有边 有向图：O( |V| + |E| )	无向图：O( |V| + 2|E| ) 有向图：O( |V| + |E| )
		十字链表（有向图）	顶点表：[data，edge1，edge2] 边表：[弧尾点，弧头点，弧头指针，弧尾指针，info]			O( |V| + |E| )
		邻接多重表（无向图）	顶点表：[data，edge] 边表：[点1，点2，指针1，指针2，info]			O( |V| + |E| )
	图的遍历	BFS，广度优先	1、队列 2、相当于树的层次遍历	像波纹一样推开遍历	邻接矩阵：O( |V|2 ) 邻接表：O( |V| + |E| )	O( |V| )
		DFS，深度优先	1、栈 2、相当于树的先序遍历 3、可用于判断有向图是否有回路 4、逆拓扑排序（王道P210.T11）	1、一条路走到黑 2、再退一步，再走到黑
图的应用	I 最小生成树 1、权值的和为最小 2、没有权值相同的边，生成树的树形才唯一 3、最小生成树的代价一定是唯一的（王道P228.T18）	Prim，普利姆 只与点有关 贪心算法	1、n个结点，时间复杂度，与边无关（因为是选n-1边，没选到的边,再多也无用），适合稠密图 2、n个结点，1个最小的，其余n-1个相等的值，从不同的顶点开始Prim算法，则会得到n-1种不同的最小生成树（王道.P228.T18.III）	1、一个顶点选连接的最小的边（最小边：将已经连接的点，作为整体，看与未连接的边的权重/值，最小的一个），选完：若构成环，则去掉刚选的边，退到上一个顶点 2、结束：所有顶点都连接时	O( |V|2 )
	普克（扑克）	Kruskal，克鲁斯卡尔 只与边有关 贪心算法	适合边稀疏	1、所有边从小到大排序，依次选择：若构成环，去掉继续选下一个 2、结束：所有顶点都连接时	O( nlog2n )，n是边
	II 最短路径 简单路径	BFS，广度优先	1、无权单源（点到点） 2、只能无向图（权值为1或相同）	/	邻接矩阵：O( |V|2 ) 邻接表：O( |V| + |E| )
	广迪弗（甘道夫）	Dijkstra，迪杰斯特拉 贪心算法	1、带权单源（点到点） 2、负权值、负回路不适用	1、主要3个元素：标记、距离、前驱 2、选一个点先初始化 3、①选中距离最小且未标记的点，标记置为True；②更新由点到其他未标记的距离、前驱 4、结束：所有结点标记都为True	O( |V|2 )
		Floyd，弗洛伊德	1、带权所有顶点 2、负回路不适用	1、A[i][j] > A[i][*] + A[*][j]，选择一个"点*"作为转中点，到其他点的距离更新 2、每次选择都需要更新邻接矩阵	O( |V|3 )	O( |V|2 )
	III 有向无环图描述表达式 DAG，Directed Acyclic Graph		最底层的元素都只有一个	1、先按顺序写出所有的字母，作为最底层的元素 2、依次往上连接符号，表示一个小的运算
	IV 拓扑排序 AOV，Activity On Vertex Network		1、有拓扑序列就不存在回路 ∵要选入度为0，回路是环，不存在入度为0的结点 2、每个顶点出现仅有一次 3、可能排序不唯一 4、A排在B前面，则不存在 B —>A 的路径	依次选择入度为0的点
	逆拓扑排序·	DFS，深度优先，出栈时读出	DFS，可得逆拓扑顶点有序序列	依次选择出度为0的点
	V 关键路径 AOE，Activity On Edge Network		1、缩短所有关键路径上共有的任意一个关键活动的时间，才可以缩短关键路径长度 2、 e(i)：事件最早发生时间 l(i)：事件最迟发生时间 ae(i)：活动最早发生时间 al(i)：活动最迟发生时间 d=ae(i)-al(i)，为0就是关键活动	从起点到结束点，长度最大的路径			平均查找长度 ASL 类似EX数学期望
查找	线性结构	顺序查找	1、数组、链表均可 2、每个元素查找成功的比较次数只与位置有关，与是否有序无关，王道.P253.T2		O(n)		一般：ASL成功 = ΣPi(n-i+1) 等概率： ASL成功 = (n+1)/2 ASL不成功 = n+1 王道.P250推导
		折半查找 二分查找	1、必须有序，且只能用顺序存储（数组） 2、平衡二叉树 3、(low+high)/2 结果：向上取整或向下取整，但一棵树只能二选一，王道.P254.T12/T21		查找：O(log2n) 插入删除：O(n)		等概率：ASL成功 ≈log2(n+1)-1 王道P252例子 P254T13/T18
		分块查找	1、块内随意，块间有序；折半查找索引表，顺序查找块内表 2、索引表：一个块的最大的关键字，和第一个元素的位置 3、最理想的块长：√n，且平均查找长度为 (√n) +1	1、先查索引表（顺序查找/(数组时)二分查找） 2、块内顺序查找			(b+1)/2 + (s+1)/2 分为 b 块，每块有 s 个记录，王道.P254.T16
	树形结构	二叉排序树BST  - 二叉查找树  - 左 < 根 < 右	0、空树也是二叉排序树 1、可以形成单支树，查找长度为 n，时间复杂度是O(nlogn) 2、中序遍历，会得到一个递增的序列 3、 叶结点，删除后插入，与原树一定相同 非叶结点，删除后插入，与原树一定不同 （王道.P276.T21）	左子树结点的值 < 根结点的值 < 右子树结点的值	查找：O(log2n)/O(n) 插入删除：O(log2n)
		平衡二叉树AVL - 发明者G. M. Adelson-Velsky和E. M. Landis  - 是特殊的二叉排序树	0、  - 空树也是平衡二叉树  - 平衡因子：左子树高度-右子树高度  - LL、RR、LR、RL 4种破坏平衡的方式 1、左右子树高度差不超过1 2、不一定是完全二叉树 3、 n0=0，n1=1，n2=2 nh = nh-1 + nh-2 +1 构造最大高度 h 的平衡二叉树，所需的最少的结点数nh（王道.P275.T10/T11），此时非叶结点的平衡因子为1（王道.P276.T20） 4、平衡二叉树，叶结点/非叶子结点，删除后插入，与原树可能相同也可能不同（王道.P276.T25）		O(log2n)		O(log2n)
	B树，多路平衡查找树	1、B树只支持随机查找，B+树支持顺序查找、随机查找（∵B+树的叶子结点包含全部关键字信息，∴支持顺序） 2、	1、每个结点： [(m/2)向上取整]-1 ≤ 关键字 ≤ m-1（王道.P290.T01） 2、平衡因子=0，绝对平衡，所有叶子结点都在同一层 3、高度 h ，m 阶B树：（王道.P291.T06） ①结点数最少：2h - 1（满二叉树） ②结点数最多：mh - 1（满m叉树） 4、外部结点不算层数 5、m阶，n个点，最大高度、最小高度 P287（王道.P291.T08/T09）
	B+树		1、用于各种索引：文件索引、数据库索引
散列表（哈希表） 散列函数（哈希函数） 1、适合关键字集合与地址集合之间存在对应关系 2、平均查找长度ALS  - 与表长、元素都无关  - 与散列函数、处理冲突的方法、装填因子有关 3、装填因子α = 已有记录数/表长度 α越大  - 表示哈希表的装满的程度  - 越容易发生冲突（王道.P302.T06） ∴想要提高查找效率，需要减小装填因子 4、探测：插入前检测次数（王道.P302.T07）	处理冲突的方法1 开放地址法 Hi = [ H(key) + di ] % m 删除时只能是假删除，否则影响查找	I 线性探测法	1、映射后，一直探测到下一个可以存放的地址 2、会出现元素堆积/聚集（同义词与非同义词发生冲突都可以造成堆积），大大降低查询效率 3、细节：空的也会消耗1次对比的机会（王道.P303.T17/T18）	di = 0 1 2 3 … m-1	理想情况：O(1)
		II 平方探测法	1、m 是一个 4k+3 的质数 2、有效避免堆积	di = 02 12 -12 22 -22 … k2 -k2
		III 伪随机序列法		di = 一个随机数列，可以自己定义
		IV 双散列法，再散列法，再哈希法		k=Hash1(key) d=Hash2(key) 探测顺序：(k+d)%n、(k+2d)%n、(k+3d)%n…
	处理冲突的方法2 拉链法	链接法，链接地址法	1、不会发生堆积	数组下标作为指针的起始，用链表存数据			稳定性
排序	插入排序	直接插入	1、不考虑哨兵的比较  - 最坏的情况需要 n(n-1)/2 次比较  - 最好的情况只要 n-1 次比较，有序，第一个元素视为已经排好序的，后面每个元素都只要比较1次，所以只要n-1次比较	1、第1个元素视为有序，无序消耗比较次数 2、第i个元素前面都是有序的 3、从后往前，找插入位置，然后进行插入	最好，初始化序列原本有序：O(n) 平均：O(n2/4)，所以是O(n2)，和最坏一样 最坏，初始化序列刚好逆序：O(n2)	O(1)，每次只要常数个辅助单元	Y，先比较，再移动
- 不稳定4个：希尔选择快速堆，选的太快不稳定  - 不能原地工作的3个内部排序：基数O(max(r))、快速O(log2n)、归并O(n)【鸡块饼，占空间】  - 原地工作：空间复杂度O(1) https://www.cnblogs.com/Xieyang-blog/p/8340578.html+B34 1、时间复杂度（比较+移动）与序列初始状态无关：  - 选择排序  - 堆排序  - 归并排序  - 基数排序 （口诀：一堆乌龟选基友，和初始状态无关） 2、排序趟数和原始状态有关：2个交换排序都有关（冒泡 + 快速） 3、利用顺序存储的随机访问特性（采用链式会降低速度）：  - 希尔排序  - 堆排序		折半插入 二分插入	数组	因为是在有序表中查找插入位置，所以查找可以先采用二分查找，再移动元素	O(n2)	O(1)	Y
		希尔排序 缩小增量排序	数组，不适用于链表	1、%d 的为一组（d=间隔+1，王道.P316.T08），然后使用直接插入排序同组元素 2、d减小，再进行排序	最好/平均：O(n1.3) 最坏：O(n2)	O(1)	N，相同元素在不同组时，可能发生位置变化
	交换排序 两两比较，次序相反的就交换，直到所有数据没有反序为止	冒泡排序 起泡排序	- 最坏的情况，刚好逆序，比较和交换次数相同，都需要 n(n-1)/2 次  - 适用于：数组、链表  - 在一趟排序过程中，没有发生交换，则算法可以提前结束	1、每次都是从头到尾，两两比较，满足条件的两两交换 2、细节：每次冒泡就确定了本趟“最后元素”的位置，剩余趟数就不用消耗比较次数 王道.P323.T08	最好，有序：O(n) 最坏/平均，逆序：O(n2)	O(1)	Y
		快速排序 递归排序	1、待排序列最适合采用：顺序存储（40811T10） 2、"有序快排最慢"原则，有序每次划分是 0 和 n-1 个元素 每次将表分为长度相近的两个子表时最快（王道.P323.T9） 3、递归次数/趟数：  - 对尚未确定最终位置的所有元素进行一遍处理。如：第二趟需要都处理左右两个子块才算一趟（王道.P324.T17）  - 与初始数据的排列次序有关（"有序最慢"原则）  - 与划分后的分区处理前后顺序无关（408.10T10） 4、每一趟排序后，基准值元素，会放在最终的位置	选一个基准值，用两个前后两个指针 i、j： 1、比基准值大，将元素放在j，然后j=j-1 2、比基准值小，将元素放在i，然后i=i+1 3、与基准值相等，不处理 i==j时，左右继续重复上述操作，递归	最好/平均：O(nlog2n)，最平衡的划分，每次划分，左右元素个数差不多都是n/2 最坏：O(n2)，有序元素	递归工作栈，需要空间 最小：O(log2n) 最大：O(n)	N，同右侧的相同元素，都小于基准值，都要移去左边，那么这2个相同的元素相对位置会改变
	选择排序 在所有记录中，每次选择最小的，放在最后/前面	选择排序	1、数组、链表均可 2、比较次数与初始状态无关，n个元素都需要 n-1 趟	1、每次都要遍历排好序之后的待排序列 2、选择最小的数，与无序的第一个数交换	比较次数：O(n2)，2层for循环 移动次数：O(n)	O(1)	N
		堆排序	1、在1亿个数里面找出100个最小值，用大根堆（根 ≥ 左、右） 2、堆是用来排序的，其查找效率不高 3、堆，必须是一个完全二叉树	1、破坏堆（取出根值，并用完全二叉树的最后一个元素填充根值） 2、恢复堆	插入/删除：O(log2n) 构建堆：O(n) 排序：O(nlog2n)	O(1)	N
		胜者树  - 竞赛树排序  - 其实就是败者树			O(nlog2n)
	归并排序	归并排序	1、N个元素，k路归并，趟数m：km = N 2、m = [logkN]向上取整，趟数	2路归并： 2个元素/2个块/2个小组，进行1对1比大小，合并成一组，组成新的有序数列	2路归并： O(nlog2n)，每一趟是O(n)，一共 log2n 趟	O(n)，合并需要n个辅助单元	Y
	基数排序 分配（收集）排序	基数排序	适用于 1、n比较大 2、r比较小 3、方便拆，且d比较小 不适用：float、double的实数	将n个元素每一个可以拆成d个关键字，每一个关键字有自己的r基数范围	O( d·(n+r) )	O(max(r))	Y
外部排序	归并排序		1、外部排序时间 = 读写外存的时间 + 内部排序所需时间 + 内部归并所需时间 2、优化思路：减少读写外存的趟数：多路归并，可以减少趟数 2路归并需要在内存分配2个输入缓冲区 4路归并需要在内存分配4个输入缓冲区 r个初始归并段，做K路归并 3、内存中任意一个输入缓冲区空了，需要立即从磁盘中加载一个块继续在内存中排序	1、生成初始的归并段（让内部有序，每一块都需要读、写一次 2、归并2的次方个“归并段”
	优化1： 败者树（选择排序）
	优化2： 置换-选择排序 + 最佳归并树（哈夫曼树）			1、置换-选择排序：生成不确定但更长的初始归并段 实际是一个一个先放在CPU输出缓冲区，当缓冲区满了才放回磁盘 2、最佳归并树/哈夫曼树  - 初始归并段的长度 = 每段中的整块数  - m路归并，初始段有x个，则需： (x-1)%(m-1) = u ≠ 0时，需要 m-1-u 个0的虚段  - 读写次数 = 2 · WPL