- 插入排序算法动态图如下:
- 插入算法思路
插入算法和玩扑克牌时排序的方式很像,具体思路如下:
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 次交换或赋值操作