一、插入排序
常见三种的排序交换、选择、插入。
什么是插入排序？
每一趟都要把待排序数放到有序区中合适的位置插入。 我们以前是把数，把一个待排序数放到有序区的某一端，这是以前的排序方法。
现在不是了，现在是把待排序数放到有序区当中的合适的位置插入，要注意插入位置的确定。
二、描述排序思路
初始 0 1 9 8 5 6 初始排序有5 个数字，0表示数据空间，用来临时存放数据的地方。这是一个空位 0后面才是待排序数，一般称为哨兵位置。
我们在待排序数的前面，由于是数组，我们在前面加了一个特殊的位置，用来保存值
不在列表前加这个空间，或者定义一个临时变量temp都可以.
这个待排序数前面的空间称为哨兵位
第一躺我们准备排序了，准备排序需要有一个有序区，才能谈插入的问题。一般情况
如果有序区为空，数据直接插入就行了。所以第一步可以不做。什么意思呢？
1 9 8 5 6
这5个数字，我们可以认为这个1 已经有序了 ，有序区自然就是1了。
所以第一躺排序顺序就是：
9 1 9 8 5 6
1的位置是不动的，1是有序区，我们需要把9放到哨兵位置，然后1和9比较，如果
1大于9，则右移。1不大于9则不动。升序排序
第二趟开始的时候，就发现 1 和 9就是有序区了，如果想把8加进去，就需要把8放到
哨兵位置 ，接下里就是1 9 8 进行排序的问题了。8 和 9比较，9大进行右移，
9把8覆盖了， 8 1 9 9 5 6 现在列表中数字顺序就是这样了，现在8还没有找到合适
的位置，然后8在和1进行比较，8大于1 ，则1不用进行右移，所以哨兵位置的8则直接
插入了
序列入下：8 1 8 9 5 6
后面进行比较也是如此，所以不在重复
总之目标就是扩大有序区，减少无序区
总结：
结果可为升序或降序排列，默认升序排列。以升序为例
扩大有序区,减小无序区。图中绿色部分就是增大的有序区，黑色部分就是减小的无序区
增加一个哨兵位，图中最左端红色数字,其中放置每一-趟待比较数值
将哨兵位数值与有序区数值从右到左依次比较,找到哨兵位数值合适的插入点
二、代码实现
#时间2023年4月4日
#插入排序
nums=[1,9,8,5,6] #待排序数
print(nums)
nums=[None]+nums #加哨兵
print(nums)
#下面做循序，该怎么确定次数呢？
'''
要注意我们每一趟要做什么？
每一躺要做的事情就是拿一个待排序数，依次跟后面所有的数进行比较
拿 9与有序区中数字比较
第一躺拿9，1是固定下来的，第二趟拿8，所以我们需要知道列表长度
从下标几开始呢？
哨兵占位0 待排序区是 1的位置。所以无序区下标应该是2,到长度-1
由于range的特性是 （1，3） 会输出 1 2 前包后不包含，直接用length就可以
for i in range(2,length)
每次拿到之后，在确定哨兵位置的内容,给待排序数
nums[0]=nums[i]
下面就是比较了，和有序区进行比较，最右端开始，逐个比较，直到合适的位置插入
既然不知道应该比较多少次，则使用while循环
我们需要新加一个索引
'''
length=len(nums)
count_move=0
for i in range(2,length):
nums[0]=nums[i] #待排序数放到哨兵位置
#和有序区比较
#新加一个索引
j =i-1
if nums[j]>nums[0]: #有序区小，不就挪动了
while nums[j]>nums[0]:
#继续写挪动
nums[j+1]=nums[j]
j-=1
count_move+=1
#覆盖
nums[j+1]=nums[0]
print(nums[1:],count_move)