1、 中文 3355 字 毕 业 论 文 外 文 文 献 译 文 及 原 文 学 生： 学 号： 院 （系）： 理学院 专 业： 信息与计算科学 指导教师： 2014 年 6 月 20 日 1 排序 1 内部排序 目前已经发明了许多不同的排序算法，我们将在本书讨论其中大约 25 个算法。这样颇使人惊讶的众多方法， 实际上还只是迄今已经想出算法的一小部分；在我们的讨论中，将略取许多现在已经被废弃的方法，或者紧紧的提及他们。为什么会有那么多的排序算法呢？在计算机的程序设计中，常有“为什么会有这样多的 x 方法呢？”的问题，其中 x 就是某个问题的集合。这个问题的答案是：每种方法都有它的优点和缺点，对于
2、某些数据和硬件的配置来说，它就有可能超过其它的方法。可惜，还不知道“最好”的排序方法；目前许多最好的方法，都是针对的、特定的机器，根据特定的目的，对特定对象进行排序所得到的。用 Rudyard Kipling 的话说：“有 69 种进行部落 安置的方法，而且它们每一种都是对的。” 一个好的想法是学习每种排序方法，它能帮助你具体的应用做出明智的选择。幸而，学习这些算法并不是一项艰难的任务，因为他们都以有趣的方式相互关联着。 在本章开始时，已经定义了将在排序研究中使用的基本术语和符号：记录 NRRR ,., 21 （ 1-1） 有待安排你键码NKKK ,., 21的非减次序进行排序，实质上要求找出
3、一个排列),().2()1( Nppp 使得 )()2()1( . . . Nppp KKK （ 1-2） 在本节中，我们讨论内部排序，此时，有待排序的记录个数足够小，以致整过过程都能在一台计算机的高速存储器中实现。 在某些情况 下，会要求在存储器中对这些记录物理地重新排列，使得它们的键码按次序排列。但在另外的情况下，则可能只要指明这个排序的某个辅助表就能够了。如果每个记录或键码要占用相当多的计算机存储器，则构造一个新的指向记录的链接地址表，并处理这些链表地址，而不是到处移动庞大的记录，通常更好些。这种方式称为地址表排序。如果键码很短，但是记录的附属信息很长，则为了获得更高的速度，这个键码即可
4、用作链接地址，这就是所谓的键码排序。另外一种排序方案利用了包括在每个记录中的一个辅助链接字段；链接的方式是使这些记录最终被链接在一起形成一个直 接的线性表，每个链接指向下一个记录，这就是所谓的表排序。 在用地址表方法或表方法进行排序之后，诸记录可像所希望的那样，重新排成递增的顺序。只要求足够容纳所有记录的新区域。后一方法通常比头一个方法快两倍，但是几乎要两倍的存储空间。在许多应用中，全然不需要移动记录，因为对于随后的寻址操作而言，使用链接字段通常已经足够了。 我们将通过 4 个方面来说明将要深入讨论的所有排序方法，即 a）算法的一个英语语言描述； b）一个框图 c）一个 MIX 程序； d）一
5、个排序方 法的实例，它应用与某个 16 个数的集合。 为了方便起见， MIX 程序通常都假定键码是数值，并且能放到一个单子中去；有时，甚至把键码限制为一个字的一部分。次序关系“ ”将是通常的算术次序；记录将只由键码 2 组成，而没有附属的信息。这些假定使得程序更短和更容易理解。读者应当发现，使用地址表排序或表排序，将通过 MIX 程序进行。 1.1 通过计数进行排序 作为研究内部排序的一个简单示例，考虑在本章开头的“计数”思想。这个简单的方法是这样一个思想为基础的，即在最后排好序的序列中，第 j 个键码恰恰大于（ j-1）个其它键码，换言之。如果知道某个键码确实超过 27 个其它键码，而且没有
6、两个键码相同，则在排序之后对应的记录应当进入位置 28。所以，这个思想是比较每对键码，计算有多少个键码小于每一个特地给的键码。 进行这些比较的明显方式是 对于 Ni 1 对于 Nj 1 但容易看出，这些比较中有一半以上是多余的，因为没有必要把一个键码同它自己进行比较。 没有必要比较 Ka 和 Kb。我们只需要比较 对于 Ni 1 对于 Nj 1 只需比较 Ki 和 Kj。因此导出了下列算法。 算法 c 本算法通过一张辅助表 COUNT1,.,COUNTN,，对于小于一个给定键码的键码个数进行计数，来实现用键码NKK ,.,1对记录NRR,.,1进行排序，算法结束时， COUNTj+1来确定 R
7、i 的最后位置。 C1： 清空 COUNT 把 COUNT1至 COUNTN都置成 0。 C2： 对 i 进行循环 对 i=N， N-1,.2 实施步骤 C3，然后结束次算法。 C3： 对 j 进行循环 对 j=i-1， i-2,.,1 实施步骤 C4. C4： 比较 Ki 和 Kj 如果 KiKj，则 COUNTj加 1，否则 COUNTi+1。 注意：次算法不涉及记录的移动， 它类似地址表排序，因为 COUNT 表确定这些记录最后安排，但是由于 COUNTj高速我们往何处移动 Rj，而不是哪一个记录应当被移动 Ri 的位置，故它与地址表排序略有不同。 通过计数进行排序，还有另外一个方法，从有效的观点看，它十分重要的：它主要应用于许多相同的键码出现，且所有的键码都落入范围 ukjv 的情况，其中（ v-u）很小。这些假定看来十分严格的限制，但是事实上将看到这一思想有不少的应用。列如，如果把这个算法的应用与键码的头几位数，而不是整个键码，则这个文件被部分地排序，而且这项任务将相当简单。 1.2 通过插入进行排序 有一类重要的排序技术，是以 1.2 节开头处提到的“玩桥牌者”的方法为基础的，在考察记录 Rj 之前，假定以前的记录11,., jRR已经排好序，然后已经把 Ri 插入到已经排好的诸多记录的适当位置。这个基本主题可以由若干有趣的变形。 1.2.1 直接插入
