原文出自：公众号 浅羽的IT小屋
原文链接：
https://mp.weixin.qq.com/s/Nny41gh4vwNri06ac1_kfw
对于编程来说的话，只有掌握了算法才是了解了编程的灵魂，算法对于新手来说的话，属实有点难度，但是以后想有更好的发展，得到更好的进阶的话，对算法进行系统的学习是重中之重的。
对于 JAVA 程序员来说，这一门后端语言只是我们的外功，我们更多的是学习它的语法，框架以及一些工具的使用。而算法才是我们真正的内功，它更多的是关注如何设计系统，如何编写高性能的代码，不断培养我们的思维能力，从而提升我们的工作效率。
小羽今天为大家介绍的是关于 Java 中我们需要了解的一些经典算法，希望大家能从这些经典算法中，品尝到算法的美妙与奇特，对她产生兴趣，更好的为我们的职业发展助力前行。好了，开始进入我们的正文：
二分查找
简介
基本思想：又叫折半查找，要求待查找的序列有序，是一种快速查找算法，时间复杂度为 O(logn)，要求数据集为一个有序数据集。
使用
应用场景：一般用于查找数组元素，并且数组在查找之前必须已经排好序（一般是升序）。
步骤：
1、取中间位置的值与待查关键字比较，如果中间位置的值比待查关键字大，则在前半部分循环这个查找的过程，
2、如果中间位置的值比待查关键字小，则在后半部分循环这个查找的过程。
3、直到查找到了为止，否则序列中没有待查的关键字。
代码示例：
public static int biSearch(int []array,int a){
int lo=0;
int hi=array.length-1;
int mid;
while(lo<=hi){
mid=(lo+hi)/2;//中间位置
if(array[mid]==a){
return mid+1;
}else if(array[mid]<a){ //向右查找
lo=mid+1;
}else{ //向左查找
hi=mid-1;
}
}
return -1;
}
冒泡排序算法
简介
基本思想：比较前后相邻的两个数据，如果前面数据大于后面的数据，就将这二个数据交换。这样对数组的第 0 个数据到 N-1 个数据进行一次遍历后，最大的一个数据就“沉”到数组第 N-1 个位置。N=N-1，如果 N 不为 0 就重复前面二步，否则排序完成。
使用
应用场景：数据量不大，对稳定性有要求，且数据基本有序的情况。
步骤：
1、将序列中所有元素两两比较，将最大的放在最后面。
2、将剩余序列中所有元素两两比较，将最大的放在最后面。
3、重复第二步，直到只剩下一个数。
代码示例：
public static void bubbleSort1(int [] a, int n){
int i, j;
for(i=0; i<n; i++){//表示 n 次排序过程。
for(j=1; j<n-i; j++){
if(a[j-1] > a[j]){//前面的数字大于后面的数字就交换
//交换 a[j-1]和 a[j]
int temp;
temp = a[j-1];
a[j-1] = a[j];
a[j]=temp;
}
}
}
}
插入排序算法
简介
基本思想：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入。
使用
应用场景：数据量不大，对算法的稳定性有要求，且数据局部或者整体有序的情况。
步骤：
1、将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
2、从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
代码示例：
public class InsertSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝，不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
// 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
for (int i = 1; i < arr.length; i++) {
// 记录要插入的数据
int tmp = arr[i];
// 从已经排序的序列最右边的开始比较，找到比其小的数
int j = i;
while (j > 0 && tmp < arr[j - 1]) {
arr[j] = arr[j - 1];
j--;
}
// 存在比其小的数，插入
if (j != i) {
arr[j] = tmp;
}
}
return arr;
}
}
快速排序算法
简介
基本思想：选择一个关键值作为基准值。比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一般是无序的）。一般选择序列的第一个元素。
使用
应用场景：数值范围较大，相同值的概率较小，数据量大且不考虑稳定性的情况，数值远大于数据量时威力更大。
步骤：
1、一次循环，从后往前比较，用基准值和最后一个值比较，如果比基准值小的交换位置，如果没有继续比较下一个，直到找到第一个比基准值小的值才交换。
2、找到这个值之后，又从前往后开始比较，如果有比基准值大的，交换位置，如果没有继续比较下一个，直到找到第一个比基准值大的值才交换。
3、直到从前往后的比较索引 > 从后往前比较的索引，结束第一次循环，此时，对于基准值来说，左右两边就是有序的了。
代码示例：
public void sort(int[] a,int low,int high){
int start = low;
int end = high;
int key = a[low];
while(end>start){
//从后往前比较
while(end>start&&a[end]>=key)
//如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
end--;
if(a[end]<=key){
int temp = a[end];
a[end] = a[start];
a[start] = temp;
}
//从前往后比较
while(end>start&&a[start]<=key)
//如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
start++;
if(a[start]>=key){
int temp = a[start];
a[start] = a[end];
a[end] = temp;
}
//此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
}
//递归
if(start>low) sort(a,low,start-1);//左边序列。第一个索引位置到关键值索引-1
if(end<high) sort(a,end+1,high);//右边序列。从关键值索引+1 到最后一个
}
}
希尔排序算法
简介
基本思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
使用
应用场景：数据量较大，不要求稳定性的情况。
步骤：
1、选择一个增量序列 t1，t2，…，tk，其中 ti>tj，tk=1；
2、按增量序列个数 k，对序列进行 k 趟排序；
3、每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
代码示例：
private void shellSort(int[] a) {
int dk = a.length/2;
while( dk >= 1 ){
ShellInsertSort(a, dk);
dk = dk/2;
}
}
private void ShellInsertSort(int[] a, int dk) {
//类似插入排序，只是插入排序增量是 1，这里增量是 dk,把 1 换成 dk 就可以了
for(int i=dk;i<a.length;i++){
if(a[i]<a[i-dk]){
int j;
int x=a[i];//x 为待插入元素
a[i]=a[i-dk];
for(j=i-dk; j>=0 && x<a[j];j=j-dk){
//通过循环，逐个后移一位找到要插入的位置。
a[j+dk]=a[j];
}
a[j+dk]=x;//插入
}
}
}
归并排序算法
简介
基本思想：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
场景使用
应用场景：内存少的时候使用，可以进行并行计算的时候使用。
步骤：
1、选择相邻两个数组成一个有序序列。
2、选择相邻的两个有序序列组成一个有序序列。
3、重复第二步，直到全部组成一个有序序列。
代码示例：
public class MergeSortTest {
public static void main(String[] args) {
int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };
print(data);
mergeSort(data);
System.out.println("排序后的数组：");
print(data);
}
public static void mergeSort(int[] data) {
sort(data, 0, data.length - 1);
}
public static void sort(int[] data, int left, int right) {
if (left >= right)
return;
// 找出中间索引
int center = (left + right) / 2;
// 对左边数组进行递归
sort(data, left, center);
// 对右边数组进行递归
sort(data, center + 1, right);
// 合并
merge(data, left, center, right);
print(data);
}
/**
* 将两个数组进行归并，归并前面 2 个数组已有序，归并后依然有序
* @param data
* 数组对象
* @param left
* 左数组的第一个元素的索引
* @param center
* 左数组的最后一个元素的索引，center+1 是右数组第一个元素的索引
* @param right
* 右数组最后一个元素的索引
*/
public static void merge(int[] data, int left, int center, int right) {
// 临时数组
int[] tmpArr = new int[data.length];
// 右数组第一个元素索引
int mid = center + 1;
// third 记录临时数组的索引
int third = left;
// 缓存左数组第一个元素的索引
int tmp = left;
while (left <= center && mid <= right) {
// 从两个数组中取出最小的放入临时数组
if (data[left] <= data[mid]) {
tmpArr[third++] = data[left++];
} else {
tmpArr[third++] = data[mid++];
}
}
// 剩余部分依次放入临时数组（实际上两个 while 只会执行其中一个）
while (mid <= right) {
tmpArr[third++] = data[mid++];
}
while (left <= center) {
tmpArr[third++] = data[left++];
}
// 将临时数组中的内容拷贝回原数组中
// （原 left-right 范围的内容被复制回原数组）
while (tmp <= right) {
data[tmp] = tmpArr[tmp++];
}
}
public static void print(int[] data) {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + "t");
}
System.out.println();
}
}
桶排序算法
简介
基本思想： 把数组 arr 划分为 n 个大小相同子区间（桶），每个子区间各自排序，最后合并 。计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。
使用
应用场景：在数据量非常大，而空间相对充裕的时候是很实用的，可以大大降低算法的运算数量级。
步骤：
1、找出待排序数组中的最大值 max、最小值 min
2、我们使用动态数组 ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为(maxmin)/arr.length+1
3、遍历数组 arr，计算每个元素 arr[i] 放的桶
4、每个桶各自排序
代码示例：
public static void bucketSort(int[] arr){
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i = 0; i < arr.length; i++){
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
//创建桶
int bucketNum = (max - min) / arr.length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for(int i = 0; i < bucketNum; i++){
bucketArr.add(new ArrayList<Integer>());
}
//将每个元素放入桶
for(int i = 0; i < arr.length; i++){
int num = (arr[i] - min) / (arr.length);
bucketArr.get(num).add(arr[i]);
}
//对每个桶进行排序
for(int i = 0; i < bucketArr.size(); i++){
Collections.sort(bucketArr.get(i));
}
}
基数排序算法
简介
基本思想：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
使用
应用场景：用于大量数，很长的数进行排序时的情况。
步骤：
1、将所有的数的个位数取出，按照个位数进行排序，构成一个序列。
2、将新构成的所有的数的十位数取出，按照十位数进行排序，构成一个序列。
代码示例：
public class radixSort {
inta[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,101,56,17,18,23,34,15,35,25,53,51};
public radixSort(){
sort(a);
for(inti=0;i<a.length;i++){
System.out.println(a[i]);
}
}
public void sort(int[] array){
//首先确定排序的趟数;
int max=array[0];
for(inti=1;i<array.length;i++){
if(array[i]>max){
max=array[i];
}
}
int time=0;
//判断位数;
while(max>0){
max/=10;
time++;
}
//建立 10 个队列;
List<ArrayList> queue=newArrayList<ArrayList>();
for(int i=0;i<10;i++){
ArrayList<Integer>queue1=new ArrayList<Integer>();
queue.add(queue1);
}
//进行 time 次分配和收集;
for(int i=0;i<time;i++){
//分配数组元素;
for(intj=0;j<array.length;j++){
//得到数字的第 time+1 位数;
int x=array[j]%(int)Math.pow(10,i+1)/(int)Math.pow(10, i);
ArrayList<Integer>queue2=queue.get(x);
queue2.add(array[j]);
queue.set(x, queue2);
}
int count=0;//元素计数器;
//收集队列元素;
for(int k=0;k<10;k++){
while(queue.get(k).size()>0){
ArrayList<Integer>queue3=queue.get(k);
array[count]=queue3.get(0);
queue3.remove(0);
count++;
}
}
}
}
}
剪枝算法
简介
基本思想：在搜索算法中优化中，剪枝，就是通过某种判断，避免一些不必要的遍历过程，形象的说，就是剪去了搜索树中的某些“枝条”，故称剪枝。应用剪枝优化的核心问题是设计剪枝判断方法，即确定哪些枝条应当舍弃，哪些枝条应当保留的方法。
使用
应用场景：通常应用在 DFS 和 BFS 搜索算法中，寻找过滤条件，提前减少不必要的搜索路径。
步骤：
1、基于训练数据集生成决策树，生成的决策树要尽量大；
2、用验证数据集最已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准
代码示例：
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
LinkedList<Integer> track = new LinkedList<>();
combinationSum(candidates, 0, target, track);
return result;
}
private List<List<Integer>> result = new ArrayList<>();
private void combinationSum(int[] candidates, int start, int target, LinkedList<Integer> track) {
if (target < 0) {
return;
} else if (target == 0) {
result.add(new LinkedList<>(track));
return;
}
for (int i = start; i < candidates.length; i++) {
if (target < candidates[i]) {
break;
}
track.add(candidates[i]);
combinationSum(candidates, i, target - candidates[i], track);
track.removeLast();
}
}
}
回溯算法
简介
基本思想：回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
使用
应用场景：设置一个递归函数，函数的参数会携带一些当前的可能解的信息，根据这些参数得出可能解或者不可能而回溯，平时经常见的有 N 皇后、数独、集合等情况。
步骤：
1、定义一个解空间，它包含问题的解；
2、利用适于搜索的方法组织解空间；
3、利用深度优先法搜索解空间；
4、利用限界函数避免移动到不可能产生解的子空间。
代码示例：
function backtrack(n, used) {
// 判断输入或者状态是否非法
if (input/state is invalid) {
return;
}
// 判读递归是否应当结束，满足结束条件就返回结果
if (match condition) {
return some value;
}
// 遍历当前所有可能出现的情况，并尝试每一种情况
for (all possible cases) {
// 如果上一步尝试会影响下一步尝试，需要写入状态
used.push(case)
// 递归进行下一步尝试，搜索该子树
result = backtrack(n + 1, used)
// 在这种情况下已经尝试完毕，重置状态，以便于下面的回溯尝试
used.pop(case)
}
}
最短路径算法
简介
基本思想：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径叫做最短路径。解决最短路的问题有以下算法，Dijkstra 算法，Bellman-Ford 算法，Floyd 算法和 SPFA 算法等。
使用
应用场景：应用有计算机网络路由算法，机器人探路，交通路线导航，人工智能，游戏设计等。
步骤：（Dijkstra 算法示例）
1、 访问路网中里起始点最近且没有被检查过的点，把这个点放入 OPEN 组中等待检查。
2、 从OPEN表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到 CLOSE 表中。
3、 遍历考察这个点的子节点。求出这些子节点距起始点的距离值，放子节点到 OPEN 表中。
4、重复2，3，步。直到 OPEN 表为空，或找到目标点。
代码示例：
//Dijkstra 算法
static int[] pathSrc = new int[9];
static int[] shortPath = new int[9];
static void shortestPath_DijkStra(MGraph m, int v0) {
// finalPath[w] = 1 表示已经获取到顶点V0到Vw的最短路径
int[] finalPath = new int[9];
for (int i = 0; i < m.numVertexes; i++) {
finalPath[i] = 0;
shortPath[i] = m.arc[v0][i];
pathSrc[i] = 0;
}
// v0到v0的路径为0
shortPath[v0] = 0;
// vo到v0不需要求路径
finalPath[v0] = 1;
for (int i = 1; i < m.numVertexes; i++) {
// 当前所知的离V0最近的距离
int min = INFINITY;
int k = 0;
for (int w = 0; w < m.numVertexes; w++) {
if(shortPath[w] < min && finalPath[w] == 0) {
min = shortPath [w];
k = w;
}
}
finalPath[k] = 1; // 修改finalPath的值，标记为已经找到最短路径
for (int w = 0; w < m.numVertexes; w++) {
// 如果经过V顶点的路径比原来的路径（不经过V）短的话
if(finalPath[w] == 0 && (min + m.arc[k][w]) < shortPath[w]) {
// 说明找到了更短的路径，修改
shortPath[w] = min + m.arc[k][w]; // 修改路径的长度
pathSrc[w] = k; // 修改顶点下标W的前驱顶点
}
}
}
}
最大子数组算法
简介
基本思想：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
使用
应用场景：生活中可以用来查看股票一周之内的增长状态，需要得到最合适的买入和卖出时间。
步骤：
1、将子串和为负数的子串丢掉，只留和为正的子串。
2、如果 nums 中有正数，从左到右遍历 nums，用变量 cur 记录每一步的累加和，遍历到正数 cur 增加，遍历到负数 cur 减少。
3、当 cur>=0 时，每一次累加都可能是最大的累加和，所以，用另外一个变量 max 全程跟踪记录 cur 出现的最大值即可。
代码示例：
class Solution {
public:
/*
* @param nums: A list of integers
* @return: A integer indicate the sum of max subarray
*/
int maxSubArray(vector<int> nums) {
if(nums.size()<=0){
return 0;
}
int max=INT_MIN,cur=0;//c++最小值
for(int i=0; i<nums.size(); i++)
{
if(cur < 0)
cur = nums[i];//如果前面加起来的和小于0，抛弃前面的
else
cur+=nums[i];
if(cur > max)
max = cur;
}
return max;
}
};
最长公共子序算法
简介
基本思想：最长公共子序列是一个在一个序列集合中用来查找所有序列中最长子序列的问题。这与查找最长公共子串的问题不同的地方是：子序列不需要在原序列中占用连续的位置。
使用
应用场景：最长公共子序列问题是一个经典的计算机科学问题，也是数据比较程序，比如 Diff 工具，和生物信息学应用的基础。它也被广泛地应用在版本控制，比如 Git 用来调和文件之间的改变。
步骤：
1、可以使用递归去解决，需要遍历出所有的可能，很慢；
2、对于一般的 LCS 问题，都属于 NP 问题；
3、当数列的量为一定的时，都可以采用动态规划去解决。
代码示例：
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int length1 = text1.length();
int length2 = text2.length();
int[][] a = new int[length1 + 1][length2 + 1];//0行0列保留
for(int i = 1; i <= length1; i++){
for(int j = 1; j <= length2; j++){
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
a[i][j] = a[i - 1][j - 1] + 1;
} else {
if (a[i][j - 1] > a[i-1][j]) {
a[i][j] = a[i][j - 1];
} else {
a[i][j] = a[i - 1][j];
}
}
}
}
return a[length1][length2];
}
}
最小生成树算法
简介
基本思想：在含有n个顶点的带权无向连通图中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树（不一定唯一）。
一般情况，要解决最小生成树问题，通常采用两种算法：Prim算法和Kruskal算法。
使用
应用场景：一般用来计算成本最小化的情况。
步骤：（Prim 算法示例）
1、以某一个点开始，寻找当前该点可以访问的所有的边；
2、在已经寻找的边中发现最小边，这个边必须有一个点还没有访问过，将还没有访问的点加入我们的集合，记录添加的边；
3、寻找当前集合可以访问的所有边，重复 2 的过程，直到没有新的点可以加入；
4、此时由所有边构成的树即为最小生成树。
代码示例：
/** prim算法
* @param first 构成最小生成树的起点的标识
* @return 返回最小生成树构成的边
*/
public List<Edge> generateMinTreePrim(T first){
//存储最小生成树构成的边
List<Edge> result=new LinkedList<>();
//首先建立map，key为vertex，value为edge
HashMap<Vertex<T>, Edge> map=new HashMap<>();
Iterator<Vertex<T>> vertexIterator=getVertexIterator();
Vertex<T> vertex;
Edge edge;
while(vertexIterator.hasNext()){
//一开始，value为edge的两端的都为自己，weight=maxDouble
vertex=vertexIterator.next();
edge=new Edge(vertex, vertex, Double.MAX_VALUE);
map.put(vertex, edge);
}
//first是构成最小生成树的起点的标识
vertex=vertexMap.get(first);
if(vertex==null){
System.out.println("没有节点："+first);
return result;
}
//所有不在生成树中的节点，都是map的key,如果map为空，代表所有节点都在树中
while(!map.isEmpty()){
//这次循环要加入生成树的节点为vertex，边为vertex对应的edge（也就是最小的边）
edge=map.get(vertex);
//每将一个结点j加入了树A，首先从map中去除这个节点
map.remove(vertex);
result.add(edge);
System.out.println("生成树加入边，顶点："+vertex.getLabel()+
" ，边的终点是："+edge.getEndVertex().getLabel()+" ，边的权值为： "+edge.getWeight());;
//如果是第一个节点，对应的边是到自己的，删除
if(vertex.getLabel().equals(first)){
result.remove(edge);
}
//然后看map中剩余的节点到节点j的距离，如果这个边的距离小于之前边的距离，就将边替换成这个到节点j的边
//在遍历替换中，同时发现距离最短的边minEdge
Edge minEdge=new Edge(vertex, vertex, Double.MAX_VALUE);
for(Vertex<T> now:map.keySet()){
edge=map.get(now);
//newEdge为now到节点j的边
Edge newEdge=now.hasNeighbourVertex(vertex);
if(newEdge!=null&&newEdge.getWeight()<edge.getWeight()){
//如果这个边的距离小于之前边的距离，就将边替换成这个到节点j的边
edge=newEdge;
map.put(now, edge);
}
if(edge.getWeight()<minEdge.getWeight()){
//更新minEdge
minEdge=edge;
}
}
//这里设定边的方向是不在树上的v（为起始点）到树上的u
//这条边的起始点是不在树上的，是下一个加入生成树的节点
vertex=minEdge.getBeginVertex();
}
return result;
}
最后
算法无论是对于学习还是工作，都是必不可少的。如果说我们掌握了这些算法背后的逻辑思想，那么是会对我们的学习和工作有很好的促进作用的。
其次算法对于面试，尤其是进入一些大厂 BAT 等公司都是一块敲门砖，大公司都会通过算法来评估你的整体技术水平，如果你有很好的算法功底，相信对你未来的职场道路也会有很大帮助。
在职业发展后期，拥有良好的算法技能，可以帮助我们更快、更高效的完成编码，往架构师的方向发展，同样的岗位，你有相应的算法知识的话，能拿到的薪资也会比别人更好一点。
当然，算法远不止这些罗列的，还有很多复杂的算法需要去不断学习，一起加油吧～
