4.3 插入排序算法
插入排序法是将数列中的元素逐一与已排序好的数据进行比较，进而找到合适的位置并插入。例如，在排好顺序的两个元素中插入第三个元素，就需要将其与其他两个元素做比较，插入合适的位置。也就是说，将第三个元素插入数列后，得到的新数列依然是排好序的。接着将第四个元素插入，以此类推，直至排序完成。直接插入排序法最后的结果也有两种形式，即递增数列和递减数列。
例如，有这样一组数据：58, 29, 86, 69, 10，如图4.16所示。采用插入排序算法使其递增排序，步骤如下。
（1）第一次排序。先用第一个位置的数据占位，放在新数列的第一个位置，如图4.17所示。
图4.16 原始值
图4.17 第一次插入
（2）第二次排序。取原数列第二个位置上的数29与58进行比较，29小于58，所以将其插入58前面的位置，将58向后移一位，如图4.18所示。
（3）第三次排序。取原数列第三个位置上的数86与29和58进行比较，86大于29和58，因此直接将86插入新数列的第三个位置上，如图4.19所示。
图4.18 第二次插入
图4.19 第三次排序过程
（4）第四次排序。取原数列第四个位置上的数69与29、58和86比较，69大于29和58，小于86，因此直接将69插入86前面的位置上，将86后移一位，如图4.20所示。
图4.20 第四步排序过程
（5）第五次排序。取原数列第五个位置上的数10分别与29、58、69和86比较，10小于29、58、69和86，因此直接将10插入29前面的位置上，将29、58、69、86依次后移一位，如图4.21所示。
图4.21 第五次排序过程
直接插入排序的最终排序结果如图4.22所示。至此，排序完成。
图4.22 最终的排序结果
【实例4.5】 使用插入排序法将列表中的数字递增排序。（实例位置：资源包\Code\04\05）
用Python代码实现上方示例中的插入排序算法，具体代码如下：
运行结果如图4.23所示。
【实例4.6】 跳绳比赛排名。（实例位置：资源包\Code\04\06）
某校体育考试，利用插入排序算法将这3位考生的跳绳成绩从高到低排序，并输出冠军、亚军、季军的名单。具体代码如下：
运行结果如图4.24所示。
图4.23 插入排序法
图4.24 运行结果