《算法基础：打开算法之门》一3.3 插入排序

本节书摘来自华章出版社《算法基础：打开算法之门》一书中的第3章，第3.3节，作者 ［美］托马斯 H 科尔曼（Thomas H Cormen），更多章节内容可以访问云栖社区“华章计算机”公众号查看

3.3 插入排序

尽管插入排序和选择排序有些相似，但它们还是有点不同。在选择排序中，当我们决定要把哪本书放在第i个位置上时，35当下前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所写的书时所空出的位置。

为了将这一观点转化为插入排序中对一个数组的排序，子数组A［1i-1］是初始时位于数组的前i-1个位置的元素，但是此时它们被重新排序了。为了判定原来在A［i］中存放的元素现在的位置，36插入排序依次与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］，但此时是已经排好序的。下图表明当i等于4时，上述例子第1B步中的内部循环是如何工作的。我们假定子数组A［13］中包含初始在前3个位置的数组元素，37但现在它们是排好序的。为了确定原来在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，因此内层循环的迭代次数组成了一个等差数列：

这正如我们在选择排序中看到的那样，也是Θ（n2）。由于每个内层循环迭代会花费常量时间，因此最坏情况下插入排序的运行时间是Θ（n2）。因此，最坏情况下，选择排序和插入排序有近似相等的运行时间。有必要完全弄清楚插入排序的平均运行时间吗？这取决于一个“平均的”输入看起来是怎样的。如果输入数组中的元素的顺序是随机的，那么对于每个元素，它比约有一半在它之前的元素要大，比约有一半在它之前的元素要小，因此每次执行内层循环时，它会近似执行(i-1)/2次迭代。相对于最坏运行时间而言，这会使运行时间减半。但1/2仅仅是一个常数因子，因此，近似情况下，它和最坏情况下的运行时间没有区别，依然是Θ（n2）。当数组开始是“基本有序”时，插入排序是一个绝佳的选择。假定每个数组元素开始时所处的位置均处于最终排好序的终止位置的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）。比较插入排序和选择排序的近似运行时间，我们会看到在最坏情况下，它们是一样的。当数组是基本有序时，插入排序更好些。39然而，选择排序较插入排序有以下优点：在任何条件下选择排序都只会移动元素Θ（n）次，而插入排序的元素移动次数可能会达到Θ（n2）次，这是因为INSERTIONSORT每执行一次第1Bi步就会移动一次元素。正如我们在选择排序中所指出的那样，如果移动一个元素相当耗时并且你无法确知插入排序的输入是否接近最好情况，那么最好运行选择排序而不是插入排序。