澄清插入排序实现的输出

Question

我希望对 Python 中实现的插入排序算法进行澄清。我正在使用此伪代码作为指南来实现该算法：

完全按照下面的方式使用实现（替换 for 循环中的索引 2 以从 0 开始的 python 索引：

l = [31, 41, 59, 26, 41, 58]
for j in range(1, len(l)):
    key = l[j]
    i = j - 1
    while i > 0 and l[i] > key:
        l[i+1] = l[i]
        i = i - 1
    l[i+1] = key

print(l)

>> [31, 26, 41, 41, 58, 59]

如您所见，它对列表中位置零以外的所有值进行了排序。

但是，如果我将 while 循环中的条件索引从 i > 0 更改为 i >= 0，则列表在输出时正确排序：

l = [31, 41, 59, 26, 41, 58]
for j in range(1, len(l)):
    key = l[j]
    i = j - 1
    while i >= 0 and l[i] > key:
        l[i+1] = l[i]
        i = i - 1
    l[i+1] = key


print(l)
>> [26, 31, 41, 41, 58, 59]

有人能解释一下为什么会这样吗？

Answer 1

您记得从索引中减去 1，因为 Python 的列表在 for j 中是 zero-based。你忘了在 while i > 0 中做同样的事情。将 while i > 0 替换为 while i >= 0 与 while i > -1

相同

澄清插入排序实现的输出

Clarification on output of insertion sort implementation

python

algorithm

insertion-sort