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

Question

我在让我的 mergeSort 算法正常工作时遇到问题。代码如下，但我会简要总结一下我尝试过的内容以及我知道的代码没有错。

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

实际的合并函数采用指向原始数组的指针、指向左侧数组的指针、指向右侧数组的指针以及两个整数值，这两个整数值是每个左侧和右侧数组的大小。然后，它比较 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 + mid + 1]

• 一旦测试失败，merge函数应从左侧或右侧数组中复制其余元素i < leftSize && j < rightSize。

这是一个修改版本：

#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");
}