2.1　插入排序

我们的第一个算法（插入排序）求解第1章中引入的排序问题：

输入：n个数的一个序列〈a1,a2,…,an〉。

输出：输入序列的一个排列〈a′1,a′2,…,a′n〉，满足a′1≤a′2≤…≤a′n。

我们希望排序的数也称为关键词。虽然概念上我们在排序一个序列，但是输入是以n个元素的数组的形式出现的。

本书中，我们通常将算法描述为用一种伪代码书写的程序，该伪代码在许多方面类似于C、C++、Java、Python或Pascal。如果你学过这些语言中的任何一种，
16那么在阅读我们的算法时应该没有困难。伪代码与真码的区别在于，在伪代码中，我们使用最清晰、最简洁的表示方法来说明给定的算法。有时最清晰的表示方法是英语，所以如果你遇到一个英文短语或句子嵌入在一段真码中就不要吃惊。伪代码与真码的另一个区别是伪代码通常不关心软件工程的问题。为了更简洁地表达算法的本质，常常忽略数据抽象、模块性和错误处理的问题。

我们首先介绍插入排序，对于少量元素的排序，它是一个有效的算法。插入排序的工作方式像许多人排序一手扑克牌。开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置

。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较，如图2-1所示。拿在左手上的牌总是排序好的，原来这些牌是桌子上牌堆中顶部的牌。

对于插入排序，我们将其伪代码过程命名为INSERTION-SORT，其中的参数是一个数组A［1..n］，包含长度为n的要排序的一个序列。（在代码中，A中元素的数目n用A.length来表示。）该算法原址排序输入的数：算法在数组A中重排这些数，在任何时候，最多只有其中的常数个数字存储在数组外面。在过程INSERTION-SORT结束时，输入数组A包含排序好的输
17出序列。

INSERTION-SORT(A)

1　for j = 2 to A.length

2　　key = A［j］

3　　// Insert A［j］ into the sorted sequence A［1..j - 1］.

4　　i = j - 1

5　　while i > 0 and A［i］ > key

6　　　　A［i+1］ = A［i］

7　　　　i = i - 1

8　　A［i + 1］ = key

循环不变式与插入排序的正确性

图2-2表明对A=〈5,2,4,6,1,3〉该算法如何工作。下标j指出正被插入到手中的“当前牌”。在for循环（循环变量为j）的每次迭代的开始，包含元素A［1..j-1］的子数组构成了当前排序好的左手中的牌，剩余的子数组A［j+1..n］对应于仍在桌子上的牌堆。事实上，元素A［1..j-1］就是原来在位置1到j-1的元素，但现在已按序排列。我们把A［1..j-1］的这些性质形式地表示为一个循环不变式：

在第1～8行的for循环的每次迭代开始时，子数组A［1..j-1］由原来在A［1..j-1］中的元素组成，但已按序排列。

图2-2　在数组A=〈5,2,4,6,1,3〉上INSERTION-SORT的操作。数组下标出现在长方形的上方，数组位置中存储的值出现在长方形中。（a)～（e)第1～8行for循环的迭代。每次迭代中，黑色的长方形保存取自A［j］的关键字，在第5行的测试中将它与其左边的加阴影的长方形中的值进行比较。加阴影的箭头指出数组值在第6行向右移动一个位置，黑色的箭头指出在第8行关键字被移到的地方。（f)最终排序好的数组

循环不变式主要用来帮助我们理解算法的正确性。关于循环不变式，我们必须证明三条性质：
18

初始化：循环的第一次迭代之前，它为真。

保持：如果循环的某次迭代之前它为真，那么下次迭代之前它仍为真。

终止：在循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法是正确的。

当前两条性质成立时，在循环的每次迭代之前循环不变式为真。（当然，为了证明循环不变式在每次迭代之前保持为真，我们完全可以使用不同于循环不变式本身的其他已证实的事实。）注意，这类似于数学归纳法，其中为了证明某条性质成立，需要证明一个基本情况和一个归纳步。这里，证明第一次迭代之前不变式成立对应于基本情况，证明从一次迭代到下一次迭代不变式成立对应于归纳步。

第三条性质也许是最重要的，因为我们将使用循环不变式来证明正确性。通常，我们和导致循环终止的条件一起使用循环不变式。终止性不同于我们通常使用数学归纳法的做法，在归纳法中，归纳步是无限地使用的，这里当循环终止时，停止“归纳”。

让我们看看对于插入排序，如何证明这些性质成立。

初始化：首先证明在第一次循环迭代之前（当j=2时），循环不变式成立。所以子数组A［1..j-1］仅由单个元素A［1］组成，实际上就是A［1］中原来的元素。而且该子数组是排序好的（当然很平凡）。这表明第一次循环迭代之前循环不变式成立。

保持：其次处理第二条性质：证明每次迭代保持循环不变式。非形式化地，for循环体的第4～7行将A［j-1］、A［j-2］、A［j-3］等向右移动一个位置，直到找到A［j］的适当位置，第8行将A［j］的值插入该位置。这时子数组A［1..j］由原来在A［1..j］中的元素组成，但已按序排列。那么对for循环的下一次迭代增加j将保持循环不变式。

　　　当循环是for循环时，在第一次迭代开始之前，我们将检查循环不变式的时刻是在对循环计数变量的初始赋值后、在循环头的第一次测试之前。对INSERTION-SORT，这个时刻就是把2赋给变量j之后但在第一次测试j≤A.length是否成立之前。

　　　在if-else语句中，我们缩进else到其匹配的if相同的层次。虽然省略了关键词then，但是我们偶尔把紧跟if的测试为真时执行的部分称为一个then子句。对于多路测试，在第一个测试之后，使用elseif来测试。

　　　大多数块结构化语言虽然其准确句法也许不同，但却具有等价的结构。Python缺乏repeat-until循环并且其for循环操作与本书中的for循环有些不同。

第二条性质的一种更形式化的处理要求我们对第5～7行的while循环给出并证明一个循环不变式。然而，这里我们不愿陷入形式主义的困境，
19而是依赖以上非形式化的分析来证明第二条性质对外层循环成立。

终止：最后研究在循环终止时发生了什么。导致for循环终止的条件是j>A.length=n。因为每次循环迭代j增加1，那么必有j=n+1。在循环不变式的表述中将j用n+1代替，我们有：子数组A［1..n］由原来在A［1..n］中的元素组成，但已按序排列。注意到，子数组A［1..n］就是整个数组，我们推断出整个数组已排序。因此算法正确。

在本章后面以及其他章中，我们将采用这种循环不变式的方法来证明算法的正确性。

伪代码中的一些约定

我们在伪代码中采用以下约定：

缩进表示块结构。例如，第1行开始的for循环体由第2～8行组成，第5行开始的while循环体包含第6～7行但不包含第8行。我们的缩进风格也适用于if-else语句。采用缩进来代替常规的块结构标志，如begin和end语句，可以大大提高代码的清晰性。

while、for与repeat-until等循环结构以及if-else等条件结构与C、C++、Java、Python和Pascal中的那些结构具有类似的解释。不像某些出现于C++、Java和Pascal中的情况，本书中在退出循环后，循环计数器保持其值。因此，紧接在一个for循环后，循环计数器的值就是第一个超出for循环界限的那个值。在证明插入排序的正确性时，我们使用了该性质。第1行的for循环头为for j=2 to A.length，所以，当该循环终止时，j=A.length+1（或者等价地，j=n+1，因为n=A.length）。
20当一个for循环每次迭代增加其循环计数器时，我们使用关键词to。当一个for循环每次迭代减少其循环计数器时，我们使用关键词downto。当循环计数器以大于1的一个量改变时，该改变量跟在可选关键词by之后。

符号“//”表示该行后面部分是个注释。

形如i=j=e的多重赋值将表达式e的值赋给变量i和j；它应被处理成等价于赋值j=e后跟着赋值i=j。

变量（如i、j和key）是局部于给定过程的。若无显式说明，我们不使用全局变量。

数组元素通过“数组名［下标］”这样的形式来访问。例如，A［i］表示数组A的第i个元素。记号“..”用于表示数组中值的一个范围，这样，A［1..j］表示A的一个子数组，它包含j个元素A［1］，A［2］，…，A［j］。

复合数据通常被组织成对象，对象又由属性组成。我们使用许多面向对象编程语言中创建的句法来访问特定的属性：对象名后跟一个点再跟属性名。例如，数组可以看成是一个对象，它具有属性length，表示数组包含多少元素，如A.length就表示数组A中的元素数目。

我们把表示一个数组或对象的变量看做指向表示数组或对象的数据的一个指针。对于某个对象x的所有属性f，赋值y=x导致y.f等于x.f。进一步，若现在置x.f=3，则赋值后不但x.f等于3，而且y.f也等于3。换句话说，在赋值y=x后，x和y指向相同的对象。

我们的属性记号可以“串联”。例如，假设属性f本身是指向某种类型的具有属性g的对象的一个指针。那么记号x.f.g被隐含地加括号成(x.f).g。换句话说，如果已经赋值y=x.f，那么x.f.g与y.g相同。

有时，一个指针根本不指向任何对象。这时，我们赋给它特殊值NIL。

我们按值把参数传递给过程：被调用过程接收其参数自身的副本。如果它对某个参数赋值，调用过程看不到这种改变。当对象被传递时，指向表示对象数据的指针被复制，而对象的属性却未被复制。例如，如果x是某个被调用过程的参数，在被调用过程中的赋值x=y对调用过程是不可见的。
21然而，赋值x.f=3却是可见的。类似地，数组通过指针来传递，结果指向数组的一个指针被传递，而不是整个数组，单个数组元素的改变对调用过程是可见的。

一个return语句立即将控制返回到调用过程的调用点。大多数return语句也将一个值传递回调用者。我们的伪代码与许多编程语言不同，因为我们允许在单一的return语句中返回多个值。

布尔运算符“and”和“or”都是短路的。也就是说，当求值表达式“x and y”时，首先求值x。如果x求值为FALSE，那么整个表达式不可能求值为TRUE，所以不再求值y。另外，如果x求值为TRUE，那么就必须求值y以确定整个表达式的值。类似地，对表达式“x or y”，仅当x求值为FALSE时，才求值表达式y。短路的运算符使我们能书写像“x≠NIL and x.f=y”这样的布尔表达式，而不必担心当x为NIL时我们试图求值x.f将会发生什么情况。

关键词error表示因为已被调用的过程情况不对而出现了一个错误。调用过程负责处理该错误，所以我们不用说明将采取什么行动。

练习

2.1-1　以图2-2为模型，说明INSERTION-SORT在数组A=〈31,41,59,26,41,58〉上的执行过程。

2.1-2　重写过程INSERTION-SORT，使之按非升序（而不是非降序）排序。

2.1-3　考虑以下查找问题：

输入：n个数的一个序列A=〈a1，a2，…，an〉和一个值v。

输出：下标i使得v=A［i］或者当v不在A中出现时，v为特殊值NIL。

写出线性查找的伪代码，它扫描整个序列来查找v。使用一个循环不变式来证明你的算法是正确的。确保你的循环不变式满足三条必要的性质。

2.1-4　考虑把两个n位二进制整数加起来的问题，这两个整数分别存储在两个n元数组A和B中。这两个整数的和应按二进制形式存储在一个（n+1）元数组C中。
22请给出该问题的形式化描述，并写出伪代码。