合并排序的 C 实现，如 Cormen's et al "Introduction to algortithms"not working properly 所示

Question

我正在尝试使用 C 来实现这个合并排序伪代码

我想出了这个

int p = 0, r = SEIZE-1, i, j, k;
int q = (p + r)/2;
int n1 = q-p+1, n2 = r-q;
float A[SEIZE] = { 125.6, 67.2, 3.21, 422, 54, 87 }, L[n1], R[n2];

printf("{ ");
for( k = 0 ; k < SEIZE ; k++ ){
    printf("%.1f ", A[k]);
}
printf(" }\n");

for( i = 0 ; i < n1 ; i++ ){
    L[i] = A[p+i];
}
for( j = 0 ; j < n2 ; j++ ){
    R[j] = A[q+j+1];
}
L[n1] = '\0';
R[n2] = '\0';

i = 0;
j = 0;

for( k = p ; k <= r; k++ ){
    if( L[i] <= R[j] ){
        A[k] = L[i];
        i = i+1;
    }
    else{
        A[k] = R[j];
        j = j+1;
    }
}

printf("{ ");
for( k = 0 ; k < SEIZE ; k++ ){
    printf("%.1f ", A[k]);
}
printf(" }\n");

然而，这会发生

第一组数字是未排序的，第二组应该是已排序的，但如您所见，算法并未对其进行排序；我认为问题源于错误地尝试将书中的 base-1 数组转换为 C 的 base-0，但我不太确定。你能帮我找出问题所在吗？

提前致谢。

Answer 1

您的代码存在一些问题，但到目前为止最大的问题是您认为您的算法应该对数组进行排序。它不是。

“合并”功能只是合并排序的一部分；它的功能是取两个已经排序的子数组——A[p..q−1] 和 A [q..r]，我想，如果我正确地解释了你的伪代码——并将它们合并到一个已经排序的子数组中——A[p..r].

因此，为了测试该函数的实现，您需要为其提供一个数组，该数组的两部分已经排序。

要获得完全排序的数组，您需要完成合并排序的实现。 (您的书可能会在您尚未阅读的页面上为您提供算法的其余部分，或者将其设置为练习。)