pseudocode - 这个用于插入排序的伪代码是如何工作的？

Question

我正在学习一个伪代码类，除了第 7 行之外，我正在遵循插入排序算法。有人可以解释一下这是什么意思吗？到目前为止的前几行是有意义的：第 6 行表示索引/占位符A[i]向右前进了一步。这是我不清楚“i <- i - 1”的下一步。

1 for j ← 2 to length[A]
2   do key ← A[j]
3     ▹ Insert A[j] into the sorted sequence A[1  j - 1].
4     i ← j - 1
5     while i > 0 and A[i] > key
6      do A[i + 1] ← A[i]
7         i ← i - 1
8     A[i + 1] ← key

Answer 1

当 i 大于 0 时，做一些事情，然后从 i 中减去一个。否则，循环将永远持续下去。（无限循环）

Answer 2

实际上，第 6 行将下一个单元格的值指定为当前单元格的值。第 7 行将索引向后移动 1。实际上，假设您在循环中达到了这一点：

(Assuming the first item is at index 1)
A = { 1, 2, 3, 4, 5, 6 }
i = 4

Line 6: Set A[i+1] to have the value of A[i]
        ==> A[5]                        A[4]
        ==> A = { 1, 2, 3, *5*, 5, 6 }

Line 7: Shift i to the next lower position
        ==> i = 3

在此之后，您已经到达循环的末尾，并在第 5 行返回到循环的顶部，在那里您测试循环的条件并继续。