3.3 插入排序

35

尽管插入排序和选择排序有些相似，但它们还是有点不同。在选择排序中，当我们决定要把哪本书放在第 i 个位置上时，当下前 i 个位置的书是 书架中所有书 按照作者姓名排序的前 i 本书。插入排序中，前 i 个位置的书仍然是 初始时刻 在前 i 个位置的书，但现在是按照作者名字顺序对这 i 本书进行了重排操作。

例如，假设放在前4个位置的书已经按照作者名字排好序了，并且按照顺序，它们分别是Charles Dickens、Herman Melville、Jonathan Swift和Leo Tolstoy所写的书。现在第5个位置处的书是Sir Walter Scott写的。通过插入排序，我们将Swift和Tolstoy所写的书分别向右移动一个位置，将它们分别从第3个位置和第4个位置移动到第4个位置和第5个位置，然后我们把由Scott所写的书放置到空出的第3个位置。此时当我们操作由Scott所写的书时，我们并不关心位于它右侧的是哪本书籍（下图中显示的是由Jack London和Gustave Flaubert所写的书），我们随后再处理它们。

为了移动Swift和Tolstoy所写的书，首先比较Tolstoy和Scott这两个作者名字。我们发现Tolstoy排在Scott之后，因此将Tolstoy所写的书向右移动一个位置，从第4个位置移动到第5个位置。然后比较Swift和Scott这两个作者名字。我们发现Swift排在Scott之后，因此将Swift所写的书向右移动一个位置，从第3个位置移动到第4个位置，其中第4个位置就是当我们移动Tolstoy时所空出的位置。下一步比较Herman Melville和Scott这两个作者名字。这时，我们发现Melville并 没有 排在Scott之后。因而不再比较作者名字，因为我们已经发现由Scott所写的书应该排在Melville所写的书的右侧和Swift所写的书的左侧。我们把Scott所写的书放在第3个位置处，也就是当我们移动Swift所写的书时所空出的位置。

36

为了将这一观点转化为插入排序中对一个数组的排序，子数组 A [1.. i -1]是初始时位于数组的前 i -1个位置的元素，但是此时它们被重新排序了。为了判定原来在 A [ i ]中存放的元素现在的位置，插入排序依次与 A [1.. i -1]中的所有元素进行比较，首先与 A [ i -1]比较，之后依次向左移动，使每个比当前 A [ i ]元素大的元素向右移动一个位置。一旦找到了一个不大于 A [ i ]的元素或者已经到达了数组的最左端，那么我们将初始时在 A [ i ]中的元素调换到数组当前的新位置上。

第1B步中的判定条件依赖于 短路的 （short circuiting）“与”运算符：如果表达式左侧部分（即 j >0）为假，那么它就不会再判定表达式右侧部分的真假。如果 j ≤0，程序又试图获取 A [ j ]的值时，就会发生数组索引指向错误。

下面我们使用在3.2节的选择排序例子里的数组来描述插入排序的执行过程：

同样地，最初的数组出现在左上侧，图中每一步显示了经过程序第1步中外部循环的一次迭代后得到的新数组。深蓝色阴影标识的元素是已经排好序的子数组。针对外部循环的循环不变式（我们也不再证明）如下：

在第 1 步循环的每次迭代开始时 ， 子数组 A [1.. i -1] 包含初始元素 A [1.. i -1]， 但此时是已经排好序的 。

37

下图表明当 i 等于4时，上述例子第1B步中的内部循环是如何工作的。我们假定子数组 A [1..3]中包含初始在前3个位置的数组元素，但现在它们是排好序的。为了确定原来在 A [4]中的元素现在应该放置的位置，我们将它保存在一个名为 key 的变量中，然后将 A [1..3]中比 key 值大的元素依次向右移动一个位置：

深蓝色阴影位置表明元素应该移动到的位置。从最后一步可以看出， A [1]的值3并不比 key 的值7大，因此内部循环终止。正如最后一步得出的， key 的值移动到了 A [1]的右侧。当然，由于内部循环的第一次迭代会覆盖 A [ i ]，所以我们必须在第1A步中将初始时在 A [ i ]中的值保存至 key 中。

也有可能内部循环的终止是因为 j >0不成立。这种情况会在 key 小于 A [1.. i -1]的所有元素时发生。当 j 变成0时， A [1.. i -1]的每个元素均会右移1次，因此第1C步中 key 值放入 A [1]中，这正好是我们想要放置的地方。

分析插入排序（INSERTION-SORT）的运行时间，我们发现它比选择排序（SELECTION-SORT）更复杂。SELECTION-SORT程序的内层循环迭代次数仅仅取决于外层循环的索引 i 而并非元素自身的值。然而，对于INSERTION-SORT程序，内层循环的迭代次数取决于外层循环的索引 i 和数组元素值。

当内层循环每次都执行0次迭代时，INSERTION-SORT会出现最好情况。对于每个 i 值，当第一次验证 A [ j ]> key 时就已经是错误的，此时便为最好情况。换句话说，每次执行第1B步时，一定有 A [ i -1]≤ A [ i ]成立。这种情况在什么时候才会发生呢？当且仅当在程序开始时，数组 A 已经是有序的。在这种情况下，外层循环迭代 n -1次，而外层循环的每次迭代均会花费常量时间，因此INSERTION-SORT会花费Θ（ n ）时间。

当内层循环每次都执行最大次数时，会发生最坏情况。现在判定条件 A [ j ]＞ key 每次都为真，且循环一定终止于条件 j ＞0被判定为假时。每个元素A[ i ]必须扫描比较到数组的最左侧。这种情况在什么时候才会发生呢？当数组 A 整体为逆序时，即 非递增顺序 。在这种情况下，外层循环每迭代一次，内层循环会迭代 i -1次。由于外层循环随着 i 值变化会从2增长到 n ，因此内层循环的迭代次数组成了一个等差数列：

1 + 2 + 3 + …（ n -2） + （ n -1）

38

这正如我们在选择排序中看到的那样，也是Θ（ n ² ）。由于每个内层循环迭代会花费常量时间，因此最坏情况下插入排序的运行时间是Θ（ n ² ）。因此，最坏情况下，选择排序和插入排序有近似相等的运行时间。

有必要完全弄清楚插入排序的平均运行时间吗？这取决于一个“平均的”输入看起来是怎样的。如果输入数组中的元素的顺序是随机的，那么对于每个元素，它比约有一半在它之前的元素要大，比约有一半在它之前的元素要小，因此每次执行内层循环时，它会近似执行（ i -1）/2次迭代。相对于最坏运行时间而言，这会使运行时间减半。但1/2仅仅是一个常数因子，因此，近似情况下，它和最坏情况下的运行时间没有区别，依然是Θ（ n ² ）。

当数组开始是“基本有序”时，插入排序是一个绝佳的选择。假定每个数组元素开始时所处的位置均处于最终排好序的终止位置的 k 步之内。那么一个给定元素移动的次数，经过内层循环的迭代，至多移动 k 步。因此，包括所有内层循环迭代，所有元素移动次数至多为 kn 次，这反过来告诉我们内层循环迭代的总次数最多是 kn 次（由于每个内层循环中每个元素恰好移动一个位置）。如果 k 是一个常数，那么插入排序总共的运行时间将是Θ（ n ），因为Θ符号能把常量因子 k 考虑在内。事实上，我们甚至能够容忍一些元素在数组中移动很长的距离，只要这样的元素不太多。尤其是，如果 l 个元素能在数组中任意移动（因此每个这样的元素移动次数能达到 n -1次），而剩下的 n-l 个元素最多移动 k 个位置，那么总共的移动次数至多是 l （ n -1）+（ n-l ） k =（ k + l ） n -（ k +1） l ，如果 k 和 l 都是常量，它也是Θ（ n ）。

比较插入排序和选择排序的近似运行时间，我们会看到在最坏情况下，它们是一样的。当数组是基本有序时，插入排序更好些。然而，选择排序较插入排序有以下优点：在任何条件下选择排序都只会移动元素Θ（ n ）次，而插入排序的元素移动次数可能会达到Θ（ n ² ）次，这是因为INSERTION-SORT每执行一次第1B 步就会移动一次元素。正如我们在选择排序中所指出的那样，如果移动一个元素相当耗时并且你无法确知插入排序的输入是否接近最好情况，那么最好运行选择排序而不是插入排序。 UOzzZhYpFHpHVBHNHoy2uRiK5FYaVYHHRfcsHKIidTHxNdrrMa+1rxH9PBgZ4Wpk

39