java算法导图
算法的时间复杂度
算法复杂度分析
n=10，nlogn要比n^2快速6000倍，nlogn处理一天，n^2要处理15年。
算法思想
基础算法
-数组排序算法
选择排序
复杂度o(n^2)，首先整个范围内找到最小的，将最小的与第一个位置交换，然后找剩下部分最小的元素，放在和当前还没有排序的第一个位置交换位置。
插入排序
复杂度o(n^2)，把当前元素插入到前面合适的位置，前面的元素都是已经排好序的元素
归并排序
复杂度o(nlogn)归并排序首先将数组分成一半，然后把左边的数组与右边的数组排序，然后归并在一起。
使用递归实现自顶向下的归并排序
如果分到一定的细度，每一部分只有一个元素，此时不用排序进行简单的归并就可以了
归并到上一个层级再进行归并，归并到更高的层级，逐层的归并
归并过程使用3个索引进行跟踪
蓝色的箭头最终归并的过程中需要跟踪的位置
比较，把更小的放在蓝色箭头的位置
使用自底向上的归并排序
两个元素一组
分成4个元素一组
-快速排序
快速排序每次从当前考虑的数组选择一个元素，以当前元素为基点挪到排好序应该在的位置
然后了再对4之前所有小于4的元素与4之后所有大于4的元素分别继续使用快速排序，逐步递归下去完成快速排序。
如何把4挪到正确的位置上，以数组的第一个元素作为标记点，逐渐遍历右边所有没有访问的元素，逐渐整理一部分小于v一部分大于v，找到分界点。
-查找表算法
-查找问题
-链表算法
翻转链表，节点的值不变，节点所指向的next变了。
在链表中删除或者添加节点
-二叉树与递归算法
二叉树的递归结构，递归的终止条件与定义递归问题
二叉树的前中后序遍历
二分搜索树的基本操作
-队列算法问题
广度优先问题
树结构是图结构的特殊形式
树-层序遍历
图-无权图中的最短路径问题
-图算法问题
图的遍历
-深度优先遍历
深度优先就是从一个节点开始不停的往下试直到试不下去为止，图与树的不同，树往下走一定有走不下去的情况。、
图存在环要记录每一个点是否遍历过，如果遍历过下面遍历不需要走了。
一次深度遍历可以将整个图中所有的节点都遍历一遍了，可以获得图中的联通分量，也可以获得路径。
广度优先遍历
一次将图中所有的相邻节点遍历，之后再去遍历相邻节点的相邻节点，使用队列作为辅助的数据结构.
将0的相邻节点1,2,5,6,放入队列完成相应的一次操作
将队列首拿出来作为遍历的对象，已经加入过队列虽然没有遍历过也不用再次遍历了
以距离起始节点0的距离为顺序遍历的
最小生成树
Kruskal算法
每次取出还没有考虑的边中最短的那条边，把边加入图中是否会形成环，如果不能形成环就是最小生成树中的一条边
最短路径
路径规划问题寻找选择耗费最低的路径
无权图的最短路径-广度优先遍历
有权图的最短路径-松弛操作
Dijkstra算法
不能有负权的边，首先将起点标示讲起点所有的临边进行标示，找到没有访问的节点能够以最短的方式到达的顶点就是最短路径中的从原点到访问节点的最短路径。
然后从访问到的节点到其他节点寻找路径更加短的路径(松弛操作)
然后寻找还没有找到最短路径的顶点最短路径能抵达的顶点是1，只要3个距离，然后以1为顶点继续松弛操作。
Bellman-Ford算法
处理负权边。如果一个图拥有负权环就没有最短路径了。
如果一个图没有负权环，从一点到另外一点的最短路径，最多经过所有的V个顶点，有V-1条边，否则存在经过顶点两次既存在负权环。
经过两次松弛操作查看有没又一条只有两条边的路径使得最终总路径的权值最小。
-递归与回溯法
-树形问题，多种字母的组合
-回溯问题
递归调用寻找答案的过程中的重要特征就是回溯，沿着一条路径寻找答案，一旦到底要返回继续寻找
回溯一般用于查找某个解，回溯法是暴力解法的一个主要实现的手段。
排列问题
回溯法解决排列问题(典型的树形问题)
组合问题
回溯法解决组合问题
在1,2,3,4个元素中选出两个元素所有组成的可能 C2 4，与排列问题不同的是组合问题不注重顺序[1,2]与[2,1]是一样的
二维平面的回溯法
二维平面的递归结构
二维平面深度优先的遍历
寻找多个岛屿，从(0,0)开始遍历，整个遍历与(0,0)相连接的岛屿下次遍历就不会重复。
第二次继续从与(0，0)相连的(0,2)继续遍历，如果已经标记过的则不再遍历(考虑结束退回上一个节点)，如果没有标记则继续从新的节点开始继续执行遍历。
-动态规划算法
与递归的对比，递归是自上而下的解决问题，没有从最基本的问题考虑出发，假设基本的问题已经解决了
斐波那契数列通过递归定义得到递归函数
假设已经解出n-1与n-2的斐波那契数了，求第n个数就是把n-1个数与n-2个数加在一起
递归中会有多次的重复计算
动态规划自下而上的思考问题
先解决小数据量下的问题，然后层层递推对于更大的数据量的结果是什么
大多数动态规划本质就是递归的问题，递归的过程中会有重叠子问题
-贪心算法
贪心算法尝试将最大的值去满足最贪心的数据，每次尝试都优先使用当前剩下最大的值，最大程度的满足更多贪心的值的原则
