Insertion_Sort() 实施（错误），Python

Question

我有两个版本的 INSERTION SORT 实现；我认为是等价的，但是第二个returns排序列表错误。 这是第一个：

def insertionSort(A):
for j in range(1,len(A)):

    key = A[j]
    i = j

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

    A[i] = key

这是第二个：

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]
            i -= 1

        A[i+1] = key

我已经用这个 C 数组测试了这两个算法

C = [54,26,93,17,77,31,44,55,20]
insertionSort(C)
print(C)

在第一种情况下，我的数组排序正确；在第二种情况下，我的结果是：

[54, 17, 20, 26, 31, 44, 55, 77, 93]

第二种情况来自我课本上的伪代码。 为什么不能正常工作？

Answer 1

这是对您的第二个代码的更正：

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]
            i -= 1

        A[i+1] = key

区别在于while循环中>=向>。为了理解，让我们参考插入排序的行为。该排序算法假定数组 [0, j-1] 已排序，然后将元素放在正确的位置。

现在，假设我们不想对 [4,3,2,0,5,6,7] 进行排序，我们现在处于该状态：

A = [2, 3, 4, 0, 5,6,7]

前三个元素在正确的位置，我们需要将0放在正确的位置（索引0）。从 i = 2 到 i = 0，条件 A[i] > key 始终为真。所以，我们会做：A[3] = A[2]，A[2] = A[1]，A[1] = A[0]。

然后我们将离开i = -1的循环并设置A[i+1] = A[0] = 0。

在您以前的版本中，循环会在 i = 0 处停止，最后一条指令会执行 A[0+1] = A[1] = 0。这就是为什么当你在算法中给出 [2, 3, 4, 0, 5,6,7] 时，它会给出一个糟糕的结果。

Insertion_Sort() 实施（错误），Python

Insertion_Sort() implementation (Error), Python

python

indexing

implementation

insertion-sort