我需要帮助解决我的 MergeSort 和 Merge 代码问题
I need help troubleshooting my code for MergeSort and Merge
所以我一直在为一个算法项目研究 MergeSort,但是在获取代码对数组进行排序时,我 运行 遇到了各种问题。每当我生成一个字符串并将其放入 MergeSort 时,它似乎完全一样。我需要一些帮助来找出我的代码中的错误所在,为什么会给我这个错误,以及一个简单但很好解释的解决方案。
这是我过去尝试过的方法:
- 我尝试使用 return
arr[0]
而不是 arr
,但它抛出一个错误,无法从 int
转换为 int[]
.
- 我查看了我的合并 class,那里似乎一切正常。
- 我和我的老师讨论过这个问题,他说一切看起来都很好,但我知道一定是哪里出了问题。
- 我已经尝试删除
return merge(arr1, arr2)
,但系统抛出一个错误,告诉我我必须 return 一些东西。
- 我试过单独打印数组,但它仍然没有显示任何变化,并且与原始字符串完全相同。
合并方法:
private static int[] merge(int[] a, int[] b)
{
int[] c = new int[a.length + b.length];
int counterA = 0;
int counterB = 0;
int counterC = 0;
while (counterA != a.length && counterB != b.length)
{
if (a[counterA] < b[counterB])
{
c[counterC] = a[counterA];
counterA++;
counterC++;
}
else
{
c[counterC] = b[counterB];
counterB++;
counterC++;
}
}
while (counterB == b.length && counterA != a.length)
{
c[counterC] = a[counterA];
counterA++;
counterC++;
}
while (counterA == a.length && counterB != b.length)
{
c[counterC] = b[counterB];
counterB++;
counterC++;
}
return c;
}
MergeSort 方法:
public static int[] mergeSort(int[] arr)
{
if (arr.length == 1)
{
return arr[0];
}
int[] arr1 = new int[arr.length / 2];
int[] arr2 = new int[arr.length - arr1.length];
for (int i = 0; i < arr1.length; i++)
{
arr1[i] = arr[i];
}
for (int i = 0; i < arr2.length; i++)
{
arr2[i] = arr[i + arr1.length];
}
arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);
return merge(arr1, arr2);
}
因为数组是 运行domly 生成的,例如:
9, 1, 7, 5, 7, 2, 2, 9, 8, 9
预期的结果应该是这样的:
1, 2, 2, 5, 7, 7, 8, 9, 9, 9
但是,输出是这样的(数组未更改):
9, 1, 7, 5, 7, 2, 2, 9, 8, 9
你的代码没有按照写的那样编译。在mergeSort
中,如果数组长度等于1,则应该return arr
。进行此更改后,您的代码可以正常工作。
但是,我们可以对您的代码进行一些小改动,使其更简洁。请注意,对于 merge
中的最后一个 while 循环,检查 counterA == a.length
将始终为真。因此,我们可以将其删除。此外,可以在访问数组时增加计数器。结合这些建议,可以为您的 merge
方法生成以下代码:
private static int[] merge(int[] a, int[] b)
{
int[] c = new int[a.length + b.length];
int counterA = 0;
int counterB = 0;
int counterC = 0;
while(counterA != a.length && counterB != b.length)
{
if(a[counterA] < b[counterB])
c[counterC++] = a[counterA++];
else
c[counterC++] = b[counterB++];
}
while(counterB == b.length && counterA != a.length)
c[counterC++] = a[counterA++];
while(counterB != b.length)
c[counterC++] = b[counterB++];
return c;
}
我在代码中看到的唯一问题是 return arr[0];
而不是 mergeSort 中的 return arr;
或 return new int[]{arr[0]};
。
除此之外,代码按预期工作。
如果您没有看到正确的输出,您可能没有正确使用输出。
这是我如何测试它的示例。
public static void main(String[] args) {
int[] input = new int[]{9, 1, 7, 5, 7, 2, 2, 9, 8, 9};
int[] output = mergeSort(input);
}
您的代码中有 2 个问题:
- 你return一个数组元素
arr[0]
而不是数组本身arr
- 你不处理
arr.length == 0
的情况。它也应该 return arr
。
注意代码可以简化:
- 您可以在复制值时对索引值使用
++
运算符,
- 您应该删除第二个和第三个
while
循环中的冗余测试。
这是一个改进版本:
private static int[] merge(int[] a, int[] b)
{
int[] c = new int[a.length + b.length];
int counterA = 0;
int counterB = 0;
int counterC = 0;
while (counterA != a.length && counterB != b.length)
{
if (a[counterA] <= b[counterB])
c[counterC++] = a[counterA++];
else
c[counterC++] = b[counterB++];
}
while (counterA != a.length)
c[counterC++] = a[counterA++];
while (counterB != b.length)
c[counterC++] = b[counterB++];
return c;
}
public static int[] mergeSort(int[] arr)
{
if (arr.length < 2)
return arr;
int[] arr1 = new int[arr.length / 2];
int[] arr2 = new int[arr.length - arr1.length];
for (int i = 0; i < arr1.length; i++)
arr1[i] = arr[i];
for (int i = 0; i < arr2.length; i++)
arr2[i] = arr[i + arr1.length];
arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);
return merge(arr1, arr2);
}
所以我一直在为一个算法项目研究 MergeSort,但是在获取代码对数组进行排序时,我 运行 遇到了各种问题。每当我生成一个字符串并将其放入 MergeSort 时,它似乎完全一样。我需要一些帮助来找出我的代码中的错误所在,为什么会给我这个错误,以及一个简单但很好解释的解决方案。
这是我过去尝试过的方法:
- 我尝试使用 return
arr[0]
而不是arr
,但它抛出一个错误,无法从int
转换为int[]
. - 我查看了我的合并 class,那里似乎一切正常。
- 我和我的老师讨论过这个问题,他说一切看起来都很好,但我知道一定是哪里出了问题。
- 我已经尝试删除
return merge(arr1, arr2)
,但系统抛出一个错误,告诉我我必须 return 一些东西。 - 我试过单独打印数组,但它仍然没有显示任何变化,并且与原始字符串完全相同。
合并方法:
private static int[] merge(int[] a, int[] b)
{
int[] c = new int[a.length + b.length];
int counterA = 0;
int counterB = 0;
int counterC = 0;
while (counterA != a.length && counterB != b.length)
{
if (a[counterA] < b[counterB])
{
c[counterC] = a[counterA];
counterA++;
counterC++;
}
else
{
c[counterC] = b[counterB];
counterB++;
counterC++;
}
}
while (counterB == b.length && counterA != a.length)
{
c[counterC] = a[counterA];
counterA++;
counterC++;
}
while (counterA == a.length && counterB != b.length)
{
c[counterC] = b[counterB];
counterB++;
counterC++;
}
return c;
}
MergeSort 方法:
public static int[] mergeSort(int[] arr)
{
if (arr.length == 1)
{
return arr[0];
}
int[] arr1 = new int[arr.length / 2];
int[] arr2 = new int[arr.length - arr1.length];
for (int i = 0; i < arr1.length; i++)
{
arr1[i] = arr[i];
}
for (int i = 0; i < arr2.length; i++)
{
arr2[i] = arr[i + arr1.length];
}
arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);
return merge(arr1, arr2);
}
因为数组是 运行domly 生成的,例如:
9, 1, 7, 5, 7, 2, 2, 9, 8, 9
预期的结果应该是这样的:
1, 2, 2, 5, 7, 7, 8, 9, 9, 9
但是,输出是这样的(数组未更改):
9, 1, 7, 5, 7, 2, 2, 9, 8, 9
你的代码没有按照写的那样编译。在mergeSort
中,如果数组长度等于1,则应该return arr
。进行此更改后,您的代码可以正常工作。
但是,我们可以对您的代码进行一些小改动,使其更简洁。请注意,对于 merge
中的最后一个 while 循环,检查 counterA == a.length
将始终为真。因此,我们可以将其删除。此外,可以在访问数组时增加计数器。结合这些建议,可以为您的 merge
方法生成以下代码:
private static int[] merge(int[] a, int[] b)
{
int[] c = new int[a.length + b.length];
int counterA = 0;
int counterB = 0;
int counterC = 0;
while(counterA != a.length && counterB != b.length)
{
if(a[counterA] < b[counterB])
c[counterC++] = a[counterA++];
else
c[counterC++] = b[counterB++];
}
while(counterB == b.length && counterA != a.length)
c[counterC++] = a[counterA++];
while(counterB != b.length)
c[counterC++] = b[counterB++];
return c;
}
我在代码中看到的唯一问题是 return arr[0];
而不是 mergeSort 中的 return arr;
或 return new int[]{arr[0]};
。
除此之外,代码按预期工作。
如果您没有看到正确的输出,您可能没有正确使用输出。
这是我如何测试它的示例。
public static void main(String[] args) {
int[] input = new int[]{9, 1, 7, 5, 7, 2, 2, 9, 8, 9};
int[] output = mergeSort(input);
}
您的代码中有 2 个问题:
- 你return一个数组元素
arr[0]
而不是数组本身arr
- 你不处理
arr.length == 0
的情况。它也应该 returnarr
。
注意代码可以简化:
- 您可以在复制值时对索引值使用
++
运算符, - 您应该删除第二个和第三个
while
循环中的冗余测试。
这是一个改进版本:
private static int[] merge(int[] a, int[] b)
{
int[] c = new int[a.length + b.length];
int counterA = 0;
int counterB = 0;
int counterC = 0;
while (counterA != a.length && counterB != b.length)
{
if (a[counterA] <= b[counterB])
c[counterC++] = a[counterA++];
else
c[counterC++] = b[counterB++];
}
while (counterA != a.length)
c[counterC++] = a[counterA++];
while (counterB != b.length)
c[counterC++] = b[counterB++];
return c;
}
public static int[] mergeSort(int[] arr)
{
if (arr.length < 2)
return arr;
int[] arr1 = new int[arr.length / 2];
int[] arr2 = new int[arr.length - arr1.length];
for (int i = 0; i < arr1.length; i++)
arr1[i] = arr[i];
for (int i = 0; i < arr2.length; i++)
arr2[i] = arr[i + arr1.length];
arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);
return merge(arr1, arr2);
}