插入从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.

您当然也应该检查类似的逐个问题的所有上限.

Answer 2

改成 for (int j = 1; ...)