c++ - T Cormen Book 中的插入排序

Question

我正在阅读 Cormen 的“算法导论”一书，并根据伪代码创建了以下内容。但是，Array 的前两个元素似乎没有排序。我无法发现错误(可能是因为它晚了)。所以我想知道是否有人可以第一眼看到。

#include <iostream>
#include <stdlib.h>

using namespace std;

int main(){
  int input;
  cout << "Enter length of desired array." << "\n";
  cin >> input;
  cout << "\n";

  int A [input];

  //Populate and print the Array.
  for(int i=0; i<input; i++){
    A[i] = rand()%99-1;
    cout << A[i] << " ";
  }

  cout << "\n";

  //Insertion sort.
  for(int j=2; j<input; j++){ //Iterate through the Array.
    int key = A[j]; //Store the current element into key.
    int i = j-1; //Iterator for while loop.
    while(i>0 && A[i]>key){ //Loop to insert A[j] into the sorted sequence.
      A[i+1] = A[i]; //Move the element.
      i=i-1; //New value of i.
      A[i+1] = key; //Update the key
    }
  }

  for(int i=0; i<input; i++){
    cout << A[i] << " ";
  }
  return 0;
}

Answer 1

我没有仔细看，但我认为这本书的伪代码使用的是从一开始的索引，对于用 C(或大多数现代语言)编写的代码，您需要将其调整为从零开始的索引。

主要嫌疑人是

for(int j=2; j<input; j++)

您可能希望从 1 而不是 2 开始。

终止条件

while(i>0 && A[i]>key)

可能还需要更改以确保您高于 -1 而不是 0。

编辑:

仔细观察后，我很确定您确实还必须调整 while。

当然，您还应该查看类似的差一问题的所有上限。