我正在通过“算法入门”第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谓词。它实际上每次都不足一次。
我的解释（从我发给教授的电子邮件中，懒得将其全部输入）：
循环仍然以{ 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代码没有产生正确的输出。教授向我解释了这一点，现在它们已经落到了原点。
我认为教授正在使用基于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个元素。
在旁注，你联系谁？维斯特？科尔曼？下次我感到困惑，我想我也会尝试联系他，因为看起来这位教授回复邮件:)
您不应该考虑翻译伪代码，而应该考虑翻译您对算法的理解。
该数组最初完全未排序。该算法通过获取连续的未排序元素并将它们插入已经排序的部分来工作。起始的“排序部分”是第一个元素，它被简单地“排序”。因此，要插入的第一个元素是第二个元素。哪个是第二个元素的索引？你的j必须从那里开始。
然后，i必须向后遍历每个已排序元素的索引，直到它找到插入当前值的位置或用完元素。那么，它必须从哪里开始，它必须在哪里结束？注意它实际上看每个元素是必须的。
众所周知，逐个错误很难发现（并且混合基于1和0的数组的概念肯定没有帮助），但不要只是在它看起来有效之前摆弄。尝试了解代码实际上在做什么。
我相信你关于i>0的论点是正确的，无论教授是什么。说。在伪代码中，循环是while i > 0，数组索引从1开始。在C＃中，数组索引从0开始，因此你应该有while i >= 0。
我也遇到了你的问题，我找到了解决方案。我用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]+" ");
}
}
我遇到了同样的问题。下面是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");
}
记住：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;
}
}