4.3　插入排序算法

插入排序法是將數(shù)列中的元素逐一與已排序好的數(shù)據(jù)進行比較，進而找到合適的位置并插入。例如，在排好順序的兩個元素中插入第三個元素，就需要將其與其他兩個元素做比較，插入合適的位置。也就是說，將第三個元素插入數(shù)列后，得到的新數(shù)列依然是排好序的。接著將第四個元素插入，以此類推，直至排序完成。直接插入排序法最后的結(jié)果也有兩種形式，即遞增數(shù)列和遞減數(shù)列。

例如，有這樣一組數(shù)據(jù)：58, 29, 86, 69, 10，如圖4.16所示。采用插入排序算法使其遞增排序，步驟如下。

（1）第一次排序。先用第一個位置的數(shù)據(jù)占位，放在新數(shù)列的第一個位置，如圖4.17所示。

（2）第二次排序。取原數(shù)列第二個位置上的數(shù)29與58進行比較，29小于58，所以將其插入58前面的位置，將58向后移一位，如圖4.18所示。

（3）第三次排序。取原數(shù)列第三個位置上的數(shù)86與29和58進行比較，86大于29和58，因此直接將86插入新數(shù)列的第三個位置上，如圖4.19所示。

（4）第四次排序。取原數(shù)列第四個位置上的數(shù)69與29、58和86比較，69大于29和58，小于86，因此直接將69插入86前面的位置上，將86后移一位，如圖4.20所示。

（5）第五次排序。取原數(shù)列第五個位置上的數(shù)10分別與29、58、69和86比較，10小于29、58、69和86，因此直接將10插入29前面的位置上，將29、58、69、86依次后移一位，如圖4.21所示。

直接插入排序的最終排序結(jié)果如圖4.22所示。至此，排序完成。

【實例4.5】　使用插入排序法將列表中的數(shù)字遞增排序。（實例位置：資源包\Code\04\05）

用Python代碼實現(xiàn)上方示例中的插入排序算法，具體代碼如下：

運行結(jié)果如圖4.23所示。

【實例4.6】　跳繩比賽排名。（實例位置：資源包\Code\04\06）

某校體育考試，利用插入排序算法將這3位考生的跳繩成績從高到低排序，并輸出冠軍、亞軍、季軍的名單。具體代碼如下：

運行結(jié)果如圖4.24所示。