Python插入法排序，又叫插值排序，是一種簡單但有效的排序算法。插入法排序的基本思想是將一個無序序列中的元素一個一個地插入到一個已排序的序列的適當(dāng)位置。通過這種混合排序的方法，插入法排序可以在短時間內(nèi)對中等大小的無序序列進行排序。

def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key< arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key

上述代碼中，insertion_sort()是插入法排序的主函數(shù)，它接受一個無序數(shù)組作為參數(shù)，函數(shù)在原始數(shù)組上排序。具體實現(xiàn)如下：

• 首先，通過初始循環(huán)從第二個元素開始遍歷，將其存儲在key變量中。
• 然后，通過循環(huán)將key依次與前面的元素進行比較，如果遇到比key大的元素，則將其向右移動一個位置，騰出位置讓key插入。
• 最后，將key插入到已排序的序列中。
• 隨著循環(huán)的進行，整個序列不斷被擴大，直到所有元素被插入到已排序的序列中。

插入法排序與冒泡排序、選擇排序等算法相比，它的時間復(fù)雜度更低，效率更高。雖然最壞情況下的時間復(fù)雜度也是O(n2)，但在實際應(yīng)用中，插入法排序的性能已經(jīng)足夠優(yōu)秀，尤其是在處理中等大小的序列時。