插入排序

 # 目标：将数组从低到高（或从高到低）排序。

您将获得一系列数字，需要按正确的顺序排列。插入排序算法的工作原理如下：

把数字放在一堆。这堆是未分类的。

从堆中挑选一个数字。你选择哪一个并不重要，但最容易从桩顶挑选。

将此数字插入新数组。

从未分类堆中选择下一个数字，并将其插入到新数组中。它要么在您选择的第一个数字之前或之后，所以现在这两个数字被排序。

再次，从堆中选择下一个数字，并将其插入到正确排序位置的数组中。

继续这样做，直到堆上没有更多的数字。最终得到一个空堆和一个排序的数组。

这就是为什么这被称为“插入”排序，因为你从堆中取一个数字并将其插入数组中的正确排序位置。

一个例子

让我们说要排序的数字是[ 8, 3, 5, 4, 6 ]。这是我们未分类的堆。

选择第一个数字，8然后将其插入新数组中。该阵列中还没有任何东西，所以这很容易。排序的数组现在[ 8 ]和堆是[ 3, 5, 4, 6 ]。

从堆中选择下一个数字3，然后将其插入到已排序的数组中。它应该在之前8，因此排序的数组现在[ 3, 8 ]和堆减少到[ 5, 4, 6 ]。

从堆中选择下一个数字5，然后将其插入到已排序的数组中。它介于3和之间8。排序的数组是[ 3, 5, 8 ]和堆[ 4, 6 ]。

重复此过程，直到堆积为空。

就地排序

上面的解释使你看起来需要两个数组：一个用于未分类的堆，另一个用于按排序顺序包含数字。

但您可以就地执行插入排序，而无需创建单独的数组。您只需跟踪数组的哪个部分已经排序，哪个部分是未排序的堆。

最初，阵列是[ 8, 3, 5, 4, 6 ]。所述|栏示出了分选部分结束和桩开始：

这表明排序的部分是空的，桩开始于8。

处理完第一个号后，我们有：

分类的部分是[ 8 ]和桩[ 3, 5, 4, 6 ]。该|酒吧已经转向一个姿势要正确。

这是排序期间数组内容的变化方式：

在每个步骤中，|条形向上移动一个位置。如您所见，数组的开头|始终排序。堆缩小一，排序部分增加一，直到堆是空的，没有更多未分类的数字。

如何插入

在每一步中，您从未分类堆中选择最顶部的数字，并将其插入到数组的已排序部分。您必须将该数字放在适当的位置，以便数组的开头保持排序。这是如何运作的？

假设我们已经完成了前几个元素，并且数组看起来像这样：

下一个要排序的数字是4。我们需要将其插入到[ 3, 5, 8 ]某处的已排序部分。

这是一种方法：查看前一个元素，8。

这大于4吗？是的，所以4应该在之前8。我们交换这两个数字得到：

我们还没有完成。新的前一个元素5也大于4。我们还交换了这两个数字：

再看一下前面的元素。是3大于4？不它不是。这意味着我们完成了数字4。数组的开头再次排序。

这是对插入排序算法的内部循环的描述，您将在下一节中看到。它通过交换数字将数字从堆的顶部插入到已排序的部分。