合并排序的实现问题

Question

我在算法简介，第三版中使用了相同的算法，但效果不是很好，它只对数组中的前 4 个数字进行排序。

代码：

#include <stdio.h>

void sortArr(int *nums, int arrSize) {
    // nums[start...end]
    // nums[start...mid]  n1
    // nums[mid+1...end]  n2
    int start, mid, end;
    start = 0;
    end = arrSize-1;
    mid = (end + start) / 2;
    int n1, n2;
    n1 = mid - start + 1;
    n2 = end - mid;
    int l[n1], r[n2];
    for (int i = 0; i < n1; i++) {
        l[i] = nums[start + i];
    }

    for (int i = 0; i < n2; i++) {
        r[i] = nums[mid + 1 + i];
    }

    int i, j;
    i = 0;
    j = 0;
    for (int k = start; k < arrSize; k++) {
        if (l[i] <= r[j]) {
            nums[k] = l[i];
            i++;
        } else {
            nums[k] = r[j];
            j++;
        }
    }
}

Answer 1

您的代码存在相当多的问题，包括您仅实现了书中的 MERGE（MERGESORT 的子例程），并且本书使用了将 +infinity 附加到数组的“一半”的技巧来避免具有处理合并时其中一半用完的代码。您没有包含该技巧（例如：通过将

INT_MAX

附加到 L 和 R 并要求原始数组不包含该值），但您没有用任何内容替换它，以便您的代码可以轻松地读出合并时的边界。

这是基于书中算法的工作版本。与问题中的代码相比，它还避免了使用一次性

malloc

缓冲区在大型输入数组上可能失败的 VLA（可变长度数组），并使用更正确的

size_t

作为数组索引.

代码在合并时在

if

语句中为

li

和

ri

添加了一些额外的测试，这与书中的 +无穷大技巧不同，并且在 C 中效果更好。

如果成功，顶级函数 MERGESORT 返回 1，如果不成功，则返回 0（如果

malloc

失败，则可能会发生这种情况）。断言用于检查有关各种索引和大小的假设 - 仅当代码中存在错误并且可以编译出来时，这些假设才会失败。

它在可配置大小（当前为 1234）的随机数组上运行，并在末尾打印出

ok

或

failed

，具体取决于数组是否实际已排序。 （注意：通常要避免使用

rand

，因为它通常是随机数的供应不足，但这里没问题）。

注意这段代码是精心编写的，但它仍然没有经过很好的测试，所以你可能会发现错误！

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

void MERGE(int *nums, int *buffer, size_t start, size_t mid, size_t end) {
    size_t n1 = mid - start + 1;
    size_t n2 = end - mid;
    assert(n1 > 0);
    assert(n2 > 0);
    memcpy(buffer, nums + start, (end - start + 1) * sizeof(int));
    int *L = buffer;
    int *R = buffer + n1;
    size_t li = 0, ri = 0;
    for (size_t i = start; i <= end; i++ ){
        if (li < n1 && (ri == n2 || L[li] <= R[ri])) {
            assert(li < n1);
            nums[i] = L[li++];
        } else {
            assert(ri < n2);
            nums[i] = R[ri++];
        }
    }
}

void MERGESORT0(int *nums, int *buffer, size_t start, size_t end) {
    if (end == start) return;
    size_t mid = start + (end - start) / 2;
    MERGESORT0(nums, buffer, start, mid);
    MERGESORT0(nums, buffer, mid+1, end);
    MERGE(nums, buffer, start, mid, end);
}

int MERGESORT(int *nums, size_t size) {
    if (size == 0) {
        return 1;
    }
    int *buffer = malloc(sizeof(int) * size);
    if (!buffer) return 0;
    MERGESORT0(nums, buffer, 0, size-1);
    free(buffer);
    return 1;
}

#define N 1234
int main(){
    int arr[N];
    for (size_t i = 0; i < N; i++) {
        arr[i] = rand();
    }
    size_t arrsize = sizeof(arr)/sizeof(arr[0]);
    printf("before sorting: \n");
    for(size_t i=0; i<arrsize; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
    if (!MERGESORT(arr, arrsize)) {
        printf("failed\n");
        exit(1);
    }
    printf("after sorting: \n");
    int failed = 0;
    for(size_t i=0; i<arrsize; i++){
        if (i > 0 && arr[i] < arr[i-1]) failed = 1;
        printf("%d ", arr[i]);
    }
    printf("\n");
    printf("%s\n", failed ? "failed" : "ok");
    return 0;
}

Answer 2

将此打印命令添加到最终循环：

printf("%d %d %d\n", k, i, j);

n1 = n2 = 4

，因此两个数组的值最多只能到索引 3。然而，在最后的循环中，您从 0 到 6 运行

i

。这是行不通的。

您可以添加更多打印命令，用笔和纸运行算法，并希望找到出错的地方。