python - 简单插入排序中的逻辑僵局

Question

我正在自学 Python，但我很难理解一个相对简单的概念。目标是使用插入排序按升序对列表进行排序。这是代码:

def InsertionSort(A):
    for j in range(1, len(A)):
        key = A[j]
        i = j - 1
        while (i >=0) and (A[i] > key):
            A[i+1] = A[i] # this is the not understood point
            i = i - 1
        A[i+1] = key
    print A

我不明白加粗的步骤是如何工作的。例如，如果我有一个列表 [6,5,4,3,1] 并且我进行了第二次迭代，那么我的列表现在不是 [6,6,4,3,1] 吗？我正在分配 A[i+1] (在第一种情况下为 5) A[i] 的值(在第一种情况下为 6)。我的5怎么了？我对代码的最初尝试是:

def InsertionSort(A):
    for j in range(1, len(A)):
        key = A[j]
        i = j - 1
        while (i >=0) and (A[i] > key):
            temp = A[i+1]
            A [i+1] = A[i]
            A[i] = temp
            i = i - 1
        A[i+1] = key
    print A

这个方法也行。我不明白为什么第一个也是如此。有人想试一试吗？

Answer 1

我认为这只是因为行 A[i+1]=key。

第一个算法执行以下操作:考虑列表 [1,2,4,5,3]，假设我们在 j=4 的迭代中，即我们正在考虑列表元素 3。该算法将元素 3 存储在 key 中并检查以下内容:

[1,2,4,5,3]
       ^    5>3 (key) => move 5 forward by 1 => [1,2,4,5,5]
[1,2,4,5,5]
     ^      4>3 (key) => move 4 forward by 1 => [1,2,4,4,5]
[1,2,4,4,5]
   ^        2<3 => stop inner while loop
now, make A[i+1]=key (remember: key is 3):
[1,2,3,4,5]

与上述相反，第二种算法实际上交换每次迭代中的元素:

[1,2,4,5,3]
       ^    5>3 (key) => swap 5 and 3 => [1,2,4,3,5]
[1,2,4,3,5]
     ^      4>3 (key) => swap 4 and 3 => [1,2,3,4,5]
[1,2,3,4,5]
   ^        2<3 => stop while loop 
now, make A[i+1]=key (remember: key is 3): (this is unnecessary!)
[1,2,3,4,5]