排序算法python版（3）-插入排序算法

• 插入排序算法动态图如下：



• 插入算法思路
  插入算法和玩扑克牌时排序的方式很像，具体思路如下：
  1、首先将第一个数作为已经有序的，取第二个数，然后观察如果第一个数比第二个数小，则此时第二个数不栋，若第二个数比第一个数小，则将第一个数移至第二的位置，将原第二个数移至第一个位置
  2、此时第一第二数已经有序，取第三个数，然后依次将第三个数与第二个第一个数比较，插入到合适的位置
  3、此时前三个数已经有序，取第四个数，然后依次将第四个数与前三个数比较，插入合适的位置
  …
  循环完成后，所有的数有序

代码如下：最坏的情况

def insert_sort(datas):
count=0
for i in range(1,len(datas)):
temp=datas[i]
for j in range(i,0,-1):
if temp<datas[j-1]:
datas[j],datas[j-1]=datas[j-1],datas[j]
count+=1
else:
if j!=i:
datas[j]=temp
count+=1
break
print(f"经过第 {i} 轮插入排序后的结果：",datas)
print(f"共经过 {count} 次交换或赋值操作")
return datas

if __name__=="__main__":
datas=[10,9,8,7,6,5,4,3,2,1,0]
datas=insert_sort(datas)

执行结果如下：

经过第 1 轮插入排序后的结果： [9, 10, 8, 7, 6, 5, 4, 3, 2, 1, 0]
经过第 2 轮插入排序后的结果： [8, 9, 10, 7, 6, 5, 4, 3, 2, 1, 0]
经过第 3 轮插入排序后的结果： [7, 8, 9, 10, 6, 5, 4, 3, 2, 1, 0]
经过第 4 轮插入排序后的结果： [6, 7, 8, 9, 10, 5, 4, 3, 2, 1, 0]
经过第 5 轮插入排序后的结果： [5, 6, 7, 8, 9, 10, 4, 3, 2, 1, 0]
经过第 6 轮插入排序后的结果： [4, 5, 6, 7, 8, 9, 10, 3, 2, 1, 0]
经过第 7 轮插入排序后的结果： [3, 4, 5, 6, 7, 8, 9, 10, 2, 1, 0]
经过第 8 轮插入排序后的结果： [2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 0]
经过第 9 轮插入排序后的结果： [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0]
经过第 10 轮插入排序后的结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
共经过 55

最好的情况：

def insert_sort(datas):
count=0
for i in range(1,len(datas)):
temp=datas[i]
for j in range(i,0,-1):
if temp<datas[j-1]:
datas[j],datas[j-1]=datas[j-1],datas[j]
count+=1
else:
if j!=i:
datas[j]=temp
count+=1
break
print(f"经过第 {i} 轮插入排序后的结果：",datas)
print(f"共经过 {count} 次交换或赋值操作")
return datas

if __name__=="__main__":
datas=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
datas=insert_sort(datas)

执行结果如下：可以发现，当已经有序的了时候速度会很快

经过第 1 轮插入排序后的结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
经过第 2 轮插入排序后的结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
经过第 3 轮插入排序后的结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
经过第 4 轮插入排序后的结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
经过第 5 轮插入排序后的结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
经过第 6 轮插入排序后的结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
经过第 7 轮插入排序后的结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
经过第 8 轮插入排序后的结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
经过第 9 轮插入排序后的结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
经过第 10 轮插入排序后的结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
共经过 0