我在让MergeSort在C中工作时遇到了问题

Question

我的合并排序算法无法正常工作。代码在下面，但是我简单总结一下我试过的，我知道的代码没有错的地方。

mergeSort函数将指向数组的指针和数组的大小作为参数。如果数组的大小小于2，它会立即返回。我确信这是有效的，因为我调试了这部分几次。它返回了8次，这是我期望它做的。接下来，创建一个变量mid作为索引来拆分数组。我测试了它，我很有信心mid在所有递归中都是正确的。然后，创建两个数组，第一个数组包含索引0…mid-1中的元素，第二个数组包含索引mid到n中的元素。接下来，计算每个数组的大小。我也测试了这个，大小似乎在所有递归中都是正确的。在左数组和右数组上调用mergeSort，然后调用合并。

实际的合并函数采用指向原始数组的指针、指向左侧数组的指针、指向右侧数组的指针以及两个整数值，这两个整数值是每个左侧和右侧数组的大小。然后，它比较 L 和 R 中的元素，并按顺序将两者中较小的元素复制到 A 中。

然而，我的输出是[2][4][1][6][8][5][3][7]我的预期输出是：[1][2][3][4][5][6][7][8]

我真的不确定为什么代码不起作用。可能我忽略了一些东西，但我一直在尝试解决它一个小时，并认为我会寻求帮助。

如果你花时间回答，或试图回答这个问题，感谢你的时间。我的代码如下:

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

void mergeSort(int *, int);
void merge(int *, int *, int, int *, int);
void print(int *, int);

int main() {
    int A[8] = { 2, 4, 1, 6, 8, 5, 3, 7 };
    int arraySize = sizeof(A) / sizeof(A[0]);
    mergeSort(A, arraySize);
    print(A, arraySize);
}

void mergeSort(int *A, int n) {
    if (n < 2) {
        return;
    }
    int mid = n / 2;
    int L[mid];
    int R[n - mid];
    for (int i = 0; i < mid; i++) {
        L[i] = A[i];
    }
    for (int j = mid; j < n; j++) {
        R[j - mid] = A[j + mid + 1];
    }
    int leftSize = sizeof(L) / sizeof(L[0]);
    int rightSize = sizeof(R) / sizeof(R[0]);
    mergeSort(L, leftSize);
    mergeSort(R, rightSize);
    merge(A, L, leftSize, R, rightSize);
}

void merge(int *A, int *L, int leftSize, int *R, int rightSize) {
    int i, j, k;
    while (i < leftSize && j < rightSize) {
        if (L[i] < R[j]) {
            A[k] = L[i];
            k++;
            i++;
        } else {
            A[k] = R[j];
            k++;
            j++;
        }
    }
}

void print(int *A, int n) {
    for (int i = 0; i < n; i++) {
        printf("[%d] ", A[i]);
    }
    printf("\n");
}

Answer 1

存在多个问题：

>

R的初始化循环不正确：您应该复制A[j]而不是A[j mid1]

＜code＞merge＜/code＞函数应该在测试＜code＞i后从左数组或右数组复制其余元素

以下是修改后的版本：

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

void mergeSort(int *, int);
void merge(int *, int *, int, int *, int);
void print(const int *, int);

int main() {
    int A[8] = { 2, 4, 1, 6, 8, 5, 3, 7 };
    int arraySize = sizeof(A) / sizeof(A[0]);
    mergeSort(A, arraySize);
    print(A, arraySize);
    return 0;
}

void mergeSort(int *A, int n) {
    if (n < 2) {
        return;
    }
    int mid = n / 2;
    int L[mid];
    int R[n - mid];
    for (int i = 0; i < mid; i++) {
        L[i] = A[i];
    }
    for (int j = mid; j < n; j++) {
        R[j - mid] = A[j];
    }
    int leftSize = sizeof(L) / sizeof(L[0]);
    int rightSize = sizeof(R) / sizeof(R[0]);
    mergeSort(L, leftSize);
    mergeSort(R, rightSize);
    merge(A, L, leftSize, R, rightSize);
}

void merge(int *A, int *L, int leftSize, int *R, int rightSize) {
    int i, j, k;
    while (i < leftSize && j < rightSize) {
        if (L[i] <= R[j]) {
            A[k++] = L[i++];
        } else {
            A[k++] = R[j++];
        }
    }
    while (i < leftSize) {
        A[k++] = L[i++];
    }
    while (j < rightSize) {
        A[k++] = R[j++];
    }
}

void print(const int *A, int n) {
    for (int i = 0; i < n; i++) {
        printf("[%d] ", A[i]);
    }
    printf("\n");
}