常见的10种算法(经典)

大家好，欢迎来到IT知识分享网。

算法研究的目的是为了更有效的处理数据，提高数据运算效率。数据的运算是定义在数据的逻辑结构上，但运算的具体实现要在存储结构上进行。

一般有以下几种常用运算：

递归过程一般通过函数或子过程来实现。

递归算法的实质：是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。

递归算法解决问题的特点：

先看看C语言中函数的执行方式，需要了解一些关于C程序在内存中的组织方式：

堆的增长方向为从低地址到高地址向上增长，而栈的增长方向刚好相反（实际情况与CPU的体系结构有关）。

当C程序中调用了一个函数时，栈中会分配一块空间来保存与这个调用相关的信息，每一个调用都被当作是活跃的。

栈上的那块存储空间称为活跃记录或者栈帧。

栈帧由5个区域组成：输入参数、返回值空间、计算表达式时用到的临时存储空间、函数调用时保存的状态信息以及输出参数，参见下图：

栈维护了每个函数调用的信息直到函数返回后才释放，这需要占用相当大的空间，尤其是在程序中使用了许多的递归调用的情况下。

除此之外，因为有大量的信息需要保存和恢复，因此生成和销毁活跃记录需要消耗一定的时间。

我们需要考虑采用迭代的方案。幸运的是我们可以采用一种称为尾递归的特殊递归方式来避免前面提到的这些缺点。

n！=n×(n-1)×(n-2)……2×1

使用递归的方式，可以定义为：

以递归方式实现阶乘函数的实现：

排序是程序设计中常做的操作，初学者往往只知道冒泡排序算法，其实还有很多效率更高的排序算法，比如希尔排序、快速排序、基数排序、归并排序等。

不同的排序算法，适用于不同的场景，本章最后从时间性能，算法稳定性等方面，分析各种排序算法。

排序算法，还分为内部排序算法和外部排序算法，之间的区别是，前者在内存中完成排序，而后者则需要借助外部存储器。

这里介绍的是内部排序算法。

例如，对无序表{49，38，65，97，76，13，27，49}进行升序排序的具体实现过程如图 1 所示：

 如下冒泡排序例子

其实现的基本思想是：通过一次排序将整个无序表分成相互独立的两部分，其中一部分中的数据都比另一部分中包含的数据的值小，然后继续沿用此方法分别对两部分进行同样的操作，

直到每一个小部分不可再分，所得到的整个序列就成为了有序序列。

其基本思想是：首先选取表中间位置的记录，将其关键字与给定关键字 key 进行比较，若相等，则査找成功；

若 key 值比该关键字值大，则要找的元素一定在右子表中，则继续对右子表进行折半查找；

若 key 值比该关键宇值小，则要找的元素一定在左子表中，继续对左子表进行折半査找。

如此递推，直到査找成功或査找失败（或査找范围为 0）。

例如：

要求用户输入数组长度，也就是有序表的数据长度，并输入数组元素和査找的关键字。

程序输出查找成功与否，以及成功时关键字在数组中的位置。

例如，在有序表 11、13、18、 28、39、56、69、89、98、122 中査找关键字为 89 的元素。

现阶段一般有枚举算法、深度优先搜索、广度优先搜索、A*算法、回溯算法、蒙特卡洛树搜索、散列函数等算法。

在大规模实验环境中，通常通过在搜索前，根据条件降低搜索规模；

根据问题的约束条件进行剪枝；利用搜索过程中的中间解，避免重复计算这几种方法进行优化。

这里介绍的是深度优先搜索，感兴趣的可以百度查询更多搜索算法。

内容很多，大家可以百度查询感兴趣的用法：也可以点击 深度优先搜索 查看更多。

深度优先搜索

　　区别在于对扩展结点过程，深度搜索扩展的是E-结点的邻接结点中的一个，并将其作为新的E-结点继续扩展，当前E-结点仍为活结点，待搜索完其子结点后，回溯到该结点扩展它的其它未搜索的邻接结点。

而广度搜索，则是扩展E-结点的所有邻接结点，E-结点就成为一个死结点。

Hash，一般翻译做散列、杂凑，或音译为哈希，是一个典型的利用空间换取时间的算法，把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。

如有一个学生信息表：

学生的学号为：年纪+学院号+班级号+顺序排序号【如：19(年纪)+002(2号学院)+01(一班)+17(17号)—à】类似于一个这样的信息，

当我们需要找到这个学号为【】的学生，在不适用哈希的时候，我们通常是使用一个顺序遍历的方式在数据中进行查询大类，再查询子类得到，

这样的作法很明显不够快 ，需要O(n)左右的时间花费，对于大型的数据规模而言这显然不行，

而哈希的做法是，根据一定的规律(比如说年纪不存在过老和过小的情况，以此将【】进行压缩成一个简短的数据如：

【】)并且将这个数据直接作用于内存的地址，届时我们查询【】只需要进行一次压缩并访问【】这个地址即可，而这个压缩的方法（函数），就可以称之为哈希函数。

一般的对于哈希函数需要考虑如下内容:

在理解了哈希的思维之后，我们要了解什么是哈希表，哈希表顾名思义就是经过哈希函数进行转换后的一张表，

通过访问哈希表，我们可以快速查询哈希表，从而得出所需要得到的数据，构建哈希表的核心就是要考虑哈希函数的冲突处理（即经过数据压缩之后可能存在多数据同一个地址，需要利用算法将冲突的数据分别存储）。

冲突处理的方法有很多，最简单的有+1法，即地址数直接+1，当两个数据都需要存储进【2019】时，可以考虑将其中的一个存进【2020】

此外还有，开放定址法，链式地址发，公共溢出法，再散列法，质数法等等，各方法面对不同的数据特征有不同的效果。

3.哈希的思维

Hash算法是一个广义的算法，也可以认为是一种思想，使用Hash算法可以提高存储空间的利用率，可以提高数据的查询效率，也可以做数字签名来保障数据传递的安全性。

所以Hash算法被广泛地应用在互联网应用中。

比如，利用哈希的思维在O(1)的复杂度情况下任意查询1000以内所有的质数（在创建是否是质数的时候并不是O(1)的复杂度），

注意本样例只是演示思维，面对本需求可以有更好的空间利用方式（本写法比较浪费空间，仅供了解）。

 如下例子：

【电话聊天狂人】

给定大量手机用户通话记录，找出其中通话次数最多的聊天狂人。

输出样例：

3

也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件，直到把所有数据枚举完。

贪心算法的思想如下：

一个有趣的事情是，动态规划中的01背包问题就是一个典型的贪心算法问题。

如下例子：贪心算法货币统计问题

求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。

还有更多例子可以百度，这里就不一一举例了。

这种走不通就回退再走的方法就是回溯算法。

例如，在解决列举集合 {1,2,3} 中所有子集的问题中，就可以使用回溯算法。

从集合的开头元素开始，对每个元素都有两种选择：取还是舍。当确定了一个元素的取舍之后，再进行下一个元素，直到集合最后一个元素。

其中的每个操作都可以看作是一次尝试，每次尝试都可以得出一个结果。将得到的结果综合起来，就是集合的所有子集。

使用回溯法解决问题的过程，实际上是建立一棵“状态树”的过程。

例如，在解决列举集合{1,2,3}所有子集的问题中，对于每个元素，都有两种状态，取还是舍，所以构建的状态树为：

在某些情况下，回溯算法解决问题的过程中创建的状态树并不都是满二叉树，因为在试探的过程中，有时会发现此种情况下，

再往下进行没有意义，所以会放弃这条死路，回溯到上一步。在树中的体现，就是在树的最后一层不是满的，即不是满二叉树，需要自己判断哪些叶子结点代表的是正确的结果。

基本思想原理

与分而治之原理类似，将待求解的问题划分成若干个子问题（阶段）求解，顺序求解各个子问题（阶段），前一子问题（阶段）为后一子问题（阶段）的求解提供有用的信息。

通过各个子问题（阶段）的求解，依次递进，最终得到初始问题的解。一般情况下，能够通过动态规划求解的问题也可通过递归求解。

动态规划求解的问题多数有重叠子问题的特点，为了减少重复计算，对每个子问题只求解一次，将不同子问题（阶段）的解保存在数组中。

与分而治之的区别：

分而治之得到的若干子问题（阶段）一般彼此独立，各个子问题（阶段）之间没有顺序要求。而动态规划中各子问题（阶段）求解有顺序要求，具有重叠子问题（阶段），后一子问题（阶段）求解取决于前一子问题（阶段）的解。

与递归区别：

与递归求解区别不大，都是划分成各个子问题（阶段），后一子问题（阶段）取决于前一子问题（阶段），但递归需要反复求解同一个子问题（阶段），相较于动态规划做了很多重复性工作。

适用解决问题

采用动态规划求解的问题一般具有如下性质：

定义：

Fab(4)=Fab(3)+Fab(2)…..显然。 Fab（3）被计算机不加区别的计算了两次。而且随着数字的增大，计算量是指数增长的。

如果我们使用一个数组，记录下Fab的值。当Fab(n)!=null 时。

直接读取。那么，我们就能把时间复杂度控制在 n 以内。

实现2：

下面是0-1背包问题的解法。

可以对比一下。（一个限重w的背包，有许多件物品。sizes[n]保存他们的重量。values[n]保存它们的价值。求不超重的情况下背包能装的最大价值） 

该模式在此文本中仅出现一次，即在位移 s = 3 处，位移 s = 3 是有效位移。

解决字符串匹配的算法包括：