*****
## 插入排序
插入排序（英語：Insertion Sort）是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。插入排序在實現上，在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。
首先，我們將數組中的數據分為兩個區間，已排序區間和未排序區間。初始已排序區間只有一個元素，就是數組的第一個元素。插入算法的核心思想是取未排序區間中的元素，在已排序區間中找到合適的插入位置將其插入，并保證已排序區間數據一直有序。重復這個過程，直到未排序區間中元素為空，算法結束。
如圖所示，要排序的數據是 4，5，6，1，3，2，其中左側為已排序區間，右側是未排序區間。
插入排序也包含兩種操作，一種是元素的比較，一種是元素的移動。當我們需要將一個數據 a 插入到已排序區間時，需要拿 a 與已排序區間的元素依次比較大小，找到合適的插入位置。找到插入點之后，我們還需要將插入點之后的元素順序往后移動一位，這樣才能騰出位置給元素 a 插入。
### 插入排序演示
```
def insert_sort(li):
# 從第二個位置，即下標為1的元素開始向前插入
for i in range(1, len(li)):
# 從第i個元素開始向前比較，如果小于前一個元素，交換位置
for j in range(i, 0, -1):
if li[j] < li[j - 1]:
li[j], li[j - 1] = li[j - 1], li[j]
li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
insert_sort(li)
print(li)
```
