gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:27:53 25 4
gpt4 key购买 nike

我正在学习算法导论,第 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代码没有产生正确的输出。教授向我解释了这一点,现在这些碎片都归位了。

最佳答案

我认为教授使用的是基于 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 个元素即可。

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

关于algorithm - 无法从算法导论第 3 版中获得插入排序。正确的。我的思维错误在哪里?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6788987/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com