Java算法总结
2021-03-05 10:26:54 1 举报AI智能生成
讲述了基于java基础的常用算法，进行了区别，使用场景的描述。除了排序、查询还牵涉到加解密等实际场景中使用到的算法归纳总结。希望对大家有所帮助！
作者其他创作
大纲/内容
数据结构
栈（stack）
栈（stack）是限制插入和删除只能在一个位置上进行的表
该位置是表的末端，叫做栈顶（top）。
它是后进先出（LIFO）的
对栈的基本操作只有 push（进栈）和 pop（出栈）两种，<br>前者相当于插入，后者相当于删除最后的元素。
队列（queue）
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作
而在表的后端（rear）进行插入操作
栈一样，队列是一种操作受限制的线性表
进行插入操作的端称为队尾，进行删除操作的端称为队头
链表（Link）
链表是一种数据结构，和数组同级
Java 中我们使用的 ArrayList，其实现原理是数组<br>（LinkedList 的实现原理就是链表）<br>
链表在进行循环遍历时效率不高，但是插入和删除时优势明显
散列表（Hash Table）
散列表（Hash table，也叫哈希表）是一种查找算法
与链表、树等算法不同的是，散列表算法在查找时不需要进行一系列和关键字
散列表算法希望能尽量做到不经过任何比较，通过一次存取就能得到所查找的数据元素
排序二叉树
左子树所有节点值小于它的根节点值
且右子树所有节点值大于它的根节点值
则这样的二叉树就是排序二叉树
先和根节点比较，如果相同就返回，如果小于根节点则到左子树中递归查找，如果大于根节点则到右子树中递归查找。<br>因此在排序二叉树中可以很容易获取最大（最右最深子节点）和最小（最左最深子节点）值。<br>
BST（二叉查找树）
AVL（平衡二叉树）
红黑树
红黑树是牺牲了严格的高度平衡的优越条件为代价，它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能
红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作
此外，由于它的设计，任何不平衡都会在三次旋转之内解决
红黑树能够给我们一个比较“便宜”的解决方案
优点
红黑树可以能确保树的最长路径不大于两倍的最短路径的长度
在最坏的情况下也可以保证O(logN)的，这是要好于<b>二叉查找树</b>的
红黑树的算法时间复杂度和<b>AVL</b>相同，但统计性能比AVL树更高
B-TREE
B-tree 又叫平衡多路查找树
一棵 m 阶的 B-tree (m 叉树)的特性如下（其中 ceil(x)是一个取上限<br>的函数）：
1. 树中每个结点至多有 m 个孩子；
2. 除根结点和叶子结点外，其它每个结点至少有有 ceil(m / 2)个孩子；
3. 若根结点不是叶子结点，则至少有 2 个孩子（特殊情况：没有孩子的根结点，即根结点为叶子<br>结点，整棵树只有一个根节点）；
4. 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部结点或查询<br>失败的结点，实际上这些结点不存在，指向这些结点的指针都为 null)；
B+tree<br>
一棵 m 阶的 B+tree 和 m 阶的 B-tree 的差异在于
1.有 n 棵子树的结点中含有 n 个关键字； (B-tree 是 n 棵子树有 n-1 个关键字)
2.所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本<br>身依关键字的大小自小而大的顺序链接。 (B-tree 的叶子节点并没有包括全部需要查找的信息)
3.所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。
(B-tree 的非终节点也包含需要查找的有效信息)
位图
位图的原理就是用一个 bit 来标识一个数字是否存在
采用一个 bit 来存储一个数据，所以这样可以大大的节省空间
bitmap 是很常用的数据结构，比如用于 Bloom Filter 中
用于无重复整数的排序等等
bitmap 通常基于数组来实现，数组中每个元素可以看成是一系列二进制数，所有元素
组成更大的二进制集合。
加密算法
AES
高级加密标准(AES,Advanced Encryption Standard)为最常见<br>的对称加密算法(微信小程序加密传输就是用这个加密算法的)。<br>
对称加密算法也就是加密和解密用相同的密钥
RSA
RSA 加密算法是一种典型的非对称加密算法，它基于大数的<br>因式分解数学难题，它也是应用最广泛的非对称加密算法。<br>
非对称加密是通过两个密钥（公钥-私钥）来实现对数据的<br>加密和解密的。公钥用于加密，私钥用于解密。<br>
RSA加解密流程
CRC
循环冗余校验(Cyclic Redundancy Check, CRC)是一种根据<br>网络数据包或电脑文件等数据产生简短固定位数校验码的一种散列函数<br>
主要用来检测或校验数据传输或者保存后可能出现的错误。
它是利用除法及余数的原理来作错误侦测的。
MD5
MD5 常常作为文件的签名出现
另一种常见用途就是网站敏感信<br>息加密，比如用户名密码，支付签名等等<br>
常用算法
二分查找
又叫折半查找，要求待查找的序列有序。
每次取中间位置的值与待查关键字比较
如果中间位置的值比待查关键字大，则在前半部分循环这个查找的过程
冒泡排序算法<br>（两个for循环）<br>
（1）比较前后相邻的二个数据，如果前面数据大于后面的数据，就将这二个数据交换
（2）这样对数组的第 0 个数据到 N-1 个数据进行一次遍历后，最大的一个数据就“沉”到数组第<br>N-1 个位置。
（3）N=N-1，如果 N 不为 0 就重复前面二步，否则排序完成。
插入排序算法<br>（for 加 while循环）
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入
插入排序非常类似于整<b>扑克牌</b>
一次从桌上摸起一张牌，并将它插入到左手一把牌中的正确位置上
为了找到这张牌的正确位置，要将它与手中已有的牌从右到左地进行比较
无论什么时候，左手中的牌都是排好序的。
快速排序算法
选择一个关键值作为基准值
比基准值小的都在左边序列（一般是无序的）
比基准值大的都在右边（一般是无序的）。一般选择序列的第一个元素。
希尔排序算法
基本思想
基本思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，
待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
步骤
1. 操作方法：选择一个增量序列 t1，t2，…，tk，其中 ti>tj，tk=1；
2. 按增量序列个数 k，对序列进行 k 趟排序；
3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序<br>仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度<br>
归并排序算法
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表
即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列
桶排序算法
桶排序的基本思想是： 把数组 arr 划分为 n 个大小相同子区间（桶），每个子区间各自排序，最后合并
计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况
逻辑
1.找出待排序数组中的最大值 max、最小值 min
2.我们使用 动态数组 ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。<br>桶的数量为(maxmin)/arr.length+1<br>
3.遍历数组 arr，计算每个元素 arr[i] 放的桶
4.每个桶各自排序
基数排序算法
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零
然后，从最低位开始，依次进行一次排序。
这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列
剪枝算法
在搜索算法中优化中，剪枝，就是通过某种判断，避免一些不必要的遍历过程
就是剪去了搜索树中的某些“枝条”，故称剪枝
应用剪枝优化的核心问题是设计剪枝判断方法，即
确定哪些枝条应当舍弃，哪些枝条应当保留的方法
回溯算法
回溯算法实际上一个类似枚举的搜索尝试过程
主要是在搜索尝试过程中寻找问题的解，当发现<br>已不满足求解条件时，就“回溯”返回，尝试别的路径。
最短路径算法
从某顶点出发，沿图的边到达另一顶点所经过的路径中
各边上权值之和最小的一条路径叫做最短路径
解决最短路的问题有以下算法，Dijkstra 算法，<br>Bellman-Ford 算法，Floyd 算法和 SPFA算法等<br>
最大子数组算法
最长公共子序算法
最小生成树算法
n 个城市就是图上的 n 个顶点，然后，边表示两个城市的通信线路，每条边上的权重就是我们搭建这条线路所需要的成本
现在我们有 n 个顶点的连通网可以建立不同的生成树
每一颗生成树都可以作为一个通信网
当我们构造这个连通网所花的成本最小时，搭建该连通网的生成树，就称为最小生成树
MST 性质生成最小生成树的算法：普里姆算法和克鲁斯卡尔算法
0 条评论
下一页
