我用C语言编写了合并排序算法,并已在本地和远程对其进行了编译。我认为源代码中的某些原因导致了平台依赖性。
#include <stdio.h>
#include <limits.h>
#include <math.h>
void merge(int A[], int p, int q, int r) {
int n1 = q-p+1;
int n2 = r-q;
int L[n1];
int R[n2];
for(int i = 0; i < n1; ++i) {
L[i] = A[p+i];
}
for(int j =0; j < n2; ++j) {
R[j] = A[q+j+1];
}
L[n1] = INT_MAX;
R[n2] = INT_MAX;
int i = 0;
int j = 0;
for(int 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;
}
}
}
void merge_recurse(int A[], int p, int r) {
if(p < r) {
int q = floor((p+r)/2);
merge_recurse(A, p, q);
merge_recurse(A, q+1, r);
merge(A, p, q, r);
}
}
void merge_sort(int A[], size_t length) {
merge_recurse(A, 0, (int)length-1);
}
int main()
{
int length = 9;
int A[] = {3, 7, 61, 3, 40, 4, -1, 8, 10};
merge_sort(A, length);
for (int i = 0; i < length; ++i) {
printf("%i, ", A[i]);
}
return 0;
}
当编译online时,返回正确的结果。
-1, 3, 3, 4, 7, 8, 10, 40, 61,
但是,当我在Linux上本地编译源代码时,返回了不正确的结果。
-1, 4, 8, 10, 2147483647, 3, 7, 40, 61
源代码中的什么导致这些不同的结果?
L[n1] = INT_MAX;
写入数组的末尾。声明int L[n1];
创建一个数组,该数组可以从0
索引到n1-1
。没有L[n1]
。 R[n2] = INT_MAX
也是如此;
当代码写到数组的末尾时,它可能以改变代码行为的方式踩在另一个变量上。否则可能没有任何明显的效果。在线编译器恰好以没有发生任何不良情况的方式将变量安排在内存中。它是完全不可预测的,被称为undefined behavior。