从clrs书上看，插入排序for循环为什么要迭代n次？

Question

为什么第一行从 2 开始迭代了 n 次？不应该是 n-1 吗？ 还有为什么第 2 行和第 3 行是 n-1 而不是 n？

Answer 1

这里循环语句被认为是多执行了一次，因为它在第一次迭代之前和最后一次迭代之后进行了比较。让我们考虑一下 A.length = 3。我们只有两次迭代，但是三个比较：

j := 2
if j > A.length then exit the loop // first comparison, false
... first loop iteration goes

j := j + 1 // j = 3 now
if j > A.length then exit the loop // second comparison, false
... second loop iteration goes

j := j + 1 // j = 4 now
if j > A.length then exit the loop // third comparison, true

因此如您所见，我们必须比较三次，但循环体只执行了两次。第一次比较是必要的，因为如果 A.length = 1 我们根本不应该执行循环体。