“

这是整个架构师连载系列，分为9大步骤，我们现在还在第一个步骤：程序设计和开发->数据结构与算法。

我们今天讲解重点讲解算法。

算法思想

1 贪心思想

顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。在面临选择时，贪心算法都作出对眼前来讲最有利的选择，不考虑对将来的不良影响，每个选择一旦做出，不可更改，不允许回溯，根据不同的贪心策略，贪心算法就不同，贪心解的质量也不同，所以贪心策略很重要。可以看出，此算法思想很简单，具有高效性，但不一定得出最优解。

2 分治法

当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。

3 动态规划

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。

4 搜索法

搜索法包含穷举搜索，深度优先搜索，广度优先搜索，回溯法，分支限界法，其实这些算法的基础就是穷举搜索，只是加上一定的原则来优化过程，就形成了后面的几种算法，回溯法就是在深度优先搜索的基础上允许回溯，分支限界法是在广度优先搜索基础上允许剪枝，学习时主要学习思想，这些算法名字不要太在意。

5 新近出现的部分算法简介

①　遗传算法

从达尔文的生物进化论中得到启发，借鉴自然选择和进化的原理，模拟生物在自然界的进化过程所形成的一种优化求解方法，遗传算法从代表问题的可能潜在解集的一个种群出发，一个种群有一定数量的个体组成，每个个体实际上是染色体带有特征的实体，每一代根据个体的适应度大小挑选个体，并借助遗传算子进行交叉和变异，得到近似最优解。

②　模拟退火算法

他的出发点是物理中固体的退火过程与一般组合优化之间的相似性，固态物质退火时，通常先加温，使其中的粒子自由游动，然后逐渐降低温度，粒子也逐渐形成低能态的晶格，最终形成最低能量的基态。所以他从某一较高初温开始，伴随温度参数的不断下降重复抽样，最终得到全局最优解，他是基于概率的。

③　蚁群算法

蚁群算法是模拟自然界蚂蚁觅食过程的一种分布式，启发式群体智能算法，用于求解复杂的组合优化问题，如TSP,JSSP,GCP等问题。

6 递归法

所谓递归，就是指如果需要求解当前状态就需要求解其依赖的迁移状态。

一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

采用递归描述的算法通常有这样的特征：

1）为求解规模为N的问题，设法将它分解成规模较小的问题；

2）然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。

3）这样的分解方法具有收敛性。即存在一个递归返回状态。

7 迭代法

也称辗转法，是一种不断用变量的旧值递推新值的过程。

最常见的迭代法是牛顿法。其他还包括最速下降法、共轭迭代法、变尺度迭代法、最小二乘法、线性规划、非线性规划、单纯型法、惩罚函数法、斜率投影法、遗传算法、模拟退火等等。

利用迭代算法解决问题，需要做好以下三个方面的工作：

1）迭代变量：在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。

2）迭代关系：指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。

3）迭代过程：迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。

迭代法都可以转为递归法。迭代法可以理解为具有递归性质的非递归解法。当然，非递归解法还可利用栈的思想。

经典算法

排序算法

排序大的分类可以分为两种：内排序和外排序。在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。下面讲的排序都是属于内排序。

内排序有可以分为以下几类：

(1)、插入排序：直接插入排序、二分法插入排序、希尔排序。

(2)、选择排序：简单选择排序、堆排序。

(3)、交换排序：冒泡排序、快速排序。

(4)、归并排序

(5)、基数排序

查找算法

1. 顺序查找

2. 二分查找

3. 插值查找

4. 斐波那契查找

5. 树表查找

6. 分块查找

7. 哈希查找

查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。以上是常见的七种查找算法，说是七种，其实二分查找、插值查找以及斐波那契查找都可以归为一类——插值查找。插值查找和斐波那契查找是在二分查找的基础上的优化查找算法。

后续再详细介绍具体的数据结构。

 

 

作者简介

陈睿|mikechen，10年+大厂架构经验，BAT资深面试官，就职于阿里巴巴、淘宝、百度等一线互联网大厂。

关注作者「mikechen」公众号，获取更多技术干货！

后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》，后台回复【面试】即可获取《史上最全阿里Java面试题总结》