c - 合并排序将垃圾值作为输出

Question

我用c编写了以下代码，但以下程序的输出始终是垃圾值数组，我所有输入的整数都在某处丢失，请帮助并告诉我错误是什么以及错误在哪里。谢谢你:)

#include<stdio.h>
#include<malloc.h>

void merge(int a[],int beg,int mid,int end)
{
    int n1=mid-beg+1;
    int n2=end-mid;
    int i=0,j=0,k=0;

    int *p1 = (int*)malloc((n1)*sizeof(int));
    int *p2 = (int*)malloc((n2)*sizeof(int));

    for(i=0;i<n1;i++)
        p1[i]=a[beg+i];

    for(j=0;j<n2;j++)
        p2[j]=a[mid+1+j];
    i=j=0;

    for(k=beg;k<=end;k++)
    {
        if(p1[i]<=p2[j])
        {
            a[k]=p1[i];
            i=i+1;
        }
        else  {
            a[k]=p2[j];
            j=j+1; }
    }
}
void merge_sort(int a[],int beg,int end)
{
    if(beg<end)
    {
        int mid=(beg+end)/2;

        merge_sort(a,beg,mid);
        merge_sort(a,mid+1,end);
        merge(a,beg,mid,end);
    }
}
void main()
{
    printf("Enter Array of size 10:\n");
    int a[10],i;
    for(i=0;i<10;i++)
        scanf("\n%d",&a[i]);

    int n=sizeof a/sizeof a[0];

    merge_sort(a,0,n-1);

    printf("\nSorted array is:\n");
    for(i=0;i<10;i++)
        printf("%d\n",a[i]);

}

Answer 1

您尚未检查以下情况:其中一个数组的所有元素之一已放入结果中，而第二个数组中的某些元素仍未位于正确的位置。

只是为了理解尝试在以下输入上运行merge 过程 -
a - {1,2,3,4,10,11,12,13,14}
乞求 - 0
结束 - 8
中 - 4

在您的 void merge(int a[],int beg,int mid,int end) 函数中，将第三个 for 循环替换为 -

for(k=beg;i<n1 && j<n2;k++)
{
    if(p1[i]<=p2[j])
        a[k]=p1[i++];
    else
        a[k]=p2[j++];
}
while(i<n1)
   a[k++] = p1[i++];
while(j<n2)
   a[k++] = p2[j++];