为什么插入排序算法的终止循环中的j=n+1不变

Question

我目前正在阅读TCRC算法导论第三版教科书的第二章，我正在阅读作者对该算法的循环不变量的解释。我理解作者对初始化和维护的逻辑。然而，终止是我所陷入的困境。作者声称，在终止时，j=n+1。然而，在算法的伪代码中，j从2循环到n。那么j不应该是n=n-1吗？

编辑：这本书的插入排序伪代码是：

for j = 2 to A.length
key = A[j]
// Insert A[j] into sorted sequence A[1...j - 1]
i = j - 1
while i > 0 and A[i] > key
A[i + 1] = A[i]
i = i  - 1
A[i + 1] = key

编辑：仔细阅读后，我终于明白为什么在终止期间j=n+1了。这是因为for循环从2到n(包括n)，所以在j超过n之后，循环终止，因此在终止时j=n+1。我很感激你的帮助。

Answer 1

免责声明：这可能是完全不正确的。。。这只是脑吐而已。

旁注：由于j在此循环中递增，因此起点与结束条件无关。

for j = 2 to A.length //A.length = n in your question

这个伪代码中有一些歧义。

首先，我们假设j是在这个for循环之外定义的，并且在循环终止时会有一个结束值参见@Dukeling的评论

其次，您的代码以数组为目标，使用j作为索引器：A[j]

for j = 2 to A.length中的to一词存在歧义，是包含还是排除A.length？还有这个索引器A[j]

在常见情况下，对于A[j]中的索引器，j的有效范围是[0...A.length -1]

有些语言使用另一个范围，即：[1...A.length]我认为这是作者想要的，因为A[0]根本没有被击中。

如果是这样的话。。。。并且for条件在其中断循环之前递增j(以测试该条件并查看其为假)，则。。。你会得到j = A.length + 1。

附带说明：

在常见的类C语言中，数组的有效范围为[0...A.length -1]。

在这个C示例中，c在终止后具有A.length的值：

int c = 0;
for (c = 3; c < A.length; c++)
{
}
//c = A.length after the loop is completed.