c - Mergesort 在执行时为已排序数组的第一个元素提供垃圾值

Question

我正在使用“算法简介”中描述的算法实现 Mergesort。但是，在每次执行时，我都会得到一个垃圾值作为排序数组的第一个元素。这是它的代码:

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

void mergesort(int a[], int p, int r);

void merge(int a[], int p, int q, int r)
{
    int *left, *right;
    int i,j,k,l,n1,n2;
    n1 = q-p+1;
    n2 = r-q;
    left = malloc(sizeof(int)*(n1+1));
    right = malloc(sizeof(int)*(n2+1));
    for ( i = 0; i < n1; i++) {
        left[i] = a[p+i];
    }
    for ( j = 0; j < n2; j++) {
        right[j] = a[q+j+1];
    }
    left[n1] = INT_MAX;
    right[n2] = INT_MAX;
    i = 0;
    j = 0;
    for ( k = p; k <= r; k++) {
        if (left[i] <= right[j]) {
            a[k] = left[i];
            i++;
        }
        else {
            a[k] = right[j];
            j++;
        }
    }
    free(left);
    free(right);
    return ;
}

int main(int argc, char* argv[])
{
    int i;
    int a[] = {5,2,4,7,1,3,2,6} ;
    mergesort(a,0,sizeof(a)/sizeof(int));
    for ( i = 0; i < sizeof(a)/sizeof(int); i++) {
        printf("%d\n",a[i]);
    }
    return 0;
}

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

Answer 1

看来您没有明确定义归并排序参数的含义。在这里，您的最后一个元素位于数组末尾之后:

mergesort(a,0,sizeof(a)/sizeof(int));

但是在这里，

mergesort(a,p,q);
mergesort(a,q+1,r);

Q 似乎超过了数组中的最后一个元素。如果您的代码遵循第一个，您将忘记实际对值 q 进行排序。如果它跟在第二个之后，您将尝试对数组末尾后一个垃圾值进行排序。