c - 如何调试合并排序？

Question

我知道什么是合并排序并且我之前已经执行过它。但通常当我尝试这样做时，我几乎从未得到想要的答案。据我猜测，我在存储最终排序的数组时遇到了麻烦。

如何调试这个问题以及调试任何类似递归问题的方法是什么？

 #include<stdio.h>

void merge(int arr[],int p,int q,int r)
{
    int n1= q-p+1;//1st half
    int n2= r-(q+1)+1;//2nd half
    int arr2[100];
    int n=p;

    int ar1[n1],ar2[n2];
    for(int i=p;i<=q;i++)
    {
        ar1[i]=arr[p+i];
    }
    for(int i=q+1;i<=r;i++)
    {
        ar1[i]=arr[p+i];
    }
    int i,j;

    for(i=0,j=0;i<n1&&j<n2;)
    {
        if(ar2[j]<ar1[i]){arr2[n]=ar2[j];j++;}

        else {arr2[n]=ar1[i];i++;}

        n++;
}

while (i<=n1)
{
    arr[n]=ar1[i];
    n++;
}
while (j<=n2)
{


    arr[n]=ar2[j];
        n++;
    }
    if(p==0&&r==9)
    {
        for(int i=0;i<=9;i++)
        {
            printf("%d",arr2[i]);
        }
    }
}
void mergesort(int arr[], int p, int r)
{
    if(p<r)
    {
        int q=(p+r)/2;
        mergesort(arr,p,q);
        mergesort(arr,q+1,r);
        merge(arr,p,q,r);
    }   
}


int main()
{
    int arr[]={2,4,13,4,0,23,54,12,6,9};
    mergesort(arr,0,9);
    for(int i=0;i<=9;i++)
    {
        printf("%d ",arr[i]);
    }

    return 0;
}

Answer 1

我的总体评论是“整洁很重要”，而您的 merge() 代码一团糟。您没有看到您从 ar2 中取出了一些东西，但从未将任何东西放入其中吗？另外，不需要 arr2，因此请将其删除。而且你的索引都是错误的。

你的缩进毫无值(value)，你期望如何调试任何东西？ (除了让 SO 上的人为你做这件事之外。)思考每一行:它是否建立在前面的陈述之上？它是否建立在以下陈述的基础上？考虑每个索引:它从哪里开始；应该在哪里结束？您的代码未扭曲:

#include <stdio.h>

void merge(int array[], int p, int q, int r)
{
    int n1 = q - p + 1; // 1st half
    int n2 = r - (q + 1) + 1; // 2nd half

    int ar1[n1], ar2[n2];

    for (int i = p, j = 0; j < n1; i++, j++)
    {
        ar1[j] = array[i];
    }

    for (int i = q + 1, j = 0; j < n2; i++, j++)
    {
        ar2[j] = array[i];
    }

    int i = 0, j = 0, n = p;

    for (; i < n1 && j < n2; n++)
    {
        if (ar2[j] < ar1[i])
        {
            array[n] = ar2[j++];
        } else {
            array[n] = ar1[i++];
        }
    }

    while (i < n1)
    {
        array[n++] = ar1[i++];
    }

    while (j < n2)
    {
        array[n++] = ar2[j++];
    }
}

void mergesort(int array[], int p, int r)
{
    if (p < r)
    {
        int q = (p + r) / 2;
        mergesort(array, p, q);
        mergesort(array, q + 1, r);
        merge(array, p, q, r);
    }   
}

int main()
{
    int array[] = {2, 4, 13, 4, 0, 23, 54, 12, 6, 9};

    int length = sizeof(array) / sizeof(int);

    mergesort(array, 0, length - 1);

    for (int i = 0; i < length; i++)
    {
        printf("%d ", array[i]);
    }

    printf("\n");

    return 0;
}