C++ 中 MergeSort 程序的错误输出

Question

我正在尝试编写一个给出错误输出的基本合并排序代码。我的输入数组是 {4,2,6,1,9,5,6,78,9,34,74,86,14,3,0} 我得到的输出是 0 1 2 3 4 5 6 9 9 14 74 32696 802952496 1 1 这绝对是错误的，但我找不到代码的错误部分。

Sort 函数将数组一分为二，合并排序到初始数组中。 MergeSort递归划分数组直到只剩下一个元素

#include <iostream>
#include <algorithm>
using namespace std;

void Sort(int *arr,int low,int mid,int high)                          //Sorting algo
{
    int n1=mid-low+1,n2=high-mid;
    int arr1[n1];
    int arr2[n2];
    for(int i=0;i<n1;i++)arr1[i]=arr[i+low];
    for(int j=0;j<n2;j++)arr2[j]=arr[mid+j+1];
    
    int i=0,j=0,it=low;
    while(i<n1 && j<n2)
    {
        if(arr1[i]<=arr2[j])
        {
            arr[it]=arr1[i];i++,it++;
        }
        else 
        {
            arr[it]=arr2[j];j++,it++;
        }
    }
    while(i<n1){
        arr[it]=arr1[i];i++;it++;
    }
    while(j<n2){
        arr[it]=arr2[i];j++;it++;
    }
}

void MergeSort(int* arr,int low,int high)      //Recursive Merge Function
{
    int mid=low+(high-low)/2;
    if(low<high)
    {
        MergeSort(arr,low,mid);
        MergeSort(arr,mid+1,high);
        Sort(arr,low,mid,high);
    }
    
    
}
int main() {
    int arr[]={4,2,6,1,9,5,6,78,011,34,74,86,14,3,0};
    int n=sizeof(arr)/sizeof(arr[0])-1;
    MergeSort(arr,0,n);
    
    for(int a:arr)
    {
        cout<<a<<" ";
    }
    return 0;
}

Answer 1

这里：

while(j<n2){
    arr[it]=arr2[i];j++;it++;
}

应该是：

while(j<n2){
    arr[it]=arr2[j];j++;it++;
}

怎么了？您正在访问索引 i 而不是 j.

注：此类代码：

int n1=mid-low+1,n2=high-mid;
int arr1[n1];
int arr2[n2];
for(int i=0;i<n1;i++)arr1[i]=arr[i+low];
for(int j=0;j<n2;j++)arr2[j]=arr[mid+j+1];

丑，太丑了。请使用空格，它们是免费的！

C++ 中 MergeSort 程序的错误输出

Wrong output of MergeSort program in C++

c++

arrays

mergesort