为什么我的插入排序算法 return 乱序

Question

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

我的教科书展示了插入排序算法的伪代码here。

如果我使用 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] 结果 returns 为 [12,5,6,11,12,13] 这显然不是正确的排序。

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

Answer 1

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

Answer 2

看来您基本上正确地将本书的算法翻译成了 Python。如您所见，本书的算法是从 1 开始的，而 Python 是从 0 开始的。

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

这也意味着让 while 循环一直运行到第一个索引。在本书的例子中，它是 1，而在你的例子中，它应该是 Python 中的 0。所以这本书是正确的，但你也是正确的（因为索引约定的差异）。

为什么我的插入排序算法 return 乱序

Why does my insertion sort Algorithm return out of order

python

algorithm

sorting

insertion-sort

insertion