合并排序不打印排序数组

Question

我的代码在打印未排序的数组后终止，并且在 ideone 上出现运行时错误，我无法在其中找到错误。代码在函数中的第一个 mergesort 之前工作正常，但之后在不执行 merge function 的情况下终止。我尝试过更改数组大小，但到目前为止没有任何效果。任何帮助将不胜感激。

#include<stdio.h>
#include<math.h>
void Merge(int arr[],int,int,int,int);

void printArray(int *arr,int n)
{
    for (int i = 0; i < n; i++)
    {
        printf("%d",arr[i]);
        printf(" ");
    }
    printf("\n");
}

void MergeSort(int arr[],int low,int high)
{
    
    int mid;
    if(low<high)
    {
       
        mid = ceil((low+high)/2);
      
        MergeSort(arr,low,mid-1);
        
        MergeSort(arr,mid,high);
     
        Merge(arr,low,mid-1,mid,high);
    }
}

void Merge(int arr[],int low,int mid1,int mid2, int high)
{
    
    int i,c,j;

    c = low;
    i = low;
    j  = mid2;

    int Temp[high-low+1];
    while(i <= mid1 && j<= high)
    {
        if(arr[i]<arr[j])
        {
            Temp[c] = arr[i];
            i++;
            c++;
        }
        else
        {
            Temp[c] = arr[j];
            j++;
            c++;
        }
    }    

    while(i<=mid1)
    {
        Temp[c] = arr[i]; 
        i++;
        c++;          
    }
    while(j<=high)
    {
        Temp[c] = arr[j]; 
        j++;
        c++;
    }
    
    for(int k=0;k<=high;k++)
    {
        arr[k] = Temp[k];
    }    
    
}

int main(void)
{
    int arr[] = {3,5,2,13,12,3,2,13,45};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("unsorted array: \n");
    printArray(arr,n);
    MergeSort(arr,0,n-1);
    printf("sorted array: \n");
    printArray(arr,n);
    return 0;

}

Answer 1

有几个问题：

ceil 没有用，因为 / 将执行整数除法，因此已经舍入 down
与此相关，您不应该在接下来的递归调用中使用mid-1和mid作为参数，而是mid和mid+1。 Merge.
您访问Temp的方式不对。您分配从 0 到 high-low 的条目，但以 c 的值开始您的访问，即 low。您应该从索引 0 开始。
在最后一个循环中，k 从 0 运行到 high，但迭代次数过多。它应该从 low 开始，然后对 Temp 的索引访问应该再次使用 k-low 作为索引进行调整。

这是更正后的代码：

void MergeSort(int arr[],int low,int high)
{
    int mid;
    if(low<high)
    {
        mid = (low+high)/2; // <--
        MergeSort(arr,low,mid); // <--
        MergeSort(arr,mid+1,high); // <--     
        Merge(arr,low,mid,mid+1,high); // <--
     }
}

void Merge(int arr[],int low,int mid1,int mid2, int high)
{   
    int i,c,j;
    c = 0; // <--
    i = low;
    j  = mid2;

    int Temp[high-low+1];
    while(i <= mid1 && j<= high)
    {
        if(arr[i]<arr[j])
        {
            Temp[c] = arr[i];
            i++;
            c++;
        }
        else
        {
            Temp[c] = arr[j];
            j++;
            c++;
        }
    }    
    while(i<=mid1)
    {
        Temp[c] = arr[i]; 
        i++;
        c++;          
    }
    while(j<=high)
    {
        Temp[c] = arr[j]; 
        j++;
        c++;
    }
    for(int k=low;k<=high;k++) // <--
    {
        arr[k] = Temp[k-low]; // <--
    }
}

重要说明：我为您调试了代码，但这是您可以自己完成的事情。在使用调试器逐步执行代码时检查变量，并找出意外情况。这需要一些时间，但这是编码人员需要学习的技能。

合并排序不打印排序数组

Merge sort not printing sorted array

c

sorting

algorithm

mergesort

data-structures