c++11 - 我在此合并排序算法代码中遇到运行时错误

Question

我在此代码中遇到运行时错误。此代码用于合并排序算法。我怎样才能找到错误？

此代码使用递归和函数。递归调用函数mergesort来划分数组，直到它的大小减小到1。然后使用merge函数合并多个数组。

 #include <iostream>
    using namespace std;
    void merge(int l[],int size1,int r[],int size2,int input[],int size){
        int i=0,j=0,k=0;
        while(i<size1 && j<size2){
            if(l[i]<=r[j]){
                input[k]=l[i];
                k++;
                i++;
            }
            else{
                input[k]=r[j];
                j++;
            }
            k++;
        }
        while(i<size1){
            input[k]=l[i];
            i++;
            k++;
        }
        while (j<size2){
            input[k]=r[j];
            j++;
            k++;
        }
    }
    void mergesort(int input[],int size){
        if(size<2){
            return;
        }
        int mid= size/2;
        int l[500];
        int r[500];
        for(int i=0;i<mid-1;i++){
            l[i]=input[i];
        }
        for(int j=mid;j<size-1;j++){
            r[j-mid]=input[j];
        }
        mergesort(l,mid);
        mergesort(r,size-mid);
        merge(l,mid,r,size-mid,input,size);
    
    
    }
    
    int main() {
        int n;
        cin>>n;
        int arr[1000];
        for(int i=0;i<n;i++){
            cin>>arr[i];
        }
        mergesort(arr,n);
        for(int j=0;j<n;j++){
            cout<<arr[j]<<" ";
        }
    
    
        return 0;
    }

标签： c++11recursionc++14c++17mergesort

Answer 1

我在您的代码中看到以下错误。

1. for(int i=0;i<mid-1;i++)需要是for(int i=0;i<mid;i++)

2. for(int j=mid;j<size-1;j++)需要是for(int j=mid;j<size;j++)

3. 您的增量k不merge正确。

   循环

   while(i<size1 && j<size2){
      if(l[i]<=r[j]){
         input[k]=l[i];
         k++;
         i++;
      }
      else{
         input[k]=r[j];
         j++;
      }
      k++;
   }
   

   需要是

   while(i<size1 && j<size2){
      if(l[i]<=r[j]){
         input[k]=l[i];
         //  k++; This is an error.
         i++;
      }
      else{
         input[k]=r[j];
         j++;
      }
      k++;
   }