合并排序给出不准确的结果

Question

我正在实施 merge sort 并且我已经为它编写了一些代码但是它没有按照给定的算法工作。请任何人让我知道代码中有什么问题。结果它显示了一些垃圾值。 this is the code

输出：给定的数组是： 85 24 63 45 17 31 96 50 6

排序数组为： -1 0 0 3 3 31 1 9 85

#include<stdio.h>
#include<stdlib.h>

void merge(int a[],int left, int middle, int right)
{
    int i,j,k;
    int size1=middle-left+1;
    int size2=right-middle;
    int left_array[size1],right_array[size2];

    for(i=0;i<size1;i++)
    left_array[i]=a[left+i];

    for(j=0;j<size2;j++)
    right_array[i]=a[middle+j+1];

    i=0;
    j=0;
    k=left;

    while(i<size1 && j<size2)
    {
        if(left_array[i]<=right_array[j])
        {
            a[k]=left_array[i];
            i++;
        }
        else
        {
            a[k]=right_array[j];
            j++;
        }
        k++;
    }
    while(i<size1)
    {
        a[k]=left_array[i];
        i++;
        k++;
    }
    while(j<size2)
    {
        a[k]=right_array[j];
        j++;
        k++;
    }
}
void merge_sort(int a[],int left, int right)
{
    if(left<right)
    {
        int middle=left+(right-left)/2;
        merge_sort(a,left,middle);
        merge_sort(a,middle+1,right);
        merge(a,left,middle,right);
    }
}
void printArray(int A[], int size)
{
int i;
for (i=0; i <size; i++)
printf("%d ", A[i]);
printf("\n");
}

int main()
{
    int a[] = {85, 24, 63, 45, 17, 31, 96, 50, 6};
    int a_size = sizeof(a)/sizeof(a[0]);

    printf("Given array is: \n");
    printArray(a, a_size);

    merge_sort(a, 0, a_size - 1);

    printf("\nSorted array is: \n");
    printArray(a, a_size);
    return 0;
}

Answer 1

这里仔细看：

void merge(int a[],int left, int middle, int right)
{
    int i,j,k;
    int size1=middle-left+1;
    int size2=right-middle;
    int left_array[size1],right_array[size2];

    for(i=0;i<size1;i++)
    left_array[i]=a[left+i];

    for(j=0;j<size2;j++)
    right_array[i]=a[middle+j+1];
    //          ^                     This should be j.

    // ...
}

考虑使用 memcpy 而不是一些原始循环。

合并排序给出不准确的结果

Merge sort giving inaccurate results

c

sorting

algorithm

mergesort