应用场景
应用于非随机且主键不重复的数组排序。即数组基本有序或部分有序下使用，大部分主键相同的情况下性能会下降
原理
与整理扑克的方式相同。遍历N次，每次将第 i 项插入到左侧正确的位置，保持左侧有序直到全部有序
伪代码
for(i = 1; i < N; ++i)
for(j = i; j > 0; --j) #待插入元素a[j]
if a[j] < a[j - 1]
交换a[j]、a[j - 1] #将a[j]向左移动，插入到正确位置
时间与空间复杂度
时间复杂度：对于主键不重复数组
- 平均情况下：O(N^2 /4),进行~N^2 /4次比较和~N^2 /4次交换；
- 最坏情况下：O(N^2 /2),进行~N^2 /4次比较和~N^2 /2次交换；
- 最好情况下：O(N)， 进行N - 1次比较和 0 次交换
特性
- 插入排序所需要的时间取决于数组的初始顺序
- 插入排序需要的交换操作和数组中的倒置数量相同，倒置数量 <= 需要比较的次数 <= (倒置数量 + N - 1）
代码 - Python实现
# 插入排序
def insertion(a):
n = len(a)
for i in range(n):
j = i
while j > 0 and less(a[j], a[j - 1]):
exch(a, j, j - 1)
j -= 1
def less(a, b):
if a <= b:
return True
else:
return False
def exch(a, i, j):
a[i], a[j] = a[j], a[i]
