有哪些JAVA必须掌握的数据结构和算法
本篇内容主要讲解"有哪些JAVA必须掌握的数据结构和算法"，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习"有哪些JAVA必须掌握的数据结构和算法"吧!
常见的数据结构
链表
LinkedHashSet LinkedList 底层数据结构由链表和哈希表组成。
数据的添加和删除都较为方便，就是访问比较耗费时间。
数组
ArrayList 访问数据十分简单，而添加和删除数据比较耗工夫
堆
堆是一种图的树形结构，被用于实现"优先队列",优先队列是一种数据结构，可以自由添加数据，但取出数据时要从最小值开始按顺序取出
堆的特点：
①堆中的每个结点最多有两个子结点
②子结点必定大于父结点
③把新数据放在最下面一行靠左的位置。当最下面一行里没有多余空间时，就再往下另起一行，把数据加在这一行的最左端
④如果子结点的数字小于父结点的，就将父结点与其左右两个子结点中较小的一个进行交换
堆中最顶端的数据始终最小，所以无论数据量有多少，取出最小值的时间复杂度都为O（1）
可知树的高度为log2n，那么重构树的时间复杂度便为O（logn）
栈 （LIFO）
略
队列 (FIFO)
略
哈希表 HashSet
TreeSet底层数据结构是红黑树
哈希函数（Hash）计算key,哈希值除以数组的长度5，求得其余数。这个余数就是key的编号即位置
如果发生哈希冲突，就使用链表进行存储（链地址法）给数组设定合适的空间非常重要
除了链地址法以外，还有几种解决冲突的方法。其中，应用较为广泛的是"开放地址法"。这种方法是指当冲突发生时，立刻计算出一个候补地址（数组上的位置）并将数据存进去。如果仍然有冲突，便继续计算下一个候补地址，直到有空地址为止。可以通过多次使用哈希函数或"线性探测法"等方法计算候补地址。
二叉树
特点：
①第一个是每个结点的值均大于其左子树上任意一个结点的值
②是每个结点的值均小于其右子树上任意一个结点的值
③二叉查找树的最小结点要从顶端开始，往其左下的末端寻找。此处最小值为3。
④二叉查找树的最大结点要从顶端开始，往其右下的末端寻找
添加数据的时候 与顶端数据比较 如果比他小就往左移，左边没有节点了就把插入的数据作为新节点添加到左下方，大于他则往右移（左小右大）
删除数据的时候 如果节点没有子节点 直接删 如果有一个 删了后子节点补上，如果有两个，删掉后从左子树中中找最大的补上
比较的次数取决于树的高度。所以如果结点数为n，而且树的形状又较为均衡的话，比较大小和移动的次数最多就是log2n。因此，时间复杂度为O（logn）。但是，如果树的形状朝单侧纵向延伸，树就会变得很高，此时时间复杂度也就变成了O（n）。
常见的算法整理
排序
冒泡排序
冒泡排序就是重复"从序列右边开始比较相邻两个数字的大小，再根据结果交换两个数字的位置"这一操作的算法。在这个过程中，数字会像泡泡一样，慢慢从右往左"浮"到序列的顶端，所以这个算法才被称为"冒泡排序"
冒泡排序的时间复杂度为O（n2）选择排序
选择排序就是重复"从待排序的数据中寻找最小值，将其与序列最左边的数字进行交换"这一操作的算法。在序列中寻找最小值时使用的是线性查找
每轮中交换数字的次数最多为1次。如果输入数据就是按从小到大的顺序排列的，便不需要进行任何交换。选择排序的时间复杂度也和冒泡排序的一样，都为O（n2）。插入排序
插入排序的思路就是从右侧的未排序区域内取出一个数据，然后将它插入到已排序区域内合适的位置上
时间复杂度和冒泡排序的一样，都为O（n2）。堆排序
首先堆中存储所有的数据，并按降序来构建堆，然后从降序排列的堆中取出数据时会从最大的数据开始取，所以将取出的数据反序输出，排序就完成了。
堆排序的时间复杂度为O（nlogn）。归并排序
归并排序算法会把序列分成长度相同的两个子序列，当无法继续往下分时（也就是每个子序列中只有一个数据时），就对子序列进行归并。归并指的是把两个排好序的子序列合并成一个有序序列。该操作会一直重复执行，直到所有子序列都归并为一个整体为止。
运行时间复杂度为O（nlogn）快速排序
快速排序算法首先会在序列中随机选择一个基准值（pivot），然后将除了基准值以外的数分为"比基准值小的数"和"比基准值大的数"这两个类别。解决子问题的时候会再次使用快速排序，甚至在这个快速排序里仍然要使用快速排序。只有在子问题里只剩一个数字的时候，排序才算完成。
整体的时间复杂度为O（nlogn）。
数组查找
线性查找
线性查找需要从头开始不断地按顺序检查数据，因此在数据量大且目标数据靠后，或者目标数据不存在时，比较的次数就会更多，也更为耗时。若数据量为n，线性查找的时间复杂度便为O（n）。二分查找（略）
图的搜索
广度优先搜索
广度优先搜索是一种对图进行搜索的算法。假设我们一开始位于某个顶点（即起点），此时并不知道图的整体结构，而我们的目的是从起点开始顺着边搜索，直到到达指定顶点（即终点）。在此过程中每走到一个顶点，就会判断一次它是否为终点。广度优先搜索会优先从离起点近的顶点开始搜索深度优先搜索
深度优先搜索和广度优先搜索一样，都是对图进行搜索的算法，目的也都是从起点开始搜索直到到达指定顶点（终点）。深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一条候补路径。贝尔曼-福特算法（略）
贝尔曼-福特（Bellman-Ford）算法是一种在图中求解最短路径问题的算法狄克斯特拉算法（略）
A*算法（略）
安全算法
共享密钥加密
公开密钥加密
混合加密
迪菲-赫尔曼交换
其他算法
k-means 算法
欧几里得算法
素性测试
网页排名
汉诺塔
【拓展】
图的表示：邻接矩阵和邻接表
遍历算法：深度搜索和广度搜索(必学)
最短路径算法：Floyd，Dijkstra（必学）
最小生成树算法：Prim，Kruskal（必学）
实际常用算法：关键路径、拓扑排序（原理与应用）
二分图匹配：配对、匈牙利算法（原理与应用）
拓展：中心性算法、社区发现算法（原理与应用）
2.图还是比较难的，不过我觉得图涉及到的挺多算法都是挺实用的，例如最短路径的计算等，图相关的，我这里还是建议看书的，可以看《算法第四版》。
3、搜索与回溯算法
贪心算法（必学）启发式搜索算法：A*寻路算法（了解）地图着色算法、N 皇后问题、最优加工顺序旅行商问题
这方便的只是都是一些算法相关的，我觉得如果可以，都学一下。像贪心算法的思想，就必须学的了。建议通过刷题来学习，leetcode 直接专题刷。
4、动态规划
树形DP：01背包问题线性DP：最长公共子序列、最长公共子串区间DP：矩阵最大值（和以及积）数位DP：数字游戏状态压缩DP：旅行商
我觉得动态规划是最难的一个算法思想了，记得当初第一次接触动态规划的时候，是看01背包问题的，看了好久都不大懂，懵懵懂懂，后面懂了基本思想，可是做题下不了手，但是看的懂答案。一气之下，再leetcdoe专题连续刷了几十道，才掌握了动态规划的套路，也有了自己的一套模板。不过说实话，动态规划，是考的真他妈多，学习算法、刷题，一定要掌握。这里建议先了解动态规划是什么，之后 leetcode 专题刷，反正就一般上面这几种题型。
5、字符匹配算法
正则表达式模式匹配：KMP、Boyer-Moore
6、流相关算法
最大流：最短增广路、Dinic 算法最大流最小割：最大收益问题、方格取数问题最小费用最大流：最小费用路、消遣
到此，相信大家对"有哪些JAVA必须掌握的数据结构和算法"有了更深的了解，不妨来实际操作一番吧！这里是网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！
