尝试在 C 中设置合并排序递归函数,我想到了以下内容。
奇怪的是,当数组的大小很小时(大约 10),它工作得很好。对于从 10 到 15 的大小,它有时会错误排序(一个或两个值随机放置在最终数组中),而对于大于 15 的值,它总是会错误地对一个或两个值进行排序,并将一个或两个整数值替换为非常大的负整数。
例如,这个数组:[3] [9] [2] [11] [8] [7] [5] [2]
像这样排序:[2] [2] [3] [-254587859] [7] [8] [11]
--
这是我想出的代码:
主要():
int main(int ac, char **av)
{
int size = atoi(av[1]);
int *array = malloc(size*sizeof(int));
int i;
for (i = 0; i < size; i++) { array[i] = rand() % size; }
merge_sort(array, 0, size-1);
print_array(array, size);
free(array);
return 0;
}
merge_sort() :
void merge_sort(int array[], int beg, int end)
{
int mid = (end + beg) / 2;
if (beg < end)
{
merge_sort(array, beg, mid);
merge_sort(array, mid+1, end);
merge(array, beg, mid, end);
}
return;
}
合并():
void merge(int array[], int beg, int mid, int end)
{
int size_left = mid - beg + 1;
int size_right = end - mid;
int *left = malloc((size_left)*sizeof(int));
int *right = malloc((size_right)*sizeof(int));
int i,j,k;
for (i = 0; i < size_left; i++) { left[i] = array[beg+i]; }
for (j = 0; j < size_right; j++) { right[j] = array[mid+1+j]; }
i = 0; j = 0; for (k = beg; k <= end; k++) { array[k] = (left[i] <= right[j]) ? left[i++] : right[j++]; }
free(left); free(right);
return;
}
我想这是一个内存分配问题,我可以分配大量内存(我试过了,它有效)但这不是重点。你知道那里发生了什么吗?
配置:gcc 4.6.2,Windows 7 64 位。
最佳答案
我的猜测是问题出在:
for (int k = beg; k <= end; k++) {
array[k] = (left[i] <= right[j]) ? left[i++] : right[j++];
}
考虑 left = [1, 2, 3, 4]
和 right = [5, 6, 7, 8]
。 left 将被占用直到 i = 4
然后你尝试引用 left[4]
它超出了数组并且具有未确定的值(在 Java 或其他安全语言中你会得到 IndexOutOfBoundException 或类似的错误 - 在 C 中你是靠自己的,你刚刚读取了一些随机内存)。
您需要确保i
和j
在数组范围内。例如:
for (int k = beg; k <= end; k++) {
if (i == size_left) {
array[k] = right[j++];
} else if (j == size_right) {
array[k] = left[i++];
} else {
array[k] = (left[i] <= right[j]) ? left[i++] : right[j++];
}
}
不幸的是,这样的错误在 C 语言中很常见。有一些免费和商业的工具可以让您找到它们。对于 Linux Valgrind通常使用。 CLang 或 gcc 4.8.0+ AddressSanitizer 也可以帮助解决这个问题——不幸的是,我不知道除此之外还有任何适用于 Windows 的免费工具。
关于c - C 中的递归合并排序和内存分配,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17033316/