插入排序（InsertionSort）可以說是最簡單直覺的排序算法了。它的工作原理是通過建構有序序列，對于未排序資料，在已排序序列中從後向前掃描，找到相應位置并插入。
通常以撲克牌舉例： 右邊新來的牌，與左邊有序的老牌依次比較，最終插到合适的位置。
實作
- Basic： 新舊牌每次都要交換一下（兩次操作：舊牌後移一位，新牌前移一位）。 （代碼見下面基礎版）
- Advanced： 每次比較，舊牌後移一位（一次操作）。新牌最後放到空位上。 （代碼見下面改進版）
後者即為通常采用的in-place方式（即隻需用到 O(1)的額外空間的排序），因而在從後向前掃描過程中，需要反複把已排序元素逐漸向後挪位，為最新元素提供插入空間。
複雜度
平均時間複雜度： O(n^2)
最壞時間複雜度： O(n^2）
最優時間複雜度： O(n)
最壞空間複雜度： 總共 O(n) ，需要輔助空間 O(1)
圖例
推薦VisuAlgo，一個資料結構和算法動态可視化的網站。
圖檔來源： 維基百科
圖檔來源： 【圖解算法】排序算法——插入排序
python實作
基礎版
Basic實作方法: 倒序周遊尋找元素arr[i]合适的插入位置
def InsertionSort(arr):
'''
插入排序思路： （撲克牌舉例） 右邊新來的牌，與左邊有序的老牌依次比較，最終插到合适的位置。
實作：
Basic： 新舊牌每次都要交換一下（兩次操作：舊牌後移一位，新牌前移一位）。
Advanced： 每次比較，舊牌後移一位（一次操作）。新牌最後放到空位上。
'''
n = len(arr)
for i in range(,n):
for j in range(i,,-):
if arr[j-]>arr[j]:
arr[j],arr[j-] = arr[j-],arr[j] # 交換
else:
break
改進版
Advanced實作方法： 每次比較，舊牌後移一位（一次操作）。新牌最後放到空位上。
（上面圖例中第二張即直覺表示了改進版的排序過程）
def InsertionSort(arr):
n = len(arr)
for i in range(,n):
temp = arr[i]
# j儲存元素temp應該插入的位置
for j in range(i,-,-):
if arr[j-]>temp and j>:
arr[j] = arr[j-] # 後移即可
else:
break
arr[j] = temp