合併排序實現不按預期工作

Question

我一直在嘗試實現合併排序;但實現方式不正確 - 輸出包含的值不是原始數組的一部分。我試着將它與其他人的實現（工作）進行比較，但似乎無法找到錯誤。

的代碼是： -

#include <iostream> 

using namespace std; 
void Merge (int A[], int lo, int hi, int mid){ 
    int i = lo; 
    int k = 0; 
    int j = mid+1; 
    int R[hi-lo]; 

    while(i<=mid && j<=hi){ 
     if(A[i]<A[j]){ 
      R[k]=A[i]; 
      cout << A[i] << "; " << A[j] << "  " << i << "  " << j << endl; 
      i++; 
     }else { 
      R[k]=A[j]; 
      cout << A[i] << "; " << A[j] << "  " << i << "  " << j << endl; 
      j++; 
     }k++; 
    } 
    while(i<=lo){ 
     R[k]=R[i]; 
     i++;k++; 
    } 
    while(j<=hi){ 
     R[k]=R[j]; 
     j++;k++; 
    } 
    int count =0; 
    for(i=lo; i<hi; i++){ 
     A[i]=R[count]; 
     count++; 
     cout << count << " ; " << i << "-/-/-/-/-/-/-" << flush; 
    } 
} 
void mergeSort(int A[], int lo, int hi){ 
    //if(hi-lo+1<2)return; 
    if (lo<hi){ 
    int mid = (lo+hi)/2; 
    mergeSort(A, lo, mid); 
    mergeSort(A, mid+1, hi); 
    Merge (A, lo, hi, mid);} 
} 

int main(){ 
    int A[] = {1,5,3,4,8,9,150,7,51,65}; 
    int hi = sizeof(A)/sizeof(int); 
    cout << hi << endl; 
    mergeSort(A,0, hi); 
    cout << endl << endl << endl << endl; 
    for(int i=0; i<=hi; i++){ 
     cout<<A[i]<< "; " << flush; 
    } 
    return 0; 
} 

我試圖尋找類似Q（S），但是沒能找到。

Answer 1

實現的問題是邊界包含和錯誤數組的混合。

首先，看最後2個，而在合併循環，你所做的：R[k]=R[i];當你的意思是R[k]=A[i];

在相同的功能，您的for循環缺少迭代，環路保護應該是i<=hi，而不是i<hi 。

hi的初始化也是錯誤的，因爲您將它初始化爲元素數而不是最後一個索引，您應該減去-1。

另外我不知道你的打印代碼是幹什麼的，所以我評論了並添加了自己的代碼，我發現它更清晰。

我糾正你的代碼如下：

#include <iostream> 

using namespace std; 
void Merge (int A[], int lo, int hi, int mid){ 
    int i = lo; 
    int k = 0; 
    int j = mid+1; 
    int R[hi-lo]; 

    cout << "input" << endl; 
    for(int i=lo; i<=mid; i++) 
     cout << A[i] << " "; 
    cout << endl; 
    for(int i=mid+1; i<=hi; i++) 
     cout << A[i] << " "; 

    cout << endl; 

    while(i<=mid && j<=hi){ 
     if(A[i]<A[j]){ 
      R[k]=A[i]; 
      //cout << A[i] << "; " << A[j] << "  " << i << "  " << j << endl; 
      i++; 
     }else { 
      R[k]=A[j]; 
      //cout << A[i] << "; " << A[j] << "  " << i << "  " << j << endl; 
      j++; 
     }k++; 
    } 
    while(i<=mid){ 
     R[k]=A[i]; 
     i++;k++; 
    } 
    while(j<=hi){ 
     R[k]=A[j]; 
     j++;k++; 
    } 
    int count =0; 
    for(i=lo; i<=hi; i++){ 
     A[i]=R[count]; 
     count++; 
     //cout << count << " ; " << i << "-/-/-/-/-/-/-" << flush; 
    } 

    cout << "output:" << endl; 
    for(int i=lo; i<=hi; i++) 
     cout << A[i] << " "; 
    cout << endl; 
} 
void mergeSort(int A[], int lo, int hi){ 
    //if(hi-lo+1<2)return; 
    if (lo<hi){ 
    int mid = (lo+hi)/2; 
    mergeSort(A, lo, mid); 
    mergeSort(A, mid+1, hi); 
    Merge (A, lo, hi, mid);} 
} 

int main(){ 
    int A[] = {1,5,3,4,8,9,150,7,51,65}; 
    int hi = sizeof(A)/sizeof(int) -1; 
    cout << hi << endl; 
    mergeSort(A,0, hi); 
    cout << endl << endl << endl << endl; 
    for(int i=0; i<=hi; i++){ 
     cout<<A[i]<< "; " << flush; 
    } 
    return 0; 
}