在这个程序中,我想计算插入排序中数据比较的次数,但是我的代码没有按我的预期工作。
def insertionSort(list):
numOfComp = 0
for i in range(1,len(list)):
value = list[i]
j = i - 1
while j>=0:
if value < list[j]:
list[j+1] = list[j]
list[j] = value
j = j - 1
numOfComp += 1
if value >= list[j]:
numOfComp += 1
j = j - 1
else:
break
print("Number of data comparisons:",numOfComp)
print("Sorted list:",list)
问题是
if value >= list[j]:
numOfComp += 1
j = j - 1
If value >= list[j]
您可以而且应该简单地退出 while 循环并停止进一步比较
此外,您还重复比较两次
请参阅以下精炼代码
def insertionSort(list):
numOfComp = 0
for i in range(1,len(list)):
value = list[i]
j = i - 1
while j>=0:
if value<list[j]:
flag=True
else :
flag=False
numOfComp += 1
if flag:
list[j+1] = list[j]
list[j] = value
j = j - 1
else:
break
print("Number of data comparisons:",numOfComp)
print("Sorted list:",list)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)