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

Question

我正在参加一个名为算法的基础 class。我们正在研究排序算法；我们得到了以下伪代码作为插入排序算法的示例。但是我认为这是错误的。

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 开始，因为第一张牌是 "already ordered"，因为它是迄今为止唯一的一张牌。

第二行写错了吗？从 i 到 2 怎么可能用 j 呢？当然，这在未来是行不通的。另外，休息时间不应该减少缩进吗？所以只有一个选项卡而不是两个？

编辑

这里是算法的"main idea"。如您所见，索引 j 的范围从这里看起来是错误的。

编辑2 所以在这里我试着写下我脑海中发生的事情，阅读这个伪代码：假设我有列表 (5,3,8,7,2,4,1,6)。我将写 | 以将 "hand" 与套牌分开，同时我将写 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

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

长度为 N 的数组具有索引 1..N
for循环覆盖指定范围，不考虑方向；因此，for x in {a,...,b} 将经过 a, a+1, a+2, ..., b-1, b if a <= b，但会经过 a, a-1, a-2, ..., b+1 b if a >= b.

Answer 2

第二行不是错误，因为您试图获取 i-th 元素（外循环上的运行）并插入到它之前的分区中。然后您必须将此元素与它之前的分区进行比较以使其排序。

这个 SO post 有一个很好的可视化： Insertion Sort vs. Selection Sort

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

Sorting Algorithm: Insertion sort - Pseudocode given in lectures seems wrong

sorting

algorithm

pseudocode