基础算法及应用情景

所谓算法，简单来说就是解决问题的方法。算法与我们的日常生活息息相关，不管有意还是无意，我们实际上经常使用不同算法在解决着各种问题，只是我们意识不到这是一种算法而已。本文主要简单介绍了三个最基础的排序算法和六个算法策略，及生活中的一些应用情景，不涉及具体的代码实现。

排序算法

冒泡排序(Bubble Sort)

冒泡排序是一种极其简单的排序算法，它的要点是重复地走访过要排序的元素，依次比较相邻两个元素，如果他们的顺序错误就把他们调换过来，直到没有元素再需要交换，排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序算法的具体步骤如下：

1. 比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

冒泡排序的实现过程如下所示：

冒泡排序1.gif

使用冒泡排序为一列数字进行排序的宏观过程：

冒泡排序2.gif

选择排序(Selection Sort)

选择排序也是一种简单直观的排序算法。它的工作原理很容易理解：初始时在序列中找到最小（大）元素，放到序列的起始位置作为已排序序列；然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

注意选择排序与冒泡排序的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。

选择排序的实现过程如下所示：

选择排序1.gif

使用选择排序为一列数字进行排序的宏观过程：

选择排序2.gif

插入排序(Insertion Sort)

插入排序的工作原理非常类似于我们抓扑克牌

插入排序1.jpeg

对于未排序数据(右手抓到的牌)，在已排序序列(左手已经排好序的手牌)中从后向前扫描，找到相应位置并插入。

具体算法描述如下：

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5

插入排序的实现过程如下所示：

插入排序2.gif

使用插入排序为一列数字进行排序的宏观过程：

插入排序3.gif

基础算法思想

穷举法

穷举法的基本思想是根据题目的部分条件确定答案的大致范围，并在此范围内对所有可能的情况逐一验证，直到全部情况验证完毕。若某个情况验证符合题目的全部条件，则为本问题的一个解；若全部情况验证后都不符合题目的全部条件，则本题无解。穷举法也称为枚举法。

穷举法是一种针对于密码的破译方法。简单来说就是将密码进行逐个推算直到找出真正的密码为止。比如一个四位并且全部由数字组成其密码共有10000种组合，也就是说最多我们会尝试9999次才能找到真正的密码。利用这种方法我们可以运用计算机来进行逐个推算，也就是说用我们破解任何一个密码也都只是一个时间问题。
当然如果破译一个有8位而且有可能拥有大小写字母、数字、以及符号的密码用普通的家用电脑可能会用掉几个月甚至更多的时间去计算，其组合方法可能有几千万亿种组合。这样长的时间显然是不能接受的。其解决办法就是运用字典，所谓“字典”就是给密码锁定某个范围，比如英文单词以及生日的数字组合等，所有的英文单词不过10万个左右这样可以大大缩小密码范围，很大程度上缩短了破译时间。

一句话总结：穷举法简单粗暴，只要时间足够，没有什么问题是搞不定的。

分治算法

分治法是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

分治法解题的一般步骤：

1. 分解，将要解决的问题划分成若干规模较小的同类相互独立的问题；
2. 求解，当子问题划分得足够小时，用较简单的方法解决；
3. 合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

应用实例：现有16个硬币，其中一个为较轻的假币，给你个天平，如何最快找出假币

1. 将所有的硬币等分为两份，放在天平的两端；
2. 因为假硬币分量比较轻，因此天平较轻的一端一定包含假硬币
3. 再将较轻的一侧中的硬币等分为两部分，重述上方的做法，直到最后剩下两个硬币，较轻的那个即为假币。

一句话总结：分治算法就是把一个困难的问题分为一系列独立的子问题，分而治之，各个击破。

贪婪算法

贪婪算法（又指贪心算法）的特点是在对问题求解时，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不需要回溯。

贪心算法的基本思路如下：

1. 把求解的问题分成若干个子问题。
2. 对每个子问题求解，得到每个子问题的局部最优解。
3. 把每个子问题的局部最优解合成为原来问题的一个解。

应用实例：人民币支付问题
现在去超市买东西，结账时，要求支付一定金额的现金，那么，按照生活常识，我们肯定会选择尽可能少的拿出钱的张数去满足支付金额，比如说：应付628元，这时候，我的钱包里有足够多的以下面额的钱：100，50，20，10，5，2，1，那么，我肯定会拿出6张100块的，1张20的，1张5块的，1张2块的，最后再拿出1张1块的，6*100+20+5+2+1 = 628；那么我用10张就可以愉快的完成支付了，正常情况下，绝对不会拿628张1块的去支付或者其它，这就是贪心选择策略。

一句话总结：自顶而下，不断贪心的选取当前最优选择。

动态规划算法

算法思想：与分治法相似，也是通过组合子问题的解而解决整个问题。区别是，动态规划适用于分解得到的子问题往往不是相互独立的。在这种情况下如果采用分治法，有些子问题会被重复计算多次，动态规划通过记录已解决的子问题，可以避免重复计算。

动态规划通常用于求解最优化问题，在这类问题中可能有多个可行解，最终得到的是其中一个最优解。

应用实例：在地图上规划最短路线。

地图.jpg

比如要想找到从北京到广州的最短路线，我们可以在图上横切一刀，这一刀要保证将任何从北京到广州的路一截二，如上图。那么从广州到北京的最短路径必须经过这一条线上的某个城市（图中蓝色的菱形）。我们可以先找到从北京出发到这条线上所有城市的最短路径，最后得到的全程最短路线一定包括这些局部最短路线中的一条，这样，我们就可以将一个“寻找全程最短路线”的问题，分解成一个个小的寻找局部最短路线的问题。只要我们将这条横切线从北京向广州推移，直到广州为止，我们的全程最短路线就找到了。这便是动态规划的原理。采用动态规划可以大大降低最短路径的计算复杂度。在我们上面的例子中，每加入一条横截线，线上平均有十个城市，从广州到北京最多经过十五个城市，那么采用动态规划的计算量是 10×10×15，而采用穷举路径的笨办法是 10 的 15 次方，前后差了万亿倍。

一句话总结：分解问题求子问题的最优解，然后再合并子问题的解。

回溯算法

回溯算法实际上一个类似枚举的深度优先搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径，直到得到问题的解或是遍历完所有的路径为止。

应用实例：一个典型的应用是走迷宫问题，当我们走一个迷宫时，如果无路可走了，那么我们就可以退一步，再在其他的路上尝试一步，如果还是无路可走，那么就再退一步，尝试新的路，直到走到终点或者退回到原点。

一句话总结：回溯算法采用深度优先策略，从一条路往前走，能进则进，不能进则退回来，换一条路再试。

分支限界算法

回溯算法是深度优先，那么分支限界法就是广度优先的一个经典的例子。所谓广度，就是一层一层的，向下遍历，层层堵截。回溯法一般来说是遍历整个解空间，获取问题的所有解，而分支限界法则是获取一个解（一般来说要获取最优解）。

所下图所示：

广度优先.gif

一句话总结：分支限界采用广度优先策略，一层一层向下遍历。