algorithm - 无法从算法导论第 3 版中获得插入排序。正确的。我的思维错误在哪里？

Question

我正在学习算法导论，第 3 版。首先要解释的事情之一是插入排序。第 18 页有一些伪代码:

A = { 5, 2, 4, 6, 1, 3 };

INSERTION-SORT(A)
1 for j = 2 to A.length
2   key = A[j]
4   i = j - 1

5   while (i > 0 and A[i] > key)
6     A[i + 1] = A[i]
7     i = i - 1

8   A[i + 1] = key

它说使用伪代码可以很容易地将其翻译成任何一种语言(C、C++、Java，他们没有提到，但我猜 C# 也是)。因为我用 C# 编程，所以我用 LinqPad 翻译它。

int[] a = { 5, 2, 4, 6, 1, 3 };

for (var j = 1; j < a.Length; j++)
{
    var key = a[j];

    var i = j - 1;

    while(i > 0 && a[i] > key)
    {
        a[i + 1] = a[i];
        i--;
    }

    a[i + 1] = key;
}

a.Dump();

你可能会问，为什么 j 从 1 开始，明明是 2？在书中，数组的索引从 1 开始。是的，我现在可能应该更新所有的 [i - 1] 和 [i + i]

无论如何，在我完成后，我运行代码并注意到它实际上没有正确排序。输出是 { 5, 1, 2, 3, 4, 6 }。已经很晚了，应该停下来，但我努力使代码正确。我做了一切，甚至采用了书中的伪代码(从 2 开始)。仍然不是正确的输出。

我联系了这本书的一位教授，他把插入排序的代码发给我，用 C:

void insertion_sort(int *A, int n) {
  for (int j = 2; j <= n; j++) {
    int key = A[j];
    int i = j-1;

    while (i > 0 && A[i] > key) {
      A[i+1] = A[i];
      i--;
    }

    A[i+1] = key;
  }
}

用 C# 翻译:

int[] a = { 5, 2, 4, 6, 1, 3 };

for (var j = 2; j <= a.Length; j++)
{
    var key = a[j];

    var i = j - 1;

    while(i > 0 && a[i] > key)
    {
        a[i + 1] = a[i];
        i--;
    }

    a[i + 1] = key;
}

我得到一个超出范围的数组。好吧，也许:

int[] a = { 5, 2, 4, 6, 1, 3 };

for (var j = 2; j <= a.Length - 1; j++)
{
    var key = a[j];

    var i = j - 1;

    while(i > 0 && a[i] > key)
    {
        a[i + 1] = a[i];
        i--;
    }

    a[i + 1] = key;
}

输出:{ 5, 1, 2, 3, 4, 6 }

我在想，这不可能是正确的。伪代码表示 2 到 array.Length。是 2 < array.Length，还是 2 <= array.Length？这是怎么回事？

我个人认为是因为while循环中的0 > 0谓词。实际上每次都达不到一次。

我的解释(来 self 发给教授的电子邮件，懒得打一遍):

循环仍然以 { 5, 1, 2, 3, 4, 6 } 结束的原因是因为 i > 0 谓词。每次在 while 循环中减去 i 的 1 (i--)。这最终会导致 0 > 0 以 false 结束(只有 0 == 0 会返回 true)，但此时循环仍需要再运行一次.它不断地落后一分。它应该再执行 while 循环 1 次以正确排序。

另一种解释:

当 j 以 2 开头时，key == 4，i == 1 和 a[i] == 2。while 循环在这种情况下不会运行，因为 2 > 0 但 2 不大于 4。

j == 3, 关键== 6， 我 == 2, a[i] == 4

While 循环不会运行，因为 4 不大于 6

j == 4, 关键== 1， 我 == 3, a[i] == 6

这次While循环运行:

a[i + 1] = a[i] -> a[4] = a[3] -> { 5, 2, 4, 6, 6, 3 } i-- -> i == 2

再次 while 循环，因为 2 > 0 和 4 > 1

a[i + 1] = a[i] -> a[3] = a[2] -> { 5, 2, 4, 4, 6, 3 } i-- -> i == 1

再次 while 循环，因为 1 > 0 和 2 > 1

a[i + 1] = a[i] -> a[2] = a[1] -> { 5, 2, 2, 4, 6, 3 } i-- -> i == 0

这就是(在我看来)错误的地方。 i 现在等于 0，但是 while 循环应该再运行一次以使 5 从第 0 个位置中取出。

教授向我保证他是正确的，但我无法得到正确的输出。我的想法哪里出了问题？

---

教授发给我的 C 代码中的数组实际上是从索引 1 开始的。我不知道这一点，检查 C 数组后我发现它们都是从 0 开始的。是的，然后是 C代码没有产生正确的输出。教授向我解释了这一点，现在这些碎片都归位了。

Answer 1

我认为教授使用的是基于 1 的数组表示法，因此对于 while (i > 0 && a[i] > key)，您在循环中缺少 a[0] 元素.将您的初始代码更改为此即可:

for (var j = 1; j < a.Length; j++)
{
    var key = a[j];

    var i = j - 1;

    while(i >= 0 && a[i] > key)  <----------- Try this, or you'd miss the first number
    {
        a[i + 1] = a[i];
        i--;
    }

    a[i + 1] = key;
}

此外，如果你想使用教授的代码，只需忽略那里的第 0 个元素即可。

附带说明一下，您联系了谁？里维斯特？科曼？下次我感到困惑时，我想我也会尝试联系他，因为这位教授似乎回复了邮件:)