- 左边为有序区，右边为无序区
- 从第二个元素跟第一个元素(假定为有序)对比，
- 如果当前元素大于新元素，将扫描元素移动到下一位
- 然后向左移位跟左有序区对比插入
- 对于之后的元素重复步骤1~4
# num=[9,8,1,5,6]
num=[1,9,8,5,6]
for i in range(len(num)):
cur=num[i]
j=i-1
while j>=0 and num[j]>cur:
num[j+1] = num[j]
j-=1
num[j+1]=cur
print(i,num)
0 [1, 9, 8, 5, 6] # <0 不进while
1 [1, 9, 8, 5, 6] # 1<9 不动
2 [1, 8, 9, 5, 6]
3 [1, 5, 8, 9, 6]
4 [1, 5, 6, 8, 9]
while过程
num=[1,9,8,5,6]
for i in range(len(num)):
cur=num[i]
j=i-1
while j>=0 and num[j]>cur:
print(f'i={i} now: {num}')
num[j+1] = num[j]
print(f"cur:{cur} {num[j]} > {cur} {num}")
j-=1
num[j+1]=cur
i=2 now: [1, 9, 8, 5, 6]
cur:8 9 > 8 [1, 9, 9, 5, 6]
i=3 now: [1, 8, 9, 5, 6]
cur:5 9 > 5 [1, 8, 9, 9, 6]
i=3 now: [1, 8, 9, 9, 6]
cur:5 8 > 5 [1, 8, 8, 9, 6]
i=4 now: [1, 5, 8, 9, 6]
cur:6 9 > 6 [1, 5, 8, 9, 9]
i=4 now: [1, 5, 8, 9, 9]
cur:6 8 > 6 [1, 5, 8, 8, 9]
复杂度
直接插入排序的时间复杂度是O(N2),空间复杂度O(1)。 假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？N-1！因此，直接插入排序的时间复杂度是O(N2)。
稳定性
直接插入排序是稳定的算法，它满足稳定算法的定义。 算法稳定性 – 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！
冒泡排序，相同数据不交换，稳定
直接选择排序，相同数据前面的先选择到，排到有序区，不稳定
直接插入排序，相同数据不移动，相对位置不变，稳定