python - 插入排序不能正确排序数组

Question

下面是我的插入排序，和《算法导论》一书中的完全一样:

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]

让它们乱序我做错了什么？

Answer 1

在 Introduction to Algorithms 中，他们总是假设数组从索引 1 开始，所以您的 range() 是从 1 开始的，但是python 列表是基于 0 的索引。这意味着您永远不会比较 5，它位于 A[0]。注意 5 排序后的所有内容。

将您的 for 循环修改为 -

for j in range(0, len(A)):

和你的 while 条件

while i >= 0 and A[i] > key:

应该可以解决问题。