数据结构与算法

连载中

算法的复杂度

时间复杂度
空间复杂度

线性表、链表、队列、栈

树

二叉树

满二叉树：每一个节点要么是叶子节点，要么有两个子节点
完全二叉树：从根节点从左到右填充，除了最后一层，每一层都是满的

非空满二叉树的叶节点数=内部节点数+1

非空二叉树空子树数=节点数+1

遍历二叉树

前序遍历：根->左子树->右子树
中序遍历：左子树->根->右子树
后序遍历：左子树->根->右子树

数组实现完全二叉树

二叉搜索树（BST）

对于二叉搜索树的任意一个节点K，该节点左子树任意节点的值都小于K，右子树任意节点的值都大于等于K

BST插入
（1）如果root为空，创建节点插入
（2）如果值小于root的值，对左子树递归
（3）反之对右子树递归

BST删除
（1）如果没有左子节点，返回右子节点
（2）如果有两个子节点，对右子树调用函数deletemin，并用函数返回值代替被删除节点

堆

最大/最小堆：任意一个节点的值都大于/小于或等于其任意一个子节点的值

建堆
假设左右子树都已经是堆，且根元素为R
（1）R的值大于或等于其他两个子节点，建堆完成
（2）否则与子节点中较大的那一个交换

霍夫曼编码树

内排序

稳定性

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，则称这种排序算法是稳定的；否则称为不稳定的。

插入排序

（1）将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
（2）从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
（发票按时间排序）

冒泡排序

（1）从后往前比较，若后一个元素比前一个小，则交换，遍历一遍之后，第一个元素为最小值
（2）对剩下的数列重复（1）

选择排序

（1）遍历整个数组，找到最小的数与第一个数交换
（2）对剩下的数列重复（1）

shell排序

基本思想：把数列变成基本有序的数列，再进行插入排序
eg：假设有16个元素
第一轮分为8个长度为2的子数列进行排序
第二轮分为4个长度为4的子数列进行排序
第三轮分为2个长度为8的子数列进行排序
最后一轮正常插入排序

归并排序

eg：假设有8个元素
相邻2个元素排序形成4个有序子数列
每2个子数列排序形成2个有序子数列
…

快速排序

找轴值
（1）从数列中挑出一个元素，称为 “轴值”（pivot），并移动到数列首位
划分
（2）重新排序数列，先从最左端开始向后移动下标l，直到找到大于轴值的值，然后从最右端向前移动下标r，直到找到小于于轴值的值，交换两个值
（3）继续移动l、r重复（2），直到l、r相遇。此时交换下标为l的值与轴值，数列被划分为轴值两侧的两个子数列
递归
（4）对轴值两侧的数列分别执行（1）（2）（3），递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了

堆排序

（1）建堆
（2）不断移除最大值

基数排序

（1）以某个基准（例如个位的数字）计算出每个桶中有多少个数
（2）分配到一个临时数组，并复制回原数组
（3）更新基准（例如十位的数字），重复（1）（2）

算法复杂度比较

排序方法	平均时间复杂度	最好时间复杂度	最坏时间复杂度	空间复杂度	稳定性
插入排序	n2	n	n2	1	稳定
冒泡排序	n2	n	n2	1	稳定
选择排序	n2	n2	n2	1	不稳定
shell排序	n1.3	n	n2	1	不稳定
归并排序	nlogn	nlogn	nlogn	n	稳定
快速排序	nlogn	nlogn	n2	nlogn	不稳定
堆排序	nlogn	nlogn	nlogn	1	不稳定
基数排序	d(r+n)	d(n+rd)	d(r+n)	rd+n	稳定

r：关键字基数 d：长度

外排序

置换选择
多路归并

检索

开散列
闭散列

基于树的索引

2-3 树

结构：
1、一个节点包含一个或两个关键码
2、每个内部节点有两个子节点（一个关键码）或三个子节点（两个关键码）
3、所有叶节点都在树结构的同一层、因此树的高度总是平衡的
4、左子树中所有节点都小于第一个关键码值，中间子树介于两个关键码值中间（左闭右开），右子树大于第二个关键码

插入和删除
2-3树删除和插入操作的小结

B+树

B+树只在叶节点存储记录，内部节点存储关键码值

图

图遍历

深度优先遍历DFS 使用栈
广度优先遍历BFS 使用队列

单源最短路径问题

Dijkstra算法
先求出从起点到最接近起点的顶点之间的最短路径，然后求出第近的，以此类推

最小支撑树

Prim算法

扩张子树

Kruskal算法

挑选最小边拼接