排序算法：插入排序-讲座中给出的伪代码似乎是错误的

Question

我在上一门叫做算法的基础课。我们正在研究排序算法；我们得到了以下伪代码作为插入排序算法的示例。然而我认为这是错误的。

For i in {2,..,n}:
    For j in {i,..,2}:
        If a(j)<a(j-1), swap a(j) and a(j-1)
        Else, Break

我理解第一行——它从2开始，因为第一张卡是“已经订购的”，因为它是迄今为止唯一的一张卡。

第二行是错误的吗？我们怎么能从i到2使用j呢？当然，这在未来不可能成立。另外，断裂处是否应该减少凹痕？所以只有一个标签而不是两个？

编辑

Edit2所以在这里，我试着写我脑海中发生的事情，阅读这个伪代码：假设我有列表（5,3,8,7,2,4,1,6)。我将写|来将手与甲板分开，我还将写5_来强调我正在看的元素。所以我们开始吧：

i = 1, (5|3,8,7,2,4,1,6)
i = 2, (5,3|8,7,2,4,1,6), now j in {2}, so we only have j = 2, a(j=2)=3 < a(j=1)=5, hence swap 3 with 5
i = 3, (3,5,8|7,2,4,1,6), j in {2,3}, so j=2 gives a(j=2)=5 !< a(j=1)=3 SO WE BREAK!
i = 4, (3,5,8,7|2,4,1,6), j in {2,3,4}, so j = 2 gives a(j=2)=5 !< a(j=1)=3, SO WE BREAK

正如你所看到的，从现在开始，这将永远发生，因为我们从2开始，因为我们打破了它！所以即使j的整数集增加，我们也不能再增加2，因为我们违反了条件

Answer 1

第二行不是错误，因为您试图获取第i个元素（在外部循环上运行）并在其前面插入分区。然后，您必须将该元素与之前的分区进行比较，以便对其进行排序。

这个SO帖子有一个很好的可视化：插入排序与选择排序

Answer 2

如果您做出以下假设，则代码有效：

• 长度N的数组具有索引1。。N
• For循环覆盖指定范围，无论方向如何；因此，{a，…，b}中x的将通过a，a1，a2。。。，b-1，如果a