插入排序算法是一種簡單直觀的排序算法。工作原理如下：

在第一輪時(shí)，假定第一個(gè)元素為已排序的元素，

而其余元素都是未排序的。

接著，從未排序的元素中選出第一個(gè)元素，

并將它插入到已排序的合適的位置上，使之成為新的已排序的元素。

以此類推，直到所有元素都排序完畢。

import random

# 插入排序
def insertionSort(arr):
 ? ?n=len(arr)
 ? ?for i in range(1, n):
 ? ? ? ?key = arr[i]
 ? ? ? ?j = i - 1
 ? ? ? ?# 將關(guān)鍵值與左側(cè)的每個(gè)元素進(jìn)行比較，直到找到一個(gè)比它小的元素為止
 ? ? ? ?# 如果要降序排列，請將 key<array[j] 改為 key>array[j]
 ? ? ? ?while j >= 0 and arr[j] > key:
 ? ? ? ? ? ?arr[j + 1] = arr[j]
 ? ? ? ? ? ?j = j - 1
 ? ? ? ?# 將 key 放到正確的位置。
 ? ? ? ?arr[j + 1] = key

# 測試
array=random.sample(range(0, 100), 50)
print("原始數(shù)組為:")
print(array)

insertionSort(array)

print('經(jīng)插入排序后的數(shù)組為:')
print(array)

運(yùn)行環(huán)境：python3.8

原始數(shù)組為:

[14, 86, 49, 66, 71, 16, 44, 40, 9, 97, 21, 2, 73, 46, 23, 82, 89, 27, 6, 32, 25, 69, 52, 88, 98, 5, 59, 8, 41, 60, 51, 57, 0, 55, 29, 53, 26, 35, 85, 76, 80, 63, 31, 22, 94, 99, 50, 17, 11, 79]

經(jīng)插入排序后的數(shù)組為:

[0, 2, 5, 6, 8, 9, 11, 14, 16, 17, 21, 22, 23, 25, 26, 27, 29, 31, 32, 35, 40, 41, 44, 46, 49, 50, 51, 52, 53, 55, 57, 59, 60, 63, 66, 69, 71, 73, 76, 79, 80, 82, 85, 86, 88, 89, 94, 97, 98, 99]