問題與歸併排序 - 在C++

Question

實現我下面的歸併排序算法算法導論的2.3.1由Cormen建議。但是，我沒有得到正確的輸出。我確信這裏有一些愚蠢的錯誤，但我現在還沒有弄清楚這一點。任何幫助將非常感激。

例如：對於輸入：5,4,3,2,1，我的輸出是3 1 2 4 5而不是1 2 3 4 5。

假設代碼將被測試爲非常小的數字，並且用999替換哨兵值∞（在算法中）不會影響程序。

這裏是代碼和算法的相應步驟在註釋中。執行此操作是here。

#include <iostream> 
using namespace std; 

void merge(int* A, int p, int q, int r) {  // MERGE(A,p,q,r) 
    int n1 = q-p+1;        // 1. n1 = q-p+1 
    int n2 = r-q;        // 2. n2 = r-q 

    int i,j,k; 
    int *L=new int[n1+1], *R = new int[n2+1]; // 3. let L[1...n1+1] and R[1..n2+1] be new arrays 

    for(i=0; i<n1; i++)       // 4. for i = 1 to n1 
     L[i]=A[p+i];       // 5. L[i] = A[p+i-1] 
     //the modification in above line is deliberately done to avoid IndexOutOfBounds when p=i=0 and is not because I forgot to subtract 1    
    for(j=0; j<n2;j++)       // 6. for j = 1 to n2 
     R[j]=A[q+j];       // 7. R[j] = A[q+j] 

    L[n1]=999; //sentinel      // 8. L[n1+1]= ∞ 
    R[n2]=999; //sentinel      // 9. R[n2+1]= ∞ 
    i=0;          // 10. i = 1 
    j=0;          // 11. j = 1 
    for(k=p; k<r; k++) {      // 12. for k = p to r 
     if(L[i]<=R[j])       // 13. if(L[i]<=R[j]) 
      A[k]=L[i++];      // 14.   A[k] = L[i] 
               // 15.   i = i+1 
     else         // 16. else A[k] = R[j] 
      A[k]=R[j++];      // 17.   j = j+1     
    } 

    delete(L); 
    delete(R); 
} 

void mergeSort(int* a, int p, int r) {  // MERGE-SORT (A,p,r) 
    if(p<r) {         // 1. if p<r 
     int q=(p+r)/2;      // 2. q = (p+r)/2 
     mergeSort(a,p,q);      // 3. MERGE-SORT(A,p,q) 
     mergeSort(a,q+1,r);     // 4. MERGE-SORT(A,q+1,r) 
     merge(a,p,q,r);      // 5. MERGE(A,p,q,r) 
    } 
} 

int main() { 
    int arr[]={5,4,3,2,1}; 
    mergeSort(arr,0,5); 

    for(int i=0; i<5; i++) 
     cout << arr[i]<<" "; 
} 

Answer 1

您對mergeSort遞歸調用建議p和r是子數組的第一個和最後一個項目的索引進行排序：

void mergeSort(int* a, int p, int r) { 
    if(p<r) { 
     int q=(p+r)/2; 
     mergeSort(a,p,q); 
     mergeSort(a,q+1,r); 
     merge(a,p,q,r); 
    } 
} 

如果是這樣，你在main調用是不正確的：

int arr[]={5,4,3,2,1}; 
mergeSort(arr,0,5); 

應該

int arr[]={5,4,3,2,1}; 
mergeSort(arr,0,4); 

接下來，複製下半年是錯誤的：

R[j]=A[q+j]; 

應該是：

R[j]=A[q+1+j]; 

注意p是在左半部分的第一個項目的索引，而q是的索引左半部分的最後一項 - 因此右半部分的第一項索引爲q+1，應該將其作爲+j的基礎。

最後，

for(k=p; k<r; k++) 

應該讀

for(k=p; k<=r; k++) 

- r是右側部分的最後一個項目的索引，所以你需要填寫合併子陣的[r]位置。

編輯
見my answer到Sorting of an array using merge sort。

Answer 2

L[i]=A[p+i];       // 5. L[i] = A[p+i-1] 

我覺得這是你的問題，你不遵循算法在這裏，受了一點（不使用-1，因爲你從0開始）將其固定，但下一個循環，你不」 t +1，當你還沒有在算法中使用相同的數字時？

R[j]=A[q+j];       // 7. R[j] = A[q+j] 

在上一個循環中，您手動更正從0開始，而不是1，但在這裏您沒有。