1.2.2 算法简介

简单地讲，算法就是解决一个问题的完整的步骤描述，是指完成一个任务准确而完整的步骤描述，也就是说给定初始状态或输入数据，按照算法描述的步骤进行运算，能够得出所要求或期望的终止状态或输出数据。

解决一个问题的方法有高明的，也有糟糕的；同样，同一个问题的算法也存在优劣之分。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。算法的时间复杂度是指执行算法需要消耗的时间资源，其表征了算法执行的效率问题，即解决问题的速度。算法的空间复杂度是指执行算法需要占用的内存空间，其表征了算法执行需要的资源，也就是解决问题付出的代价。很显然，算法的效率越高、代价越小，其性能越优异。

下面以数组排序方法为例，来讨论一下如何得到一个解决问题的算法。要求将一个序列的数值从小到大排序。为了描述方便，将要排序的序列具体化为一个含有10个元素的整数数列，内容为：

        {31, 72, 4, 13, 42, 8, 56, 4, 9, 2}

由于排序时，需要频繁地访问序列元素，但无须增删元素，且不会改变元素数目，因此，使用数组作为数据结构来存储数据是比较合适的。

对序列排序，可以很容易想到一种最直接、最简单的解决方案，具体操作如下所示：

· 第1步，先选出所有数中的最小值，将其放在第1个位置；

· 第2步，选出第2小的数，将其放在第2个位置；

· ……

· 第9步，选出第9小的数，将其放在第9个位置；

· 第10步，剩下的数放在第10个位置。

这种排序算法一般被称为直接排序法。将该思想整理为算法，同时，推广到任意N个元素的序列，可得按如下的步骤操作：

（1）访问序列中的所有元素，找到最小值，将其位置与第一个元素互换；

（2）从剩余的N-1个元素中找到最小值，将其位置与第2个元素交换；

……

（n）从剩余的N-n+1个元素中找到最小值，将其位置与第n个元素交换；

……

（N-1）从剩余的两个元素中找到最小指，将其与第N-1个元素交换；

（N）排序完毕。

在以上算法中，每一步执行需要的操作为：

（1）N-1次比较，1次交换。如果最小值本来就在第一个位置，便无须交换；

（2）N-2次比较，1次交换；

……

（n）N-n次比较，1次交换；

……

（N-1）1次比较，1次交换。

因此，共需要的操作为1+2+……+（N-1），即N(N-1)/2，为N的平方级别。因此，其时间复杂度可以记为O(N2)。同时，该算法只需在交换元素时需要额外的一个空间，因此，其空间复杂度为常数级别，记为O(1)。

从以上案例可以得到，提出一个问题的算法是一个从具体到抽象的过程，一般有以下步骤：

① 分析问题，选择需要的数据结构，得出初步的解决方法。有的问题中，可以先得出算法后再决定需要采用的数据结构；

② 将解决方法合理地拆分，整理成多个步骤；

③ 为重复执行的步骤合理地选择循环变量；

④ 使用易转化为程序实现的自然语言简练地描述算法。

有了解决问题的算法后，编程实现才有章可循。