- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我正在学习算法导论,第 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/
我是一名优秀的程序员,十分优秀!