插入从T Cormen书中排序

Question

我正在通过Cormen的“算法导论”一书工作，并且我从伪代码创建了以下内容。但是，数组的前两个元素似乎没有进行排序。我无法发现错误（可能是因为它晚了）。所以我想知道是否有人能从第一眼看到。

#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; ...)

Answer 3

其实你的代码是正确的，但你的for循环初始化的问题。用于插入排序的伪代码是：

for j ←1 to length(A)-1 
key ← A[ j ] 
> A[ j ] is added in the sorted sequence A[0, .. j-1] 
i ← j - 1 
while i >= 0 and A [ i ] > key 
    A[ i +1 ] ← A[ i ] 
    i ← i -1 
A [i +1] ← key 

实际上，您的代码不考虑数组的第一个元素。它只是从数组的第二个元素开始排序，得到这种类型的结果。

只要将j的初始化更改为1，它就可以正常运行。

Answer 4

您可以使用此代码，我已经纠正你的错误

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

using namespace std; 

int main(){ 
    int input; 

    cout<< "Enter length of desired array"; 
    cin>>input; 

    cout<<"\n"; 

    int A[input]; 

    for(int i = 0 ;i <input ; i++) 
    { 
     A[i] = rand() % 100; 
     cout<<A[i] << "\t"; 
    } 

    cout<<"\n"; 

    for(int j =1; j<input ; j++) 
    { int i; 
     int key = A[j]; 
     i = j-1; 
     while(i >=0 && A[i] > key) 
     { 
      A[i+1] = A[i]; 
      i = i-1; 
      A[i+1] = key; 
     } 
    } 

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

Answer 5

看看翻译在Java中CLRS插入排序算法。

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; 

     System.out.println("i in for loop "+i); 

     for(int k=0; k<a.length;k++) 
     { 
      System.out.print(a[k]+" "); 
     } 
    }