选或陷入技术。

算法直接插入排序重新安排记录，，到适当位置在完成排序之后，它们键码是有序，即有。

对进行循环对于，实施步骤到然后终止本算法。

给赋值置←，←，←比较如果则转向步骤移动，减值置←，然后←。

如果，则返回到步骤。

进入置←。

二叉插入和两路插入在个直接插入排序期间，在处理第个记录时，平均说来要把它键码大约同个此前已排好键码进行比较，因此所实施比较总数大约是，当适当大时，这就已经非常之大了。

在小节，将研究二分查找技术，该技术使我们能够在仅仅次仔细选择比较之后，就指出在那里插入第项。

例如，当插入第个记录时，可以由对和进行比较开始。

如果是小于，则就把它同进行比较，但如果是大于，则就把它同进行比较，等等。

于是仅仅做次比较之后，就可知道应查如得位置。

插入所有项所作比较总数就大学时，这是对于实质性改进。

而小节表示，它早在年就由在计算机排序第个公开讨论中述及。

二叉插入困难时，它只解决问题半。

在已经发现记录应插入到那里之后，仍然需要移动大个此前已排序好记录，以便腾出位置，所以总共运行时间实质上仍同成正比。

当然，个灵巧程序员可以相处各种方式来减少所需要移动数量头个这样技巧，如表所示，是早在年代时就提出，表中排序头项被放置在个输出区域中心，而且通过向右或向左移动腾出空间。

此法比普通二叉插入节省半运行时间，其代价是程序稍微复杂点，使用此法时，还可以不必使用个记录所需要更多空间但对于这个两路插入方法，将不作更详细叙述因为已有更多有趣方法。

方法如果有这样份排序算法，它次只把诸多项目移动个位置，则它平均运行时间最好也是同成比例。

因为在这个排序过程中每个记录都必须平均遍历个位置。

因此，如果直接对插入作实质性改进，就需要种新原理，它是这些记录作长距离跳跃，而不是些短促小步移动。

这样个方法是由于年提出，我们称它为排序，表说明该法般想法首先把这个记录分成组即。

分别对每组记录进行排序。

使我们进到表第二行，这称为第次扫描。

表增量递减排序排序也叫做减少增量排序，因为每遍通过增量来确定，使得我们对相距个单位进行排序。

任何序列，都可以使用此方法，只要最后增量就行。

小结既然我们已经接近着极为冗长章结尾，我们最好整理出已研究过最为重要事实。

用于排序个算法，是个这样过程，它重新安排个文件所有记录，使得其码处于递增次序，这有序排列是有用，因为它把相同记录放到起，允许有效处理按同个键码排好多个文件，这导致了有效检索方法，而且是计算机删除看上去不那么混乱。

如果无论是对那种应用，或无论正在使用什么样计算机，仅仅有两种排序方法，它比所有排序方法都好，那么，事情倒好结局，事实上，每种方法都有各自优点。

因此所有方法都要去记，因为在特地环境中，它们是最好。

参考文献，，，，，，，，，，，，，，，，，，把新键码依次地和，进行比较，直到发现应当插入到和处。

如下列算法所示那样，宜于把比较和移动操作组合在起，互相穿插，由于被安放到适当层次中区，这种排序方式通常称为筛选或陷入技术。

算法直接插入排序重新安排记录，，到适当位置在完成排序之后，它们键码是有序，即有。

对进行循环对于，实施步骤到然后终止本算法。

给赋值置←，←，←比较如果则转向步骤移动，减值置←，然后←。

如果，则返回到步骤。

进入置←。

二叉插入和两路插入在个直接插入排序期间，在处理第个记录时，平均说来要把它键码大约同个此前已排好键码进行比较，因此所实施比较总数大约是中文字毕业论文外文文献译文及原文学生学号院系理学院专业信息与计算科学指导教师年月日排序内部排序目前已经发明了许多不同排序算法，我们将在本书讨论其中大约个算法。

这样颇使人惊讶众多方法，实际上还只是迄今已经想出算法小部分在我们讨论中，将略取许多现在已经被废弃方法，或者紧紧提及他们。

为什么会有那么多排序算法呢在计算机程序设计中，常有为什么会有这样多方法呢问题，其中就是个问题集合。

这个问题答案是每种方法都有它优点和缺点，对于些数据和硬件配置来说，它就有可能超过其它方法。

可惜，还不知道最好排序方法目前许多最好方法，都是针对特定机器，根据特定目，对特定对象进行排序所得到。

用话说有种进行部落安置方法，而且它们每种都是对。

个好想法是学习每种排序方法，它能帮助你具体应用做出明智选择。

幸而，学习这些算法并不是项艰难任务，因为他们都以有趣方式相互关联着。

在本章开始时，已经定义了将在排序研究中使用基本术语和符号记录，有待安排你键码，非减次序进行排序，实质上要求找出个排列，使得在本节中，我们讨论内部排序，此时，有待排序记录个数足够小，以致整过过程都能在台计算机高速存储器中实现。

在些情况下，会要求在存储器中对这些记录物理地重新排列，使得它们键码按次序排列。

但在另外情况下，则可能只要指明这个排序个辅助表就能够了。

如果每个记录或键码要占用相当多计算机存储器，则构造个新指向记录链接地址表，并处理这些链表地址，而不是到处移动庞大记录，通常更好些。

这种方式称为地址表排序。

如果键码很短，但是记录附属信息很长，则为了获得更高速度，这个键码即可用作链接地址，这就是所谓键码排序。

另外种排序方案利用了包括在每个记录中个辅助链接字段链接方式是使这些记录最终被链接在起形成个直接线性表，每个链接指向下个记录，这就是所谓表排序。

在用地址表方法或表方法进行排序之后，诸记录可像所希望那样，重新排成递增顺序。

只要求足够容纳所有记录新区域。

后方法通常比头个方法快两倍，但是几乎要两倍存储空间。

在许多应用中，全然不需要移动记录，因为对于随后寻址操作而言，使用链接字段通常已经足够了。

我们将通过个方面来说明将要深入讨论所有排序方法，即算法个英语语言描述个框图个程序个排序方法实例，它应用与个个数集合。

为了方便起见，程序通常都假定键码是数值，并且能放到个单子中去有时，甚至把键码限制为个字部分。

次序关系将是通常算术次序记录将只由键码组成，而没有附属信息。

这些假定使得程序更短和更容易理解。

读者应当发现，使用地址表排序或表排序，将通过程序进行。

通过计数进行排序作为研究内部排序个简单示例，考虑在本章开头计数思想。

这个简单方法是这样个思想为基础，即在最后排好序序列中，第个键码恰恰大于个其它键码，换言之。

如果知道个键码确实超过个其它键码，而且没有两个键码相同，则在排序之后对应记录应当进入位置。

所以，这个思想是比较每对键码，计算有多少个键码小于每个特地给键码。

进行这些比较明显方式是对于对于但容易看出，这些比较中有半以上是多余，因为没有必要把个键码同它自己进行比较。

没有必要比较和。

我们只需要比较对于对于只需比较和。

因此导出了下列算法。

算法本算法通过张辅助表，，对于小于个给定键码键码个数进行计数，来实现用键码，，对记录，，进行排序，算法结束时，来确定最后位置。

清空把至都置成。

对进行循环对实施步骤，然后结束次算法。

对进行循环对，实施步骤比较和如果，则加，否则。

注意次算法不涉及记录移动，它类似地址表排序，因为表确定这些记录最后安排，但是由于高速我们往何处移动，而不是哪个记录应当被移动位置，故它与地址表排序略有不同。

通过计数进行排序，还有另外个方法，从有效观点看，它十分重要它主要应用于许多相同键码出现，且所有键码都落入范围情况，其中很小。

这些假定看来十分严格限制，但是事实上将看到这思想有不少应用。

列如，如果把这个算法应用与键码头几位数，而不是整个键码，则这个文件被部分地排序，而且这项任务将相当简单。

通过插入进行排序有类重要排序技术，是以节开头处提到玩桥牌者方法为基础，在考察记录之前，假定以前记录，，已经排好序，然后已经把插入到已经排好诸多记录适当位置。

这个基本主题可以由若干有趣变形。

直接插入最简单插入排序也是最显然。

假定，而且已经把记录，，重新排好序，使得把新键码依次地和，进行比较，直到发现应当插入到和处。

如下列算法所示那样，宜于把比较和移动操作组合在起，互相穿插，由于被安放到适当层次中区，这种排序方式通常称为筛选或陷入技术。

算法直接插入排序重新安排记录，，到适当位置在完成排序之后，它们键码是有序，即有。

对进行循环对于，实施步骤到然后终止本算法。

给赋值置←，←，←比较如果则转向步骤移动，减值置←，然后←。

如果，则返回到步骤。

进入置←。

二叉插入和两路插入在个直接插入排序期间，在处理第个记录时，平均说来要把它键码大约同个此前已排好键码进行比较，因此所实施比较总数大约是，当适当大时，这就已经非常之大了。

在小节，将研究二分查找技术，该技术使我们能够在仅仅次仔细选择比较之后，就指出在那里插入第项。

例如，当插入第个记录时，可以由对和进行比较开始。

如果是小于，则就把它同进行比较，但如果是大于，则就把它同进行比较，等等。

于是仅仅做次比较之后，就可知道应查如得位置。

插入所有项所作比较总数就大学时，这是对于实质性改进。

而小节表示，它早在年就由在计算机排序第个公开讨论中述及。

二叉插入困难时，它只解决问题半。

在已经发现记录应插入到那里之后，仍然需要移动大个此前已排序好记录，以便腾出位置，所以总共运行时间实质上仍同成正比。

当然，个灵巧程序员可以相处各种方式来减少所需要移动数量头个这样技巧，如表所示，是早在年代时就提出，表中