合并排序算法输出错误

Question

我已经非常仔细地遵循了所有算法步骤，但这仍然总是输出错误的答案。我不明白为什么。我认为导致这种情况的合并算法有问题，但无法查明是什么。请帮忙。另外，如果有任何可以改进代码的地方，请提出建议。

谢谢

输入 - {5,6,1,8,9,7}

输出 - {1,0,7,0,9,7}

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

void mergeSort(int array[],int length);
void merge(int *leftArray,int *rightArray,int *array);

void main()
{

    int array[] = {5,6,1,8,9,7};
    int length_of_array;

    length_of_array = sizeof(array) / sizeof(array[0]);

    mergeSort(array,length_of_array);

    int i;

    for(i=0;i<length_of_array;i++)
    {
        printf("%d->",array[i]);
    }
}

void mergeSort(int array[],int length)
{

    if(length <  2)
        return;


    int mid;
    int i;

    mid = length/2;

    int *leftArray, *rightArray;

    leftArray = (int*)malloc(mid*sizeof(int));
    rightArray = (int*)malloc((length-mid)*sizeof(int));

    for(i=0;i<mid;i++)
        leftArray[i] = array[i];

    for(i=mid;i<length;i++)
        rightArray[i-mid] = array[i];


    mergeSort(leftArray, mid);
    mergeSort(rightArray, length-mid);

    merge(leftArray,rightArray,array);

}

void merge(int *leftArray,int *rightArray,int *array)
{
    int i,j,k;
    i = j = k = 0;

    int leftSize = sizeof(leftArray)/sizeof(leftArray[0]);
    int rightSize = sizeof(rightArray)/sizeof(rightArray[0]);

    while(i < leftSize && j < rightSize)
    {
        if(leftArray[i]<rightArray[j])
        {
            array[k] = leftArray[i];
            k = k + 1;
            i = i + 1;
        }
        else
        {
            array[k] = rightArray[j];
            k = k + 1;
            j = j + 1;
        }

    }

    while(i<leftSize)
    {
        array[k] = leftArray[i];
        k = k + 1;
        i = i + 1;

    }

    while(j<rightSize)
    {
        array[k]  = rightArray[j];
        k = k + 1;
        j = j + 1;

    }

}

Answer 1

正如@molbdnilo 所评论的，您无法从指针参数中获取数组的大小。所以merge需要取左右数组的长度以及指向它们的指针。

问题在于 C 中的数组不是 'complete' 数据类型，而只是一种方便的语法。在您的 merge 函数中，参数 int *leftArray 正是它所说的 - 一个指向整数的指针。所以 sizeof 会告诉你指针的大小。在您的 main 函数中，已知 array 是一个数组，并且它的长度是已知的（从给定的初始值），因此 sizeof 可以给出分配给该数组的实际内存大小多变的。但是这个大小没有存储在变量的任何地方，所以它没有传递到 merge - 唯一传递的是指向内存块的指针。

此外，虽然在这种情况下不会给您带来问题，但您应该free使用您 malloc 的 leftArray 和 rightArray 指针.这样您就可以在实际应用程序中使用您的排序功能而不会泄漏内存。

合并排序算法输出错误

Wrong output in Merge Sort Algorithm

c

algorithm

mergesort