为什么我的插入排序算法会按顺序返回？

Question

我正在使用Python创建一个基本的插入排序算法。

我的教科书显示了插入排序算法这里的psudeocode。

如果我使用python 3遵循该约定，则生成以下代码：

def insertionSort(arr):
#Traverse through 1 to len array
   for j in range(1, len(arr)):
       key = arr[j]
       i = j-1
       while i >0 and arr[i] > key:  #this line seems incorrect?
           arr[i+1] = arr[i]
           i = i-1
       arr[i+1] = key
   return arr

如果我设定arr = 12,11,13,5,6，结果返回为12,5,6,11,12,13，这显然是不正确的。

在调整算法一段时间后，将我标记为不正确的行更改为while i>=0 and arr[i] > key:，该算法给出了正确的输出。我的书中省略等号是不正确的，还是我不明白psuedocode是如何在我的教科书中运行的？

Answer 1

看起来你基本上正确地把这本书的算法翻译成了Python。正如您所看到的，这本书的算法是基于1的，而Python是基于0的.

这本书的算法从索引2开始，但你必须从索引1开始。

这也意味着让while循环一直运行到第一个索引为止。在本书的例子中，这是1，在Python中应该是0。因此，这本书是正确的，但你也是正确的(因为索引惯例的差异)。

Answer 2

def insertionSort(arr):
#Traverse through 1 to len array
   for j in range(1, len(arr)):
       key = arr[j]
       i = j-1
       # you need to change here to i>=0
       while i >= 0 and arr[i] > key:  #this line seems incorrect?
           arr[i+1] = arr[i]
           i = i-1
       arr[i+1] = key
   return arr