c++ - 我的 C++ 合并排序代码有什么问题？

Question

我用这个作为参考，但是在得到错误的输出之后，我匹配了代码中的每一行，但我找不到什么问题。我的代码-

#include <iostream>

using namespace std;

void printA(int a[] , int l , int r){
    cout << endl;
    for(int i = l ; i < r ; i++)
        cout<< a[i] <<" ";
    cout<< endl;
}
void merge(int arr[] , int l , int m , int r){
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1];
    int R[n2];
    for(int i=0 ; i < n1 ; i++)
        L[i]=arr[l+i];
    for(int j=0 ; j < n2 ; j++)
        R[j] = arr[m+1+j];
    int i=0, j=0, k=0;
    while(i < n1 && j < n2){
        if(L[i] <= R[j]){
            arr[k] = L[i];
            i++;
        }
        else{
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while(i < n1){
        arr[k] = L[i];
        i++;
        k++;
    }
    while(j < n2){
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[] , int l , int r){
    if(l < r){
        int m = l + (r-l)/2;

        //cout<<"l="<<l<<" m="<<m<<" r="<<r<<" Array";
        //printA(arr,l,r+1);

        mergeSort(arr, l, m);
        mergeSort(arr , m+1 ,r);
        merge(arr, l, m, r);
    }
}

 int main(){
     int n;
     cin >> n;
     int arr[n];
     for(int i=0 ; i < n ; i++)
        cin>> arr[i];
    cout<< "Before: ";
    printA(arr, 0 ,n);
     mergeSort(arr, 0 , n-1);
     cout<<"After";
     printA(arr, 0 ,n);
     return 0;
 }

输入：5

5 4 3 2 1

输出： 之前：

5 4 3 2 1

后

1 2 2 1 5

我无法弄清楚什么是错的，请帮助。

忽略这些 - sa asfasfadgdsg sdg sgdkdjgjngjknrgjk ns

标签： c++mergesort

Answer 1

当您想到 'r' 指向范围之后的第一个元素时，您可以轻松地修复您的程序：

#include <iostream>

using namespace std;

void printA(int a[],int l,int r){
    cout<<endl;
    for(int i=l;i<r;i++)
        cout<<a[i]<<" ";
    cout<<endl;
}
void merge(int arr[],int l,int m,int r){
    int n1 = m-l; // was: int n1 = m-l+1;
    int n2 = r-m;
    int L[n1];
    int R[n2];
    for(int i=0;i<n1;i++)
        L[i]=arr[l+i];

    for(int j=0;j<n2;j++)
        R[j] = arr[m+j]; // was: R[j] = arr[m+1+j];


    int i=0,j=0,k=l; // was: int i=0,j=0,k=0;
    while(i < n1 && j < n2){
        if(L[i]<=R[j]){
            arr[k] = L[i];
            i++;
        }
        else{
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while(i<n1){
        arr[k] = L[i];
        i++;
        k++;
    }
    while(j<n2){
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[],int l,int r){
    if(r - l > 1){ // was: if(l<r){
        int m = l+(r-l)/2;
        //cout<<"l="<<l<<" m="<<m<<" r="<<r<<" Array";
        //printA(arr,l,r+1);
        mergeSort(arr,l,m);
        mergeSort(arr,m,r); // was: mergeSort(arr,m+1,r);
        merge(arr,l,m,r);
    }
}

int main(){
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
        cin>>arr[i];
    cout<<"Before: ";
    printA(arr,0,n);
    mergeSort(arr,0,n); // was: mergeSort(arr,0,n-1);
    cout<<"After";
    printA(arr,0,n);
    return 0;
}