常用的计算机算法

目前已知的计算机算法有很多，如枚举法、迭代法、分治法、递归法、排序算法、树结构算法等。下面就来分别介绍这些算法。

枚举法

枚举法又称穷举法，是一种常见的数学方法，也是日常使用最多的算法之一。枚举法的核心思想是“列举出所有的可能”。具体来说就是逐一列举问题涉及的所有情形，并根据问题中规定的条件检验哪些情形符合条件，是问题的解，哪些情形不符合条件，应予以排除。枚举法的优点是比较直观、易于理解，缺点是速度太慢。

例如，著名的数学趣题“鸡兔同笼”：有若干只鸡和兔子同在一个笼子里，从上面数共有35个头，从下面数共有94只脚，求笼子中鸡和兔子各有几只。这个问题就可以使用枚举法求解，即从0开始逐一增加兔子的数量，并根据兔子的数量算出鸡的数量，然后判断鸡和兔子的总脚数是否等于94，直到找到符合条件的答案为止。算法过程见下表。

迭代法

迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，它利用的是计算机运算速度快、适合做重复性操作的特点，让计算机重复执行一组指令，在每次执行这组指令时，都从变量的原值推出它的一个新值，从而得到最终的结果。

例如，经典的兔子繁殖问题：饲养场引进一只刚出生的新品种兔子，这种兔子从出生的下一个月开始，每月新生一只兔子，新生的兔子也如此繁殖。假如所有的兔子都不死，求第n个月时，该饲养场共有多少只兔子？这个问题的求解就可以使用迭代法。假设第1个月时兔子的只数为y ₁ ，第2个月时兔子的只数为y ₂ ，第3个月时兔子的只数为y ₃ ，……，第n个月时兔子的只数为y _n ，根据题意，这种兔子从出生的下一个月开始，每月新生一只兔子，则有：

在编程时定义两个迭代变量y和x，分别对应y _n 和y _n－1 ，就可以将上面的递推公式转换成如下迭代关系：

y=x*2

x=y

分治法

分治法是把一个复杂的问题分成两个或更多个与原问题相似的子问题，再把子问题分成更小的子问题……直到子问题简单到可以直接求解，最后将各个子问题的解合并，就能得到原问题的答案。简单来说，分治法就是一个“分—治—合”的过程。

例如，要在给定的一组数字中找出最大值，就可以使用分治法将这组数字进行多次“一分为二”，再分别求解，算法过程如下：

递归法

递归法与分治法有些类似，都是对一个复杂的算法问题进行分解，让其规模变得越来越小，最终使子问题容易求解。假如一个函数或过程是由其自定义或调用的，就称为递归。递归只需少量代码就可以描述出解题过程需要的多次重复计算，大大减少了程序的代码量。一般来说，递归至少要有两个要素：一个是可以反复执行的递归过程；另一个是跳出递归的出口。

例如，数学中的阶乘运算就可以看成一个比较典型的递归算法。一般以符号“！”代表阶乘运算，则n！的计算公式如下：

n！＝1×2×3×…×n

并且可以推导出：

n！＝n×（n－1）！

以5！为例逐步分解运算过程。通过仔细观察不难发现，阶乘问题非常适合用递归法来解决，它满足了递归的两大特性：一是反复执行的递归过程；二是跳出递归过程的出口。

排序算法

排序就是将一组数字按照从小到大或从大到小的顺序排列。例如，将一组数字7、5、11、4、9从小到大排序，结果为4、5、7、9、11。

如果数字比较少，人工就能轻松完成排序，但是如果有成百上千个数字，要想高效地完成排序，就要使用排序算法。

因为排序时需要对序列中的数字进行交换，所以在学习排序算法之前，我们先来了解数字交换的算法。我们通常理解的交换是直接交换两个数字的位置。如下图所示，要交换数字10和20，只需要将10移到20所在的位置，将20移到10所在的位置。

在编程中，数字通常存储在变量、数组或列表等“容器”里，无法实现两个数字的直接交换，还需要借助一个额外容器，此容器在初始状态下没有存储任何数字。如下图所示，要在编程中交换数字10和20，需要先将10移到紫色方块代表的额外容器中，再将20移到原来10所在的容器（橙色方块）中，最后将10移到原来20所在的容器（蓝色方块）中。

了解完数字交换的算法，下面开始学习排序算法。排序算法的种类有很多，如冒泡排序、选择排序、插入排序、快速排序、希尔排序、基数排序等。下面简单介绍几种常用的排序算法。

▶冒泡排序

冒泡排序又称交换排序，其思路是从第一个元素开始比较相邻两个元素的大小，若大小顺序有误，就对调后再进行下一个元素的比较，仿佛气泡从水底逐渐上升到水面一样。如此比较一轮之后，就可以确保最后一个元素位于正确的顺序。接着使用相同的方法进行第2轮比较，直到完成所有元素的排序为止。下图所示为使用冒泡排序将一组数字从小到大排序的过程。

▶选择排序

以从小到大排序为例，选择排序法的基本思路是从待排序的一组数字中找到最小的那个元素，将其与第一个元素交换位置，然后在剩下的元素中再次找到最小的元素，与第二个元素交换位置，重复以上操作，最终完成排序，整个过程如下图所示。

用选择排序法进行从小到大排序也可以将最大的元素与最后一个元素交换位置，将第二大的元素与倒数第二个元素交换位置，依此类推。从大到小排序的思路也是类似的。

▶插入排序

插入排序是一种从一组数字的左端开始依次进行排序的算法，在排序过程中，左侧的数字陆续归位，称为已排序区域，而右侧留下的则是还未排序的数字，称为未排序区域。具体思路是把第一个元素作为初始的已排序区域，然后依次从未排序区域中取出第一个元素，插入已排序区域内的合适位置上，直到未排序区域中没有元素可取为止。使用插入排序法完成从小到大排序的过程如下图所示。

▶快速排序

快速排序也称分割排序，其思路是先在一组数字中随机选择一个数字作为基准，通常选取第一个数字作为基准，把比基准小的数字移到左边，比基准大的数字移到右边，然后用相同的方法分别递归左边和右边的部分，直到最后每个部分只有一个数字，排序就完成了。快速排序的过程如下图所示。 gzt2TtFFI31oOcRoK2lK3sOvU3y7BWaIE045Q64xG/Le8ux5B1g309jcwp11Ffxt