# 经典排序算法+数据结构
# 1.比较类排序
# 交换排序
- 冒泡排序：依次比较相邻两个数，前面比后面的大就交换位置。N个数字要进行N-1次排序(N-1趟就有序了) 最好时间复杂度是O(n) 平均时间复杂度O(n^2) 稳定 空间复杂度是O(1)
- 快速排序 通常将第一个元素作为基准元素，将数组比基准元素小的放左边，大的放右边。 再对左右两边的元素进行同样的比较，直到无法拆分为止。 时间复杂度O(nlogn) 空间复杂度O(nlong) 不稳定
# 插入排序
- 简单插入排序 先插入数组中第一个数，再次插入时在已排序的新数组中从后向前扫描比较，找到相应位置插入。 最好O(n) 时间复杂度都是O(n^2) 稳定 空间复杂度是O(1)
- 希尔排序
# 选择排序
- 简单选择排序: 找到最小的元素，放到起始位置，再从剩余元素中找到最小的元素，放到第二个位置，依次类推 时间复杂度都是O(n^2) 不稳定 空间复杂度是O(1)
- 堆排序
# 2.非比较排序
计数排序、桶排序、基数排序
- 稳定性：a原本在b前面，a==b，排序之后ab顺序改变为不稳定，否则为稳定
- 时间复杂度：总的操作次数
- 空间复杂度：算法执行所需的空间大小
# 平均时间复杂度：
- O(n^2) 插入排序 选择排序 冒泡排序
- O(nlog2n) 堆排序 归并排序
- O(nlogn) 快速排序
# 空间复杂度：
- O(1) 插入排序 希尔排序 选择排序 堆排序 冒泡排序
- O(logn) 快速排序
- O(n) 归并排序
# 稳定性：
- 稳定：插入排序 冒泡排序 归并排序 非比较排序都稳定
- 不稳定：希尔排序 选择排序 堆排序 快速排序
# 3.快排实现思路
- 通常将第一个元素作为基准元素，将数组比基准元素小的放左边，大的放右边。
- 再对左右两边的元素进行同样的比较，直到无法拆分为止。
# 4.二叉查找树(BST树)
- 又称二叉搜索树。每个节点左子节点小于该节点，右子节点大于等于该节点
- 最小值是树最左端的节点，最大值是树最右端的节点
# 常见查找算法
- 顺序查找：也称线性查找，是最低效的查找算法。时间复杂度O(n) 空间复杂度O(1)
- 二分查找：也称折半查找，要求待查找数组已排序。选择中间数，查找数比中间数小去左边子数组找，比中间数大去右边子数组找，以此类推。
- 时间复杂度是O(logn) 空间复杂度O(1)
# 5.斐波那契数列
0,1,1,2,3,5,8...
function fib(n) {
if (n < 2 && n >= 0) return n
return fib(n - 1) + fib(n - 2)
}
1
2
3
4
2
3
4
# 6.二叉树
- 二叉树每个节点最多有两个节点，分别是左节点，右节点。仅有一个根节点，节点间不能闭环(普通树可以有多个子节点)
- 当一颗二叉树的叶子节点数量满时，就是满二叉树
- 二叉查找树(二叉搜索树BST)特点是根节点都比左节点大，比右节点小
- 平衡二叉树(AVL)：左右子树的高度差不能大于1
- 先序遍历中左右、中序遍历左中右、后序遍历左右中
# *7.二叉堆
- 堆是一个完全二叉树
- 任意节点小于或大于它的所有子节点
- 堆总是一颗完全树，除了最底层，其他层的节点都被元素填满，且最底层从左到右填入
- 根节点最大的堆是大根堆，最小的堆是小根堆
# 复杂度分析
- 时间复杂度：衡量代码执行的时间,取最大的为其时间复杂度(并不是真正的代码执行的时间。而是表示时间随数据规模增加的趋势)
- 空间复杂度：执行过程临时占用的存储空间大小(表示空间随数据规模增加的趋势。原地算法就是不用多余的空间O(1))
# 常见复杂度
- O(1) 原地算法
- O(logn) 二分查找
- O(n) 常数for循环(1个，2个for循环，非嵌套)
- O(n^2) 嵌套for循环，如冒泡排序
# 8.链表
单链表：只有一个方向，从头节点到尾节点
- 追加节点：初始化节点，遍历到链尾，链尾元素的next指向该节点=》当链表为null，直接将head指向该节点即可
- 查找：遍历单链表，判断节点值是否等于查找值，等于返回true，否则继续遍历，遍历完都没有返回false=》链表为null返回false
- 在position位置插入：初始化一个节点，遍历到position前一个节点，在该节点后插入节点
- 删除：遍历单链表，找到待删除节点，删除
- 复杂度：从头开始查找，复杂度是O(n) 插入或删除在某个节点后插入或删除的时间复杂度都是O(1) 双链表：有两个方向，从头节点到尾节点，从尾节点到头节点
- 在position位置插入：初始化一个节点，遍历链表到position前一个节点，在该节点后插入节点
- 删除：遍历双链表，找到待删除节点，删除
- 查找：同单链表
- 复杂度：查找前驱后后继节点的时间复杂度都是O(1)，其他节点是O(n) 插入或删除：插入或删除前驱或后继节点的时间复杂度都是O(1) 循环单链表：链尾的next指向头节点
# 9.栈
- 栈是后进先出(LIFO/Last In First Out)
- 查找：从栈头开始查找，时间复杂度是O(n)
- 插入和删除：时间复杂度是O(1) *调用栈又称执行上下文栈，用来管理函数执行上下文的栈结构。
# 10.队列
- 队列是先进先出(FIFO/First In First Out)
- 特有方法有enqueue进队，dequeue出队，front获取队头元素
- 查找：从对头开始查找，时间复杂度是O(n)
- 插入和删除：时间复杂度是O(1)
- 双端队列(Deque):队头和队尾都可以进队和出队
- 滑动窗口：滑动窗口就是运行在一个大数组上的子列表
# 11.图的特性
- 图的每个节点可以连接0或多个元素，两点相连的是边，节点也被称作顶点。一个顶点的度是指与该顶点相连的边的条数
- 如果所有的边都有方向就是有向图，否则就是无向图。
- 顶点的边可以从自己出发再连接回自己，这样的图就是自环，没有环的图就是无环图=》无环无向的图也被称作树
- 从任一节点出发沿着各条边可以访问图中任意节点的图是连通图
- 当一个图中两两不同的顶点之间都有一条边相连，这样的图就是完全图。每个顶点都有图的顶点-1条边=》n个顶点每个顶点都有n-1条边
- 图中很少顶点互相相连是稀疏图，否则是稠密图
# 12.算法思想
- 递归：适用斐波那契数列，回溯，数的遍历，图的搜索
- 分治：分而治之。适用快速排序，归并排序，二分查找
- 贪心：期望通过局部最优选择获取整体最优选择。
- 回溯：试探法，每一步作出选择，发现无法获取期望结果就回溯回去重新选择。适用于深度优先遍历，全排列
- 动态规划：将复杂问题分解成小问题，与分治不同的是它要求问题之间是关联的，不是独立的。适用于求最优解，爬楼梯，硬币找零，最长公共子序列
- 枚举算法：将问题的所有答案一一列举，再根据条件判断答案是否符合，保留符合抛弃不符合