c - C 中的递归合并排序和内存分配

Question

尝试在 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 位。

Answer 1

我的猜测是问题出在:

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 的免费工具。