插入排序
# 目标：将数组从低到高（或从高到低）排序。
您将获得一系列数字，需要按正确的顺序排列。插入排序算法的工作原理如下：
把数字放在一堆。这堆是未分类的。
从堆中挑选一个数字。你选择哪一个并不重要，但最容易从桩顶挑选。
将此数字插入新数组。
从未分类堆中选择下一个数字，并将其插入到新数组中。它要么在您选择的第一个数字之前或之后，所以现在这两个数字被排序。
再次，从堆中选择下一个数字，并将其插入到正确排序位置的数组中。
继续这样做，直到堆上没有更多的数字。最终得到一个空堆和一个排序的数组。
这就是为什么这被称为“插入”排序，因为你从堆中取一个数字并将其插入数组中的正确排序位置。
一个例子
让我们说要排序的数字是[ 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。数组的开头再次排序。
这是对插入排序算法的内部循环的描述，您将在下一节中看到。它通过交换数字将数字从堆的顶部插入到已排序的部分。
