插入排序

排序算法不只有一种。在选择排序法运行过程中，数组开头的子数组是已经排好序的，但位于后面的子数组不会被排序。选择排序法会扫描未排序的子数组，以获取要加入到已排序子数组中的下一个元素。

我们换一种方式来考虑排序问题。假设你正在玩纸牌游戏。你手里拿着牌，这些牌都整理好顺序了。发牌人现在递给你一张新卡。你必须把它插到正确的位置使手牌一直保持有序。在选择排序法中，添加到已排序子数组中的每个元素都不会比现有元素小。但在我们的纸牌例子中新发的牌可能比你已经有的一些牌要小，所以你就会把新牌和手中已有的每一张牌进行比较，直到找到放它的地方。您将新牌插入正确的位置，现在您手里全是排好序的牌。然后发牌人又给你另一张牌，你重复同样的步骤。然后是另一张牌，又一张牌，等等，直到发牌人停止给你发牌。

这是 插入排序法 的排序思路。从索引1开始，循环到数组中的每一个位置。每一个新位置都像发牌人发给你的新牌一样，你需要在已经排序的子数组中将它插入正确的位置。下面是一个分步的动画示范：

对于数组来说，假设从索引 0 到索引 $5$‍ 的子数组已排序，我们希望将现在位于索引6中的元素插入到已排序的子数组中，这样从索引0到索引6中的子数组是按规则排序的。下面是我们的开始步骤:

下面是子数组重新排序后的目标：

要将位置6中的元素插入到左侧的子数组中，我们会反复将其与左侧的元素进行比较，从右到左。让我们将位置6中的元素称为key。每次我们发现key比它左边的元素小的时候，我们就将左边的元素向右滑动一个位置，因为我们知道key必须移到到该元素的左侧。要实现这个想法，我们需要做两件事： 我们需要有一个 slide 操作，将元素向右滑动一个位置，然后我们需要将key的值保存在一个单独的位置 (这样它就不会被它左侧紧挨着的元素覆盖)。在我们的示例中，让我们将索引6处的元素拉到一个名为 key的变量中:

现在，我们将 key 值与位置 5的元素进行比较。发现 key (5) 小于位置 5 的元素 (13) ，所以我们要将位置5 的元素向右滑动到位置 6：

请注意，滑动操作只是将该元素复制到右边一个位置。接下来，我们将 key值与位置 4的元素进行比较。我们发现 key (5) 也比位置 4 (10)的数字小，所以，我们继续将该元素向右滑动一个位置：

接下来, 我们将key 值与位置3处的元素进行比较，并将此元素向右滑动一位:

位置2处的元素也是同样的情况:

现在，我们到了位置 1 上的元素，它的值为3。这个元素值小于 key值，所以我们 不 让它滑动。相反，我们将 key 放在该元素右侧紧邻的位置 (也就是位置2)，原来右边的元素刚刚被滑到了再右侧。结果是，从索引 0 至索引 6中的子数组完成排序。如下：

插入排序法重复将一个元素插入到已经排序的子数组元素左侧。最初，我们可以说只包含索引0的子数组是已经排好序的，因为它只包含一个元素。只有单个元素怎么可能是 乱序 呢？它肯定是有序的。下面让我们来尝试一个示例。这是我们的初始数组:

因为仅包含索引0的子数组是我们的初始有序子数组，所以第一个key就位于索引1\ 。(我们用红色显示已排序的子数组，以黄色显示key，以蓝色显示数组中尚未处理的部分。我们将key插入到左侧的已经排序的子数组中:

现在，已排序的子数组是从索引 0 到索引 1的数组，新key位于索引2\ 。我们将其插入到左侧的已排序子数组中:

我们继续这样操作， 依次将每个数组元素视为key，并将其插入左侧的已排序子数组中:

一旦我们在有序数组中插入了最右边的元素，我们就对整个数组完成了排序:

在我们的示例中有几个情况需要我们注意：当要插入的key小于其左侧的所有元素时 (如插入的 key 是 2和 3时)，以及当它大于或等于左侧的所有元素时 (如插入key 是 13时)。 在前一种情况下，key左侧子数组中的每个元素都会向右滑动一个位置， 一旦我们到达了数组的最左端，排序就完成了。在后一种情况下，当我们第一次将key与左侧的元素进行比较时，我们发现key相对于左侧的所有元素已经处于正确的位置；没有元素需要滑动，此时key就会确定放在它开始的位置。

插入排序法的主要步骤是在数组中腾出空位以放置存储在变量 key 中的当前值。正如我们在上面看到的，我们从右到左逐个比较 key 初始位置左侧的元素。对于每个大于 key 的元素，就将其向右滑动一个位置。一旦我们遇到一个小于 key 或等于 key 的元素，我们就会停止移动数组元素并将 key 值复制到该元素右侧的空出位置。(当然，这个位置并没有真正腾空，但它的元素已经被滑向了右边）。下图显示了整个思路：

本内容是 达特茅斯计算机科学 教授 Thomas Cormen 和 Devin Balkcom，与可汗学院的计算课程团队合作完成。内容获得许可 CC-BY-NC-SA。