# 插入排序
## 示意圖
## 運作步驟
1. 第一個元素可被認為已被排序。
2. 取出下一個元素，在已排序的元素序列中從后向前掃描。
3. 如果該元素（已排序）大于新元素，將該元素移到下一位置。
4. 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置。
5. 將新元素插入到該位置后。
6. 重復步驟2~5。
## 助記碼
```
i∈[1,N) //循環N-1遍
j∈[i, 0, -1) //每遍循環已排序部分
swap(j,j-1) //將大值往后移
```
## 算法分析
* 最壞時間復雜度 O(n^2)
* 最優時間復雜度 O(n)
* 平均時間復雜度 O(n^2)
## 實現
```Python
def insertion_sort_1(list):
'''Python中的插入排序算法實現1
:param list: 需要排序的數字列表
:return: 排序結果
'''
list_len = len(list)
for i in range(1, list_len): # 第一個元素默認為已被排序
for j in range(i, 0, -1): # 將已被排序的序列從后向前掃描
if list[j - 1] > list[j]: # 如果該元素（已排序）大于新元素，將該元素移到下一位置
list[j - 1], list[j] = list[j], list[j - 1]
else:
break
return list
def insertion_sort_2(list):
'''Python中的插入排序算法實現2
:param list: 需要排序的數字列表
:return: 排序結果
'''
list_len = len(list)
for i in range(1, list_len): # 第一個元素默認為已被排序
j = i - 1 # 記錄往前掃描的key
while j >= 0 and list[i] < list[j]: # 如果已排序的序列從后往前掃描，發現當前比新元素大，則往后移一位
list[j + 1] = list[j]
j -= 1
list[j + 1] = list[i] # 新元素添加到找到的key后方，前是小，后是大
return list
def insertion_sort_3(list):
'''Python中的插入排序算法實現3
:param list: 需要排序的數字列表
:return: 排序結果
'''
for i in range(1, len(list)): # 第一個元素默認為已被排序
while i > 0 and list[i - 1] > list[i]: # 將新元素和前方元素一一對比，若新元素比較小，則交換兩者位置
list[i], list[i - 1] = list[i - 1], list[i]
i -= 1
return list
```
## 測試
```
$ python insertion_sort.py
插入排序>>>
請輸入需要排序的數字，用英文半角逗號隔開，直接回車則使用默認數據：
需要排序的數字為：
8,-5,10,6,-23,15,45
insertion_sort_1 排序結果：
-23,-5,6,8,10,15,45
insertion_sort_2 排序結果：
-23,-5,6,8,10,15,45
insertion_sort_3 排序結果：
-23,-5,6,8,10,15,45
```
# 代碼庫地址
[https://github.com/liuzhen153/play-algorithm-python](https://github.com/liuzhen153/play-algorithm-python)
