顾名思义，直接插入排序是一种插入排序。排序过程中不需要借助硬盘来保存临时数据，所以它也是一种内部排序。
直接插入排序的思想是将一个序列在逻辑上分为两部分组成，一半是已经排序好的，一半是没经过排序的，要做的是将数据从没排序的部分拿出来，然后在排序好的部分里找个合适的位置插入。
算法的空间复杂度是：O(1)
算法的时间复杂度是：O(n^2)
# 直接插入排序
import numpy as np
def insert_sort(data: list):
init = np.array([0]) # 将数组第一个位置留空，或者作为哨兵
unsort = np.append(init, data)
for i in range(2, unsort.size):
if unsort[i] < unsort[i-1]:
unsort[0] = unsort[i] # 将待插入的记录暂存到监视哨
unsort[i] = unsort[i-1] # i-1位置已经比较过了，可以向后移动
for j in range(i-2, -1, -1): # 从后向前寻找插入位置，比较区间: [i-2, ..., 0]
if unsort[0] < unsort[j]:
unsort[j+1] = unsort[j] # 比监视哨大的元素都向后移一位，腾出插入空间
else:
unsort[j + 1] = unsort[0] # 完成本轮插入
break
return unsort[1:]
def test_1():
a = [1, 45, 76,
89, 84, 23,
11, 32, 44]
print(f"排序前: {a}")
print(f"排序后: {insert_sort(a)}")
def test_2():
b = [i for i in range(10, 0, -1)]
print(f"排序前: {b}")
print(f"排序后: {insert_sort(b)}")
if __name__ == '__main__':
test_2()
