算法 ALGORITHM

|

算法是程序设计的精髓，程序设计的实质就是构造解决问题的算法，将其解释为计算机语言。

在这里您可以了解到：

• 算法定义
• 伪代码的使用
• 算法的复杂性
• 算法设计策略
• 常用算法

这里所有的算法都以一种类似 Pascal 语言的伪代码描述，请参阅 伪代码的使用 。

---|---

|

** 新增内容 **

---|---

关于数论的算法 —— 数论基本知识 （ May 6, 2001 ）
动态规划重新整理 （ January 15, 2001 ）
图的深度优先遍历 （ January 21, 2001 ）

|

图的广度优先遍历 （ January 21, 2001 ）
图的拓扑排序 （ January 21, 2001 ）

---|---

算法 Algorithm

算法 是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。

一个算法应该具有以下五个重要的特征：

1. ** 有穷性： ** 一个算法必须保证执行有限步之后结束；

2. ** 确切性： ** 算法的每一步骤必须有确切的定义；

3. ** 输入： ** 一个算法有 0 个或多个输入，以刻画运算对象的初始情况，所谓 0 个输入是指算法本身定除了初始条件；

4. ** 输出： ** 一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；

5. ** 可行性： ** 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。

|

** Did you know **

---|---

Algorithm 一词的由来

Algorithm( 算法 ) 一词本身就十分有趣。初看起来，这个词好像是某人打算要写 “Logarithm”( 对数 ) 一词但却把头四个字母写的前后颠倒了。这个词一直到 1957 年之前在 Webster's New World Dictionary( 《韦氏新世界词典》 ) 中还未出现，我们只能找到带有它的古代涵义的较老形式的 “Algorism”( 算术 ) ，指的是用阿拉伯数字进行算术运算的过程。在中世纪时，珠算家用算盘进行计算，而算术家用算术进行计算。中世纪之后，对这个词的起源已经拿不准了，早期的语言学家试图推断它的来历，认为它是从把 algiros( 费力的 )+arithmos( 数字 ) 组合起来派生而成的，但另一些人则不同意这种说法，认为这个词是从 “ 喀斯迪尔国王 Algor” 派生而来的。最后，数学史学家发现了 algorism( 算术 ) 一词的真实起源：它来源于著名的 Persian Textbook( 《波斯教科书》 ) 的作者的名字 Abu Ja'far Mohammed ibn Mûsâ al-Khowârizm （约公元前 825 年） —— 从字面上看，这个名字的意思是 “Ja'far 的父亲， Mohammed 和 Mûsâ 的儿子， Khowârizm 的本地人 ” 。 Khowârizm 是前苏联 XИBA( 基发 ) 的小城镇 。 Al-Khowârizm 写了著名的书 Kitab al jabr w'al-muqabala ( 《复原和化简的规则》 ) ；另一个词， “algebra”( 代数 ) ，是从他的书的标题引出来的，尽管这本书实际上根本不是讲代数的。

逐渐地， “algorism” 的形式和意义就变得面目全非了。如牛津英语字典所说明的，这个词是由于同 arithmetic( 算术 ) 相混淆而形成的错拼词。由 algorism 又变成 algorithm 。一本早期的德文数学词典 Vollstandiges Mathematisches Lexicon ( 《数学大全辞典》 ) ，给出了 Algorithmus ( 算法 ) 一词的如下定义： “ 在这个名称之下，组合了四种类型的算术计算的概念，即加法、乘法、减法、除法 ” 。拉顶短语 _ algorithmus infinitesimalis _ ( 无限小方法 ) ，在当时就用来表示 Leibnitz ( 莱布尼兹 ) 所发明的以无限小量进行计算的微积分方法。

1950 年左右， algorithm 一词经常地同欧几里德算法 (Euclid's algorithm) 联系在一起。这个算法就是在欧几里德的 《几何原本》 ( Euclid's Elements , 第 VII 卷，命题 i 和 ii ) 中所阐述的求两个数的最大公约数的过程 ( 即辗转相除法 ) 。

左上方的图片是 Abu Ja'far Mohammed ibn Mûsâ al-Khowârizm 的肖像，点击该图片可以看见关于他的更详细的资料。

排序

Sorting

排序问题 的输入是一个 线性表 ，该线性表的元素属于一个偏序集；要求对该线性表的元素做某种重排，使得线性表中除表尾外的每个元素都小于等于（或大于等于）它的后继。

设 R 为非空集合 A 上的二元关系，如果 R 满足 自反性 ( 对于每一个 x ∈ A ， (x,x) ∈ R ) ， 反对称性 ((x,y) ∈ R ∧ (y,x) ∈ R→x=y ) 和 传递性 ((x,y) ∈ R ∧ (y,x) ∈ R→(x,z) ∈ R) ，则称 R 为 A 上的 偏序关系 ，记作 ≤ 。如果 (x,y) ∈ R ，则记作 x≤y ，读作 “x 小于等于 y” 。存在偏序关系的集合 A 称为 偏序集 。

注意，这里的 ≤ 不是指数的大小，而是指在偏序关系中的顺序性。 x≤y 的含义是：按照这个序， x 排在 y 前面。根据不同的偏序定义， ≤ 有不同的解释。例如整除关系是偏序关系 ≤ ， 3≤6 的含义是 3 整除 6 。大于或等于关系也是偏序关系，针对这个关系 5≤4 是指在大于或等于关系中 5 排在 4 的前面，也就是说 5 比 4 大。

在实际应用中，经常遇到的偏序关系是定义在一个记录类型的数据集合上的。在该记录类型中有一个 主键 域 key ， key 域的类型是某一个偏序集，记录的其他域称为卫星数据。比较线性表中的两个元素 L i 和 L j 的大小，实际上是比较 L i .key 和 L j .key 的大小（这种比较当然也是偏序集中的比较）。举例而言，某公司的数据库里记 录了员工的数据，每一项纪录包括姓名，编号，年龄，工资等几个域，如果以编号为 key 域对员工记录排序，则是将员工记录按照编号排序；如果以工资为 key 域对员工记录排序，则是将员工记录按照工资高低排序；如果以姓名为 key 域对员工记录排序，则是以员工姓名的汉语拼音按照字典顺序排序。

关于偏序集的具体概念和应用，请参见离散数学的相关资料。

如果一个排序算法利用输入的线性表在原地重排其中元素，而没有额外的内存开销，这种排序算法叫做 原地置换排序算法 ** (in place sort) ** ； 如果排序后并不改变表中相同的元素原来的相对位置，那么这种排序算法叫做 稳定排序算法 ** (stable sort) ** 。

排序问题一般分为 内排序 ** ( internal sorting ) ** 和 外排序 ** ( external sorting ) ** 两类：

1. 内排序 ：待排序的表中记录个数较少，整个排序过程中所有的记录都可以保留在内存中；

2. 外排序 ：待排序的记录个数足够多，以至于他们必须存储在磁带、磁盘上组成外部文件，排序过程中需要多次访问外存。

** 内排序 **

待排序的表中记录个数较少，整个排序过程中所有的记录都可以保留在内存中，这样的排序叫做内排序。

请参阅：

• 排序问题的计算复杂性

• 比较排序算法

  • 冒泡排序
  • <SPAN lan