4.3　插入排序算法

插入排序法是将数列中的元素逐一与已排序好的数据进行比较，进而找到合适的位置并插入。例如，在排好顺序的两个元素中插入第三个元素，就需要将其与其他两个元素做比较，插入合适的位置。也就是说，将第三个元素插入数列后，得到的新数列依然是排好序的。接着将第四个元素插入，以此类推，直至排序完成。直接插入排序法最后的结果也有两种形式，即递增数列和递减数列。

例如，有这样一组数据：58, 29, 86, 69, 10，如图4.16所示。采用插入排序算法使其递增排序，步骤如下。

（1）第一次排序。先用第一个位置的数据占位，放在新数列的第一个位置，如图4.17所示。

（2）第二次排序。取原数列第二个位置上的数29与58进行比较，29小于58，所以将其插入58前面的位置，将58向后移一位，如图4.18所示。

（3）第三次排序。取原数列第三个位置上的数86与29和58进行比较，86大于29和58，因此直接将86插入新数列的第三个位置上，如图4.19所示。

（4）第四次排序。取原数列第四个位置上的数69与29、58和86比较，69大于29和58，小于86，因此直接将69插入86前面的位置上，将86后移一位，如图4.20所示。

（5）第五次排序。取原数列第五个位置上的数10分别与29、58、69和86比较，10小于29、58、69和86，因此直接将10插入29前面的位置上，将29、58、69、86依次后移一位，如图4.21所示。

直接插入排序的最终排序结果如图4.22所示。至此，排序完成。

【实例4.5】　使用插入排序法将列表中的数字递增排序。（实例位置：资源包\Code\04\05）

用Python代码实现上方示例中的插入排序算法，具体代码如下：

运行结果如图4.23所示。

【实例4.6】　跳绳比赛排名。（实例位置：资源包\Code\04\06）

某校体育考试，利用插入排序算法将这3位考生的跳绳成绩从高到低排序，并输出冠军、亚军、季军的名单。具体代码如下：

运行结果如图4.24所示。