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

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}
beg - 0
end - 8
mid - 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++];

Answer 2

merge函数错误。以下可能有效。

#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 ( j >= n2 || (i < n1 && 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);
    }
}

int 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]);

    return 0;
}

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

Merge sort is giving garbage value as output

c

sorting

mergesort