程序员必会的算法(程序员必会的五十种算法是啥)

来源：博客花园链接：

http://kb.cnblogs.com/page/210687/

快速排序是由Tony Hall开发的一种排序算法。平均来说，对N个项目进行排序需要 (nlogn)次比较。在最坏的情况下，需要进行 (N2)比较，但这种情况并不常见。

事实上，快速排序通常比其他 (NLOGN)算法快得多，因为它的内循环可以在大多数架构中有效实现。

快速排序使用Divideandconquer策略将一个列表分成两个子列表。

算法步骤：

1.从序列中挑出一个元素，称之为“pivot”。

2.对序列重新排序，所有小于基准值的元素放在基准前面，所有大于基准值的元素放在基准后面(同一个数可以在两边)。

在这个分区退出后，基准位于系列的中间。这称为分区操作。

3.递归排序小于参考值的元素子系列和大于参考值的元素子系列。

在递归的最底层，序列的大小是零或一，也就是一直排序下去。虽然它一直在递归，但这种算法总是会退出，因为在每次迭代中，它至少会将一个元素放到最后一个位置。

堆排序是指利用堆的数据结构设计的一种排序算法。Heap是一种类似于完全二叉树的结构，同时满足heap的性质：即子节点的键值或索引总是小于(或大于)其父节点。

堆排序的平均时间复杂度为 (nlogn)。

算法步骤：

1.创建一个堆H[0.n-1]

2.交换反应器的头部(最大值)和尾部。

3.将堆的大小减少1，并调用shift_down(0 ),以便将新数组顶部的数据调整到相应的位置。

4.重复步骤2，直到堆的大小为1

Mergesort(台湾省译)是一种基于归并运算的有效排序算法。该算法是DivideandConquer方法的典型应用。

算法步骤：

1.申请一个大小为两个排序序列之和的空间，这个空间用来存放合并后的序列。

2.设置两个指针，指针的初始位置是两个排序序列的起始位置。

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

4.重复步骤3，直到指针到达序列的末尾。

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

二进制搜索算法是一种在有序数组中寻找特定元素的搜索算法。

搜索过程从数组的中间元素开始，如果中间元素正是要搜索的元素，则搜索过程结束。如果某个元素比中间的元素大或小，则在数组中比中间的元素大或小的那一半中进行搜索，并从中间的元素开始比较。

如果数组在某一步是空的，说明找不到。这种搜索算法每次比较都将搜索范围缩小一半。对折搜索每次将搜索区域缩小一半，时间复杂度为 (logn)。

算法5: BFPRT(线性搜索算法)

BFPRT算法解决的问题非常经典，就是从N个元素的某个序列中选择第K个最大(第K个最小)的元素。通过巧妙的分析，BFPRT可以保证在最坏的情况下，时间复杂度仍然是线性的。

该算法的思想类似于快速排序的思想。当然，为了让算法在最坏的情况下仍然达到o(n)的时间复杂度，算法的五位作者做了细微的处理。

算法步骤：

1.将n个元素分成五个一组的n/5(上限)组。

2.取出每组的中间值，使用任意排序方法，比如插入排序。

3.递归调用选择算法，求出上一步所有中值的中值，设为x，如果有偶数个中值，设为中间较小的那个。

4.将数组除以x，设小于等于x的数为k，大于x的数为n-k。

5.如果i==k，返回x；如果ik，递归查找小于x的元素中第I个最小的元素；如果是ik，递归查找大于x的元素中i-k最小的元素。

终止条件：当n=1时，返回I个小元素。

算法6: DFS(深度优先搜索)

深度优先搜索算法是一种搜索算法。

它沿着树的深度遍历树的节点，并尽可能深地搜索树的分支。当节点V的所有边都已被浏览时，搜索将返回到找到节点V的边的起始节点。

这个过程一直持续到找到从源节点可到达的所有节点。如果还有未发现的节点，选择其中一个作为源节点，重复上述过程。重复整个过程，直到所有节点都被访问。DFS属于盲搜索。

深度优先搜索是图论中的经典算法。利用深度优先搜索算法，可以生成目标图对应的拓扑排序表，利用拓扑排序表可以方便地解决许多相关的图论问题，如最大路径问题。使用通用堆数据结构来帮助实现DFS算法。

深度优先遍历图算法步骤：

1.访问顶点v；

2.依次从V的未访问过的相邻点出发，先遍历图形深度；直到访问图中与V条路径相连的顶点；

3.如果此时图中还有一些顶点没有被访问，从其中一个没有被访问过的顶点开始，重复深度优先遍历，直到图中的所有顶点都被访问过。

上述描述可以是抽象的，例如：

DFS访问图中某个起始顶点V后，从V开始，访问任意相邻顶点W1；从w1开始，访问与w1相邻但尚未访问的顶点w2；然后从w2开始，进行类似的访问，…等等，直到到达所有相邻顶点都被访问过的顶点U。

然后，退一步回到之前刚访问过的顶点，看看是否还有其他相邻的顶点没有访问过。

如果是，访问这个顶点，然后从这个顶点，进行与之前类似的访问；如果没有，就退一步搜索。重复上述过程，直到连通图中的所有顶点都被访问过。

算法7: BFS(广度优先搜索)

广度优先搜索算法是一种图形搜索算法。简单地说，BFS是一个从根节点开始，沿着树的宽度遍历树(图)的节点。

如果访问了所有节点，则算法中止。BFS也属于盲目搜索。使用通用队列数据结构来帮助实现BFS算法。

算法步骤：

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

2.从队列中取出第一个节点，并验证它是目标节点。如果找到目标，搜索结束并返回结果。否则，其所有未测试的直接子节点都被添加到队列中。

3.如果队列是空的，说明整张图片已经查了——，也就是图片中没有要搜索的目标。结束搜索，返回“目标未找到”。

4.重复步骤2。

Dijkstra的算法(dykstra)是由荷兰计算机科学家Azhel dykstra提出的。

Dikoscher算法使用广度优先搜索来解决非负加权有向图的单源最短路径问题，算法最终得到一棵最短路径树。这种算法常用于路由算法或作为其他图算法的子模块。

算法的输入包括一个加权有向图G和G中的一个源顶点S，我们用v表示G中所有顶点的集合。

每个图的边都是由两个顶点构成的有序元素对。(u，v)表示从顶点u到v有一条路连接，我们用E来表示G中所有边的集合，边的权重由权函数w:E[0，]定义。因此，w(u，v)是从顶点u到顶点v的非负权重.

边的权重可以被认为是两个顶点之间的距离。任意两点之间的路径的权重是该路径上所有边的权重之和。给定v中有顶点s和t，Dijkstra算法可以找到从s到t的最低权路径(例如最短路径)。

该算法还可以找到从一个顶点S到图中任何其它顶点的最短路径。对于无负权的有向图，Dijkstra算法是目前已知最快的单源最短路径算法。

算法步骤：

1.初始季S={V0}，T={其他顶点}，T中顶点对应的距离值，如果有V0，vi，d(V0，Vi)是V0，Vi弧上的权值；如果没有V0，Vi，d(V0，Vi)是。

2.选择一个与T距离最小且不在S中的顶点W，加上S。

3.修改其余T中顶点的距离值：如果添加W作为中间顶点，并且从V0到Vi的距离值缩短，则修改这个距离值。

重复上述步骤2和3，直到所有顶点都包含在S中，即W=Vi。

动态编程是数学、计算机科学和经济学中使用的一种方法，通过将原始问题分解为相对简单的子问题来解决复杂的问题。

动态规划常用于子问题重叠且子结构性质最优的问题，动态规划方法所花费的时间往往远小于简单求解。

动态规划背后的基本思想非常简单。一般来说，解决一个给定的问题，需要求解它的不同部分(即子问题)，然后将子问题的解组合起来，得到原问题的解。

通常很多子问题都很相似，所以动态规划法尽量每个子问题只解一次，这样就减少了计算量：给定子问题的解一旦被计算出来，就会被记忆存储，下次需要同一个子问题的解时，可以直接在表中查找。当重复子问题的数量随着输入的大小呈指数增长时，这种方法特别有用。

关于动态规划最经典的问题是背包问题。

算法步骤：

1.最佳子结构特性。如果问题的最优解所包含的子问题的解也是最优的，我们就说该问题具有最优子结构性质(即满足最优化原理)。

最优子结构性质为动态规划算法解决问题提供了重要线索。

2.子问题的重叠性质。子问题的重叠性是指当采用递归算法自上而下求解问题时，每次产生的子问题并不总是新问题，有些子问题会重复计算多次。

动态规划算法利用了这个子问题的重叠性，每个子问题只计算一次，然后将其计算结果保存在一个表中。当需要再次计算已经计算好的子问题时，它只需查看表中的结果，从而获得更高的效率。

算法10:朴素贝叶斯分类算法

朴素贝叶斯分类算法是一种基于贝叶斯定理的简单概率分类算法。贝叶斯分类以概率推理为基础，即在各种条件的存在不确定，只知道其发生的概率的情况下，如何完成推理和决策任务。

概率推理对应于确定性推理。朴素贝叶斯分类器基于独立假设，即假设样本的每个特征与其他特征无关。

朴素贝叶斯分类器依赖于精确的自然概率模型，在有监督学习的样本集中可以获得非常好的分类结果。在许多实际应用中，朴素贝叶斯模型的参数估计使用最大似然估计方法，换句话说，朴素贝叶斯模型可以不使用贝叶斯概率或任何贝叶斯模型而工作。

尽管有这些天真的想法和过于简化的假设，朴素贝叶斯分类器仍然可以在许多复杂的真实情况下取得相当好的结果。

(完)