我在这个C#合并排序算法中做错了什么

Question

对于学校作业，我必须实现mergesort。

我用这个代码来做这个把戏：

static int[] MergeSort(int[] C)
{
int left = 0;
int right = C.Length;
int middle = (left + right) / 2;
int[] A, B;
A = new int[middle];
B = new int[middle];
if (C.Length == 0 || C.Length == 1)
{
return C;
}
else
{
for (int i = left; i < middle; i++)
{
A[i] = C[i];
B[i] = C[middle + i];
}
MergeSort(A);
MergeSort(B);
return Merge(A, B, C);
}
}
static int[] Merge(int[] A, int[] B, int[] C)
{
int i, j, k;
i = j = k = 0;
int n = A.Length;
int m = B.Length;
int c = C.Length;
int middle = C.Length / 2;
while (i < n && j < m)
{
if (A[i] < B[j])
{
C[k] = A[i];
i++;
}
else
{
C[k] = B[j];
j++;
}
k++;
if (i == n)
{
for (int b = i; b < B.Length; b++)
{
C[middle + b] = B[b];
}
}
else
{
for (int a = i; a < A.Length; a++)
{
C[middle + a] = A[a];
}
}
}
return C;
}

不过，它不适用于许多不同的行。我已经调试并检查了约束是否有问题，但似乎找不到问题。

提前感谢！

Answer 1

我发现的第一件事是如何将数组一分为二：

A = new int[middle];
B = new int[middle];

如果长度不均匀，您将遗漏最后一项。你应该有：

A = new int[middle];
B = new int[right - middle];

然后你会为它们使用单独的循环，因为它们的长度可能不同：

for (int i = left; i < middle; i++) {
A[i - left] = C[i];
}
for (int i = middle; i < right; i++) {
B[i - middle] = C[i];
}

Answer 2

除了Guffa答案，您还应该编辑Merge方法的代码，如下所示：

while (i < n && j < m)
{
if (A[i] < B[j])
{
C[k] = A[i];
i++;
}
else
{
C[k] = B[j];
j++;
}
k++;
}
if (i == n)
{
for (int b = j; b < B.Length; b++)
{
C[k++] = B[b];
}
}
else
{
for (int a = i; a < A.Length; a++)
{
C[k++] = A[a];
}
}

虽然循环块应该在k++之后结束，在循环的第一个循环中，你应该用j而不是i初始化b。此外，注意C数组的下一个元素的索引，它是k，而不一定是中间的+a或b。