合併排序給我無效輸出（Turbo C++）

Question

這裏是我的簡單邏輯合併排序Turbo C++。我無法弄清邏輯中的錯誤。我從算法寫的。請告訴我我哪裏錯了。謝謝 ！ 邏輯很簡單，請不要更改邏輯或插入指針。我正在獲得某種垃圾值。在輸入5個數字時，我得到5個隨機值（可能是垃圾）。

#include<iostream.h> 
#include<conio.h> 
void merge(int A[], int p,int q, int r) 
{ 
    int n1=q-p+1; 
    int n2=r-q; 
    int i,j,L[50],R[50]; 
    for(i=0;i<n1;i++) 
    L[i]=A[p+i]; 
    for(j=0;j<n2;j++) 
    R[j]=A[q+j+1]; 
    L[n1+1]=6500; 
    R[n2+1]=6500; 
    i=0;j=0; 
    for(int k=p;k<r;k++) 
    { if(L[i]<=R[j]) 
     { 
      A[k]=L[i]; 
      i++; 
     } 
     else 
     { 
     A[k]=R[j]; 
     j++; 
     } 
    } 
} 

void merge_sort(int A[],int p, int r) 
{ 
    if(p<r) 
    { 
     int q=(p+r)/2; 
     merge_sort(A,p,q); 
     merge_sort(A,q+1,r); 
     merge(A,p,q,r); 
    } 
} 

void main() 
{ 
    clrscr(); 
    int A[5]; 
    cout<<"Enter the elements"<<endl; 
    for(int i=0;i<5;i++) 
     cin>>A[i]; 
    merge_sort(A,0,4); 
    for(i=0;i<5;i++) 
     cout<<A[i]<<" "; 
    getch(); 
} 

Answer 1

修復或清除在評論中指出：

void merge(int A[], int p,int q, int r) 
{ 
    int n1=q-p+1; 
    int n2=r-q; 
    int i,j,L[50],R[50]; 
    for(i=0;i<n1;i++) 
     L[i]=A[p+i];  // indent 
    for(j=0;j<n2;j++) 
     R[j]=A[q+j+1]; 
    L[n1]=6500;    // fix 
    R[n2]=6500;    // fix 
    i=0;j=0; 
    for(int k=p;k<=r;k++) // fix 
    { if(L[i]<=R[j]) 
     { 
      A[k]=L[i]; 
      i++; 
     } 
     else 
     { 
      A[k]=R[j];  // indent 
      j++;   // indent 
     } 
    } 
} 

Answer 2

有似乎是在你對變量的merge功能初始循環值i和j斷言的一個問題。在初始循環之後，i的值等於n1的值，因此將L[n1+1]設置爲值會留下L[n1]的空位，該空位將是未初始化的值。 R[n2+1]也是如此，它會在R[n2]處留下間隙，嘗試從兩者中刪除+1。

添加簡單的打印輸出到所述merge功能表明它被稱爲在我的例子4倍傳入數5,4，3，2和1：

merge called with: p: 0, q: 0, r: 1 
merge called with: p: 0, q: 1, r: 2 
merge called with: p: 3, q: 3, r: 4 
merge called with: p: 0, q: 2, r: 4 

進一步在此之後是固定你不是在切換數值，而只是複製它們，例如你循環遍歷數字列表，例如：5,4,3,2,1。第一次循環比較前兩個數字：

您正確地發現4小於5，因此您在第一個位置插入4，然後繼續。該列表現在看起來像這樣：4，4，3，2，1。5已被刪除。

下一迭代merge被調用，你現在發現，圖3是小於4，且因此集的第一數目爲3（R[0]），而第二個數字爲4（L[0]）。

它繼續和結果可以看到下面：

merge called with: p: 0, q: 0, r: 1 
    Building L[0] value: 5 
    Building R[0] value: 4 
    Setting A[0] to 4 R[0] 
merge called with: p: 0, q: 1, r: 2 
    Building L[0] value: 4 
    Building L[1] value: 4 
    Building R[0] value: 3 
    Setting A[0] to 3 R[0] 
    Setting A[1] to 4 L[0] 
merge called with: p: 3, q: 3, r: 4 
    Building L[0] value: 2 
    Building R[0] value: 1 
    Setting A[3] to 1 R[0] 
merge called with: p: 0, q: 2, r: 4 
    Building L[0] value: 3 
    Building L[1] value: 4 
    Building L[2] value: 3 
    Building R[0] value: 1 
    Building R[1] value: 1 
    Setting A[0] to 1 R[0] 
    Setting A[1] to 1 R[1] 
    Setting A[2] to 3 L[0] 
    Setting A[3] to 4 L[1] 

1 1 3 4 1 

開始建設該消息是從線：

for(i=0;i<n1;i++) 
    L[i]=A[p+i]; 

和

for(j=0;j<n2;j++) 
    R[j]=A[q+j+1]; 

爲什麼讓這一切通過使用L和R陣列而不是si更復雜mply直接交換A的值？