这是我的插入排序,与《算法导论》书中的方式完全一样:
def insertion_sort():
A = [5,2,4,6,1,3]
for j in range(1, len(A)):
print 'j:'+str(j)
key = A[j]
print 'key:'+str(key)
i=j-1
print 'i:'+str(i)
while i > 0 and A[i] > key:
A[i+1] = A[i]
i=i-1
print 'new i: '+str(i)
print 'swapping value: '+str(A[i]) + ' with value: '+str(A[i+1])
print ' '
A[i+1] = key
print A
打印:
[5, 1, 2, 3, 4, 6]
我做错了什么,导致它们出现故障?
最佳答案
在算法简介中,他们总是假设数组从索引 1 开始,因此您从 1 开始 range()
,但是python 列表是从 0 开始索引的。这意味着您永远不会比较位于 A[0]
的 5
。请注意 5
之后的所有内容均已排序。
将 for 循环修改为 -
for j in range(0, len(A)):
以及你的 while 条件
while i >= 0 and A[i] > key:
应该可以解决问题。
关于python - 插入排序不能正确排序数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22332824/