0

尝试在 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;

}

合并排序（）：

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 位。

4

3 回答 3

3

我的猜测是问题出在：

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]。左边将被占用，直到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 的免费工具。

于 2013-06-10T21:55:17.943 回答
3

问题是你的合并：

array[k] = (left[i] <= right[j]) ? left[i++] : right[j++];

这不考虑i或j可能超过数组末尾的事实。您需要实际检查：

i = j = 0;
k = beg;

// Merge both
while( i < size_left && j < size_right ) {
    array[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
}

// Merge leftovers
while( i < size_left ) array[k++] = left[i++];
while( j < size_right ) array[k++] = left[j++];
于 2013-06-10T21:55:23.027 回答
0

好的，谢谢 Maciej 和 Paddy，您在我对“合并”步骤的推理中指出了如此大的失败。这正是 C 语言的有趣之处，即您“靠自己”的感觉，如果您做出错误的举动，没有任何指导方针可以阻止您。

根据您的改进，以下是我的结尾：

for (k = beg; k <= end; k++) {
    array[k] = (left[i] <= right[j]) ?
        (i == size_left) ? right[j++] : left[i++] :
        (j == size_right) ? left[i++] : right[j++];
}
于 2013-06-11T09:48:19.543 回答