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

Question

我正在阅读《算法导论》第三版这本书。首先解释的事情之一是插入排序。第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 }

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

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

我的解释（来自我发给教授的电子邮件，懒得把它全部打一遍）：

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

另一种解释：

当 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 == 2

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

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

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

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

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

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

---

教授发给我的 C 代码中的数组实际上是以 1 的索引开始的。我不知道这一点，检查 C 数组时我发现它们都以 0 开头。是的，那么 C 代码就不会了。 t 产生正确的输出。教授向我解释了这一点，现在这些碎片就各归其位了。

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 个元素即可。

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

Answer 2

你不应该考虑翻译伪代码，而应该考虑
翻译你对算法的理解。

该数组一开始是完全未排序的。该算法的工作原理是
获取连续的未排序元素并将它们插入到
已经排序的部分。起始“排序部分”是第一个元素，
这是简单的“排序”。因此，要插入的第一个元素是
第二。第二个元素的索引是哪个？你的j必须
从那里开始。

然后，i 必须遍历每个已排序元素的索引，
向后，直到找到插入当前值的位置
或元素耗尽。那么，它必须从哪里开始，又从哪里开始呢？
它必须结束吗？注意它实际上会查看每个元素
是必须的。

众所周知，相差一的错误很难被发现（并且混合
基于 1 和基于 0 的数组的概念肯定没有帮助），但不要
只是摆弄直到它看起来有效。尝试了解什么是
代码实际上是在做。

Answer 3

我相信你关于 i>0 的论点是正确的，无论教授如何。说。在伪代码中，循环是 while i > 。 0 并且数组索引从 1 开始。在 C# 中，数组索引从 0 开始，因此您应该使用 while i >= 0。

Answer 4

我遇到了同样的问题。下面是正确实现上述伪代码的 C 代码。我没有像其他解决方案一样使用指针。

事实上，棘手的部分是伪代码使用基于 1 的数组表示法，这与大多数编程语言不同！

#include <stdio.h>

int main(void)
{
  int A[] = { 50, 20, 10, 40, 60, 30 };
  int j, key, len, i;
  len = (sizeof(A)) / (sizeof(A[0]));

    for (j = 1; j < 6; j++) {  <-- Change here
      key = A[j];
      // Insert key into the sorted sequence A[1 .. j - 1].
      i = j - 1;
      while (i >= 0 && A[i] > key) {  <-- Change here
          A[i + 1] = A[i];
          i--;
      }
      A[i + 1] = key;
    }

    for (int z = 0; z < len; z++) {
       printf("%d ", A[z]);
    }
   printf("\n");
 }

Answer 5

我也遇到了你的问题，并且找到了解决方案。我用java编写了算法，如下所示。

int a[] = {5,2,4,3,1};
    int key;
    int i;
    for(int j = 0; j < 5; j++)
    {
        key = a[j];
        i = j - 1;

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

        for(int k=0; k<a.length;k++)
        {
            System.out.print(a[k]+" ");
        }
    }

Answer 6

请记住：A.length 从 0 到 n，因此 Length 应为 A.Length -1。我使用那本书，用西班牙语用 C++ 为我的学生编写了这个算法。用 C# 翻译很简单。

一些翻译，以便您可以更好地理解

largo = length
actual = current
cadena = chain

void InsertionSort::Sort(char cadena[])
{
    int largo = strlen(cadena) - 1;
    char actual = '0';
    int i = 0;

    for (int j = 1; j <= largo; j++)
    {
        actual = cadena[j];
        i = j - 1;
        while(i >= 0 && cadena[i] > actual)
        {
            cadena[i + 1] = cadena[i];
            i--;
        }
        cadena[i + 1] = actual;
    }
}

Answer 7

当转换为 0 数组时，请注意您可能会错过数组的第一个元素。
解决这个问题的一种方法是 while i > -1;

JavaScript：

A = [5,2,4,6,1,3];
for (let j=1; j < A.length; j++) {
  let key = A[j];
  let i = j-1;
  while(i>-1 && A[i] > key) {
    A[i+1] = A[i];
    i = i-1;
  }
  A[i+1] = key;
}
console.log(A);