前言

众所周知，算法作为程序的灵魂，是我们设计一个程序的关键。瑞士著名计算机科学家沃斯提出了程序定义的著名公式：程序=数据结构+算法

本篇文章将会就算法的几大基本思路为纲对一些常用的算法进行基本介绍，希望能够让广大初学者朋友们对算法有一个初步的认识，具体的更加深入的内容还需要大家在实际开发中不断学习。

一、算法是什么？

算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。在用计算机解决问题问题的过程中，形成解题思路是推理实施算法，编写程序是操作实施算法。算法并不给出问题的精确解，只是说明怎样才能得到解。

算法的特性：

有穷性：一个算法的操作步骤必须是有限的。
确定性：算法的每一个步骤必须目的明确，不能存在歧义。
有效性：又被称为可行性，算法中的每一个步骤都应该是可以有效执行的。
输入：一个算法中有零个或多个输入。
输出：一个算法中有一个或多个输出，没有输出的算法是无意义的。

?二、算法的常用描述方法

?1.自然语言描述法

自然语言就是人们日常使用的语言，如汉语、英语等。用自然语言表示的优点是通俗易懂，缺点是文字冗长，容易出现“歧义性”。一般情况下不使用自然语言来描述算法

2.流程图

即用一些图框来表示各种类型的操作，用流程线来表示这些操作的执行顺序。这种操作直观形象，容易转化成相应的程序语言。目前所采用的是美国国家标准化协会ANSI规定的流程图符号。

一些常用的流程图符号：

3.N-S图

传统的流程图对流程线的使用没有严格的限制，流程可以随意的转向，给读图带来很大困难，也难以修改，为此，美国学者提出了一种新的流程图形式，去掉了带箭头的流程线，整个算法写在一个矩形框内，整个算法1从上至下执行，又被称为盒图。

顺序结构选择结构

当型循环结构直到型循环结构

4.伪代码

综合使用了多种编程语言中的语法和保留字，又使用了自然语言，是用介于自然语言和计算机语言之间的文字和符号来描述算法的。使用伪代码表示的算法结构清晰，代码简单，可读性好，经常运用在计算机教学之中。

三、算法设计的常用思路

1.随机法

依赖于随机数的统计特性，常用的包括快速排序，数值概率算法，拉斯维加斯算法等。

计算机产生的数都是伪随机数，如rand（）函数产生的随机序列是伪随机序列。解决方法之一是以当前时间作为随机种子，具体我们在这里不过多涉及。

快速排序按如下方式工作：设有一组随机顺序的数，想要对其排序，首先将其分成两个部分，其中一部分大于某个设定好的中间值，另一部分小于等于这个中间值。有了这两组数后再以同样的方式对其进行划分，直到每一组只有一个数为止，此时所有的数字都已完成排序。

在设定中间值时，通过遍历所有数来确定中间值需要花费大量时间，因此我们随机选择一个数作为中间值，由于随机数的正态分布使得划分的结果是相对平衡的。这种方式就是随机法。

2.分治法

分治法包含三个步骤：分解，求解与合并。即将一个大的问题分解成若干个更小，更容易解决的子问题并进行求解，子问题之间相互独立，然后将答案进行合并得到最初大问题的答案。在分治法中，由于子问题与原问题在结构与解法上的相似形，大都采用递归的方式解决问题。常见的如阶乘，汉诺塔，二分查找，归并排序，快速排序等。

在上文快速排序中将一组数分割成两个部分然后继续不断分割的思想也是分治法的一种。

3.动态规划

动态规划同分治法类似，都是将较大的问题分解成子问题然后合并结果。在分治法中，每个子问题是独立的，不同子问题之间的答案不会相互干涉，但是有些问题的子问题之间存在关联，使用分治法需要对一些子问题重复计算多次，这时使用动态规划能够减少很多工作。

4.贪心法

贪心法在求解问题时总是做出当前状态下的最佳选择，但是从整体上看可能并不是最优解，而仅仅是某种意义上的局部最优解。但是从某些方面上来说，运用贪心法是最佳选择。

一个常见的例子是霍夫曼编码，这是一种数据压缩算法，构建一棵霍夫曼树将需压缩的符号和频率作为二叉树的根节点保存，然后选择两棵拥有最小频率值的根节点作为左右子树节点，构造一棵新的二叉树，重复这个过程直到形成一棵完整的霍夫曼树。每次挑选两棵当前最合适的树进行合并的过程就是一种贪心算法。

5.近似法

近似法并不计算最优解，而是计算“足够好”的解。通常利用近似法来解决那些计算成本很高但是十分有价值的“鸡肋”问题。

邮递员问题是一个通常会用近似法来求解的问题。假设一位邮递员有多封不同地址的邮件需要递送，每个地点都要经过且只能经过一次，需要我们找出最短的可能路径。邮递员问题存在可能的最优策略，但计算的代价很大，因此通常从起始点开始，前往距离起始点最近的地点，然后再前往下一个距离最近的地点，直到去到最后一个地点。这是一种比最优解稍逊的策略，但是能够大幅简化计算。