1.3.3 直接插入排序

接下来介绍最后一种简单排序方式——直接插入排序，直接插入排序就是不断地选择未排序的第一个数字，插入已经排好序的有序列表中。如果是从小到大排序，第一次会将前两个元素通过直接插入的方式排好序，第二次会将前三个元素通过直接插入的方式排好序，以此类推，直到整个数组都排序完成。现在我们还是对数字5，4，3，1，2进行排序，我们通过图例讲解直接插入排序。

（1）我们开始第一次插入，第一次插入的目的是将前两个元素排好序，插入策略就是不断和前面的有序列表进行比较，找到合适的插入位置后，将整个有序列表向后退1，并将数字插入有序列表的正确位置。第一次是4和5比较，因为5比4大，所以需要将4插入5的前面，插入完成后的排序是4，5，3，1，2，这样前两个元素就排好序了，如图1.20所示。

图1.20 第一次插入排序

（2）我们要开始第二次插入，经过第一次插入排序，现在的数字序列是4，5，3，1，2。第二次插入的目的是将前三个元素排好序，插入的策略还是一样，不断地和前面的有序列表进行比较，找到合适的插入位置后，将整个有序列表向后退1，并将数字插入有序列表的正确位置。第一次是3和5比较，因为5比3大，所以还需要向前比较；第二次是3和4比较，因为4比3大，所以需要将3插入4的前面。首先将4和5两个元素整体向后退1，将3插入4的前面，插入后的排序是3，4，5，1，2，这样前三个元素就排好序了，如图1.21所示。

图1.21 第二次插入排序

（3）我们要开始第三次插入，经过第二次插入排序，现在的数字序列是3，4，5，1，2。第三次插入的目的是将前四个元素排好序，插入的策略还是一样，不断地和前面的有序列表进行比较，找到合适的插入位置后，将整个有序列表向后退1，并将数字插入有序列表的正确位置。第一次是1和5比较，因为5比1大，所以还需要向前比较；第二次是4和1比较，因为4比1大，所以还需要向前比较；第三次是3和1比较，因为3比1大，所以需要将1插入3的前面。首先将3，4，5三个元素整体向后退1，将1插入3的前面，插入后的排序是1，3，4，5，2，这样前四个元素就排好序了，如图1.22所示。

（4）我们要开始第四次插入，经过第三次插入排序，现在的数字序列是1，3，4，5，2。第四次插入的目的是将五个元素排好序，插入的策略还是一样，不断地和前面的有序列表进行比较，找到合适的插入位置后，将整个有序列表向后退1，并将数字插入有序列表的正确位置。第一次是2和5比较，因为5比2大，所以还需要向前比较；第二次是4和2比较，因为4比2大，所以还需要向前比较；第三次是3和2比较，因为3比2大，所以还需要向前比较；第四次是1和2比较，因为1比2小，所以需要将2插入3的前面，首先将3，4，5三个元素整体向后退1，将2插入3的前面，插入后的排序是1，2，3，4，5，这样整个数组就排好序了，如图1.23所示。

图1.22 第三次插入排序

图1.23 第四次插入排序

通过上面的图解，相信大家对直接插入排序算法已经有了了解，直接插入排序算法的实质就是将数组没有排序的部分不断地插入已经排好序的有序列表。那么接下来我们就要通过程序来实现直接插入排序，把整个插入过程通过程序体现出来。插入排序算法完整代码如下。

直接插入排序运行结果如图1.24所示。

图1.24 直接插入排序运行结果

可以发现，程序的运行结果和前面的分析结果是一致的。我们已经成功地通过程序将直接插入排序的内部细节进行了展示。直接插入排序属于插入排序中的一种，上面的图解及程序每次将无序部分的元素不断插入前面的有序列表，从而达到排序的目的。