手把手教你5大基础实用算法，赶紧mark下来吧！

人类社会文明之所以能快速进步，是因为我们懂得将知识一代一代传授下去。在共享经济时代，大圣众包威客平台（www.dashengzb.cn）手把手教你5大基础实用算法并讲解，赶紧mark下来吧！

归并排序算法

【概念解析】：

归并排序（Mergesort，也译作“合并排序”），是建立在归并操作上的一种有效的排序算法。

【算法优势】：

作为采用分治法（DivideandConquer）的一个应用，归并排序非常典型。

【算法步骤】：

1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

2.设定两个指针，最初位置分别为两个已经排序序列的起始位置；

3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

4.重复步骤3直到某一指针达到序列尾；

5.将另一序列剩下的所有元素直接复制到合并序列尾。

2.BFPRT（线性查找算法）

【概念解析】：

BFPRT算法解决的问题十分经典，即从某n个元素的序列中选出第k大（第k小）的元素。它的思想与快速排序思想相似，当然，为使得算法在最坏情况下，依然能达到o（n）的时间复杂度，五位算法作者做了精妙的处理。

【算法优势】：

基于巧妙的分析，BFPRT可以保证在最坏情况下仍为线性时间复杂度。

【算法步骤】：

1.将n个元素每5个一组，分成n/5（上界）组；

2.取出每一组的中位数，以任意排序方法排序，比如插入排序；

3.递归地调用selection算法，查找上一步中所有中位数的中位数，设为x，偶数个中位数的情况下设定为选取中间小的一个；

4.用x来分割数组，设小于等于x的个数为k，大于x的个数即为n-k；

5.若i=k，返回x；若ik，在大于x的元素中递归查找第i-k小的元素。终止条件：n=1时，返回的即是i小元素。

3.快速排序算法

【概念解析】：

快速排序使用分治法（Divideandconquer）策略来把一个串行（list）分为两个子串行（sub-lists）。在平均状况下，排序n个项目要Ο（nlogn）次比较。在最坏状况下则需要Ο（n2）次比较，但这种状况并不常见。它是由东尼·霍尔所发展的一种排序算法。

【算法优势】：

因为快速排序的内部循环（innerloop）可以在大部分的架构上很有效率地被实现出来，所以，通常快速排序明显比其他Ο（nlogn）算法更快。

【算法步骤】：

1.从数列中挑出一个元素，称为“基准”（pivot）；

2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

3.递归（recursive）地把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

4.动态规划算法

【概念解析】：

动态规划（Dynamicprogramming）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

理论上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。所以说，动态规划背后的基本思想非常简单。

【算法优势】：

动态规划常常适用于有重叠子问题和最优子结构性质的问题，这种方法所耗时间往往远少于朴素解法。动态规划算法在重复子问题的数目关于输入的规模呈指数增长时，特别有用。

【算法步骤】：

1.最优子结构性质：如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。

2.子问题重叠性质：子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，便能获得较高的效率。

5.BFS（广度优先搜索算法）

【概念解析】：

广度优先搜索算法（Breadth-First-Search），是一种图形搜索算法。简单地说，BFS是从根节点开始，沿着树（图）的宽度遍历树（图）的节点。如果所有节点均被访问，则算法中止。一般用队列数据结构来辅助实现BFS算法。

【算法优势】：

BFS属于盲目搜索，即这一过程一直进行到已发现从源节点可达的所有节点为止。

【算法步骤】：

1.首先将根节点放入队列中；

2.从队列中取出第一个节点，并检验它是否为目标——如果找到目标，则结束搜寻并回传结果；否则将它所有尚未检验过的直接子节点加入队列中；

3.若队列为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标，那么，结束搜寻并回传“找不到目标”；

4.重复步骤2。

希望以上基础实用的算法讲解，能够对你的学习与工作有实际的教导意义。

（更多大数据与商业智能领域干货、兼职机会请关注大圣众包平台，或添加大圣花花个人微信号（dashenghuaer)，拉你入bigdata&BI交流群330648564。)