无法从第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？这里发生了什么？

我个人认为这是因为0 > 0while循环中的谓词.它实际上每次都不足一次.

我的解释(从我发给教授的电子邮件中,懒得将其全部输入):

循环仍然最终的原因{ 5, 1, 2, 3, 4, 6 }是因为i > 0谓词.每次在while循环中你减去i(i--)的1.这最终将导致0 > 0哪个结束为假(仅0 == 0返回true),但这是循环仍然需要再运行一次的时间.它不断下降.它应该进行while循环1更多时间来正确排序.

另一种解释:

当j以2开始时,键== 4,i == 1和a [i] == 2.在这种情况下,while循环不会运行,因为2> 0但是2不大于4.

j == 3, key == 6, i == 2, a[i] == 4

while循环不会运行,因为4不大于6

j == 4, key == 1, i == 3, a[i] == 6

这次循环运行时:

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

同时循环因为2> 0和4> 1

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

同时循环,因为1> 0和2> 1

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

这就是它(在我看来)错误的地方.我现在等于零,但是while循环应再运行一次以获得第五个位置的5.

教授向我保证他是正确的,但我无法得到正确的结果.我的想法在哪里出错了？

---

教授发给我的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个元素.

在旁注,你联系谁？维斯特？科尔曼？下次我感到困惑,我想我也会尝试联系他,因为看起来这位教授回复邮件:)