开始学习算法，而不是一直摆烂…

排序

排序或许是前端接触最多的算法了，很多人的算法之路是从一个冒泡排序开始的，排序的方法有非常多中，它们各自有各自的应用场景和优缺点，这里我推荐如下6种应用最多的排序方法，如果你有兴趣也可以研究下其他几种。

选择一个目标值，比目标值小的放左边，比目标值大的放右边，目标值的位置已排好，将左右两侧再进行快排。

将大序列二分成小序列，将小序列排序后再将排序后的小序列归并成大序列。

每次排序取一个最大或最小的数字放到前面的有序序列中。

将左侧序列看成一个有序序列，每次将一个数字插入该有序序列。插入时，从有序序列最右侧开始比较，若比较的数较大，后移一位。

循环数组，比较当前元素和下一个元素，如果当前元素比下一个元素大，向上冒泡。下一次循环继续上面的操作，不循环已经排序好的数。

创建一个大顶堆，大顶堆的堆顶一定是最大的元素。交换第一个元素和最后一个元素，让剩余的元素继续调整为大顶堆。从后往前以此和第一个元素交换并重新构建，排序完成。

二分查找

查找是计算机中最基本也是最有用的算法之一。 它描述了在有序集合中搜索特定值的过程。
算法导读 - 图1
二分查找维护查找空间的左、右和中间指示符，并比较查找目标或将查找条件应用于集合的中间值；如果条件不满足或值不相等，则清除目标不可能存在的那一半，并在剩下的一半上继续查找，直到成功为止。如果查以空的一半结束，则无法满足条件，并且无法找到目标。

  • 二维数组查找
  • 旋转数组的最小数字
  • 在排序数组中查找数字
  • x 的平方根

  • 猜数字大小

    递归

    递归是一种解决问题的有效方法，在递归过程中，函数将自身作为子例程调用。
    算法导读 - 图2
    你可能想知道如何实现调用自身的函数。诀窍在于，每当递归函数调用自身时，它都会将给定的问题拆解为子问题。递归调用继续进行，直到到子问题无需进一步递归就可以解决的地步。
    为了确保递归函数不会导致无限循环，它应具有以下属性：

  • 一个简单的基本案例 —— 能够不使用递归来产生答案的终止方案。

  • 一组规则，也称作递推关系，可将所有其他情况拆分到基本案例。

    重复计算

    一些问题使用递归考虑，思路是非常清晰的，但是却不推荐使用递归，例如下面的几个问题：

  • 斐波拉契数列

  • 跳台阶
  • 矩形覆盖

这几个问题使用递归都有一个共同的缺点，那就是包含大量的重复计算，如果递归层次比较深的话，直接会导致JS进程崩溃。
算法导读 - 图3
你可以使用记忆化的方法来避免重复计算，即开辟一个额外空间来存储已经计算过的值，但是这样又会浪费一定的内存空间。因此上面的问题一般会使用动态规划求解。
所以，在使用递归之前，一定要判断代码是否含有重复计算，如果有的话，不推荐使用递归。
递归是一种思想，而非一个类型，很多经典算法都是以递归为基础，因此这里就不再给出更多问题。

广度优先搜索

广度优先搜索（BFS）是一种遍历或搜索数据结构（如树或图）的算法，也可以在更抽象的场景中使用。
它的特点是越是接近根结点的结点将越早地遍历。
例如，我们可以使用 BFS 找到从起始结点到目标结点的路径，特别是最短路径。
在BFS中，结点的处理顺序与它们添加到队列的顺序是完全相同的顺序，即先进先出，所以广度优先搜索一般使用队列实现。

深度优先搜索

和广度优先搜索一样，深度优先搜索（DFS）是用于在树/图中遍历/搜索的一种重要算法。
与 BFS 不同，更早访问的结点可能不是更靠近根结点的结点。因此，你在DFS 中找到的第一条路径可能不是最短路径。
算法导读 - 图4
在DFS中，结点的处理顺序是完全相反的顺序，就像它们被添加到栈中一样，它是后进先出。所以深度优先搜索一般使用栈实现。

回溯算法

从解决问题每一步的所有可能选项里系统选择出一个可行的解决方案。
在某一步选择一个选项后，进入下一步，然后面临新的选项。重复选择，直至达到最终状态。
回溯法解决的问题的所有选项可以用树状结构表示。

  • 在某一步有n个可能的选项，该步骤可看作树中一个节点。
  • 节点每个选项看成节点连线，到达它的n个子节点。
  • 叶节点对应终结状态。
  • 叶节点满足约束条件，则为一个可行的解决方案。
  • 叶节点不满足约束条件，回溯到上一个节点，并尝试其他叶子节点。
  • 节点所有子节点均不满足条件，再回溯到上一个节点。
  • 所有状态均不能满足条件，问题无解。

算法导读 - 图5
回溯算法适合由多个步骤组成的问题，并且每个步骤都有多个选项。

动态规划

动态规划往往是最能有效考察算法和设计能力的题目类型，面对这类题目最重要的是抓住问题的阶段，了解每个阶段的状态，从而分析阶段之间的关系转化。
适用于动态规划的问题，需要满足最优子结构和无后效性，动态规划的求解过程，在于找到状态转移方程，进行自底向上的求解。
算法导读 - 图6
自底向上的求解，可以帮你省略大量的复杂计算，例如上面的斐波拉契数列，使用递归的话时间复杂度会呈指数型增长，而动态规划则让此算法的时间复杂度保持在O(n)。

路径问题

贪心算法

贪心算法：对问题求解的时候，总是做出在当前看来是最好的做法。
适用贪心算法的场景：问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。这种子问题最优解成为最优子结构
算法导读 - 图7

买卖股票类问题

贪心算法、动态规划、回溯的区别

贪心算法与动态规划的不同在于它对每个子问题的解决方案都作出选择，不能回退，动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能，而回溯算法就是大量的重复计算来获得最优解。
算法导读 - 图8
有很多算法题目都是可以用这三种思想同时解答的，但是总有一种最适合的解法，这就需要不断的练习和总结来进行深入的理解才能更好的选择解决办法。

鸣谢：转载自作者ConardLi，十分感谢！