C语言 我写了一个合并排序的代码(从clrs的书)，但没有得到输出

Question

我参考了cls的《Introduction to Algorithms》并用C语言编写了一个程序。虽然我用笔和纸手工检查了它，但代码似乎是正确的，然后我也没有得到正确的输出。

输出如下:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
void merge(int array[], int start, int middle, int end) {
int n1 = middle - start + 1;
int n2 = end - start;
int i;
int leftarray[n1 + 1], rightarray[n2 + 1];
for (i = 0; i < n1; i++) {
leftarray[i] = array[start + i];
}
for (int j = 0; i < n2; i++) {
rightarray[j] = array[middle + j + 1];
}
leftarray[n1 + 1] = 1000000;
rightarray[n2 + 1] = 1000000;

int k, j = 0;
i = 0;
for (k = start; k <= end; k++) {
if (leftarray[i] > rightarray[j]) {
array[k] = rightarray[j];
j++;
} else {
array[k] = leftarray[i];
i++;
}
}
}
void mergeSort(int array[], int start, int end) {
if (start < end) {
int middle = (start + end) / 2;
mergeSort(array, start, middle);
mergeSort(array, middle + 1, end);
merge(array, start, middle, end);   
}
}
void sorting(int array[], int length) {
int i;
for (i = 0; i < length; i++) {
printf("%d ", array[i]);
}   
}
int main() {
int noOfelements;
scanf("%d", &noOfelements);
int array[noOfelements];
for (int i = 0; i < noOfelements; i++) {
scanf("%d", &array[i]);
}
printf("Before Sorting: ");
sorting(array, noOfelements);
mergeSort(array, 0, noOfelements - 1);
printf("After Sorting: ");
sorting(array, noOfelements);
return 0;   
}

以上程序的输出:

5
5 4 3 2 1 
Before Sorting: 5 4 3 2 1 After Sorting: 2 0 5 0 32

Answer 1

尽管算法导论由Thomas H . Cormen, Charles E . Leiserson, Ronald L . Rivest和Clifford Stein编写的被认为是一本优秀的教科书，但您实现的算法有几个缺点:

• 它使用哨兵值的概念，在要合并的数组末尾设置的值，据说比任何现有的值都大，希望能简化合并过程。实际上，没有这样的值，如果有的话，为什么它们不应该作为常规值出现在数组中呢?
• 使用end作为数组中最后一个元素的索引:使用end作为数组之外的第一个元素的索引会简单得多，从而消除了混淆+1/-1调整的需要并允许空数组。
• 你使用int middle = (start + end) / 2;,start和end的大值可能溢出，虽然你的实现的其他部分会失败，如果你尝试和排序这么大的数组。写int middle = start + (end - start) / 2;
更安全

您的代码失败是因为您将哨兵值设置得太远了。你应该写:

leftarray[n1] = 1000000;
rightarray[n2] = 1000000;

这里有一个更好的方法:

#include <stdio.h>
void merge(int array[], int start, int middle, int end) {
int n1 = middle - start;
int i, j, k;
// save the elements from the left half, no need to save the right half
int leftarray[n1];
for (i = 0; i < n1; i++) {
leftarray[i] = array[start + i];
}

for (i = 0, j = middle, k = start; i < n1; k++) {
if (j >= end || leftarray[i] <= array[j]) {
array[k] = leftarray[i];
i++;
} else {
array[k] = array[j];
j++;
}
}
}
void mergeSort(int array[], int start, int end) {
if (end - start >= 2) {
int middle = start + (end - start) / 2;
if (middle - start > 100000) {
// avoid stack overflow: allocate at most 100k ints for `leftarray`
middle = start + 100000;
}
mergeSort(array, start, middle);
mergeSort(array, middle, end);
merge(array, start, middle, end);   
}
}
void print_array(const char *prefix, const int array[], int length) {
printf("%s:", prefix);
for (int i = 0; i < length; i++) {
printf(" %d", array[i]);
}
printf("n");
}
int main() {
int noOfelements;
if (scanf("%d", &noOfelements) != 1 || noOfelements < 0)
return 1;
int array[noOfelements];
for (int i = 0; i < noOfelements; i++) {
if (scanf("%d", &array[i]) != 1)
return 1;
}
print_array("Before Sorting", array, noOfelements);
mergeSort(array, 0, noOfelements);
print_array("After Sorting", array, noOfelements);
return 0;   
}