
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 运行结果