python - 为什么我的插入排序算法乱序返回

Question

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

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

如果我使用 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: 算法不正确的行会给出正确的输出。我的书在省略等号方面是不正确的，还是我不理解伪代码在我的教科书中是如何运作的？

标签： pythonalgorithmsortinginsertion-sortinsertion

Answer 1

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

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

这也转化为保持 while 循环直到第一个索引。在本书的情况下，它是 1，而在你的情况下，它在 Python 中应该是 0。所以这本书是正确的，但你也是正确的（因为索引约定的不同）。