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

Question

我目前正在阅读 TCRC 算法导论第 3 版教科书的第 2 章，我正在阅读作者对该算法的循环不变量的解释。我理解作者的初始化和维护逻辑。然而，终止是我有点陷入困境的地方。作者声称在终止时，j = n + 1。但是，在算法的伪代码中，j 从 2 循环到 n。那么不应该 j = 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(含)，所以在 j 超过 n 之后，循环终止，因此终止时 j = n + 1。感谢您的帮助。

Answer 1

免责声明:这可能是完全不正确的......这只是一个脑洞。

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

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

这段伪代码有一点歧义。

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

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

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

通常情况下，对于A[j]中的indexer，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.