java - 我需要帮助对 MergeSort 和 Merge 的代码进行故障排除
问题描述
因此,我一直在为算法项目进行 MergeSort 工作,但是在获取对数组进行排序的代码时遇到了各种问题。每当我生成一个字符串并将其放入 MergeSort 时,它似乎完全一样。我需要一些帮助来找出我的代码中的错误在哪里,为什么它会给我这个,以及一个简单但很好的解释的解决方案。
这是我过去尝试过的:
- 我尝试使用 return
arr[0]
而不是arr
,但它给我一个错误,因为它无法从转换int
为int[]
。 - 我查看了我的合并课程,那里的一切似乎都很好。
- 我已经和我的老师讨论过这个问题,他说一切看起来都很好,但我知道一定有什么地方出了问题。
- 我试图删除
return merge(arr1, arr2)
,但系统抛出一个错误,告诉我我必须返回一些东西。 - 我尝试单独打印出数组,但它仍然没有显示任何变化,并且与原始字符串完全相同。
合并方法:
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;
}
合并排序方法:
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);
}
由于数组是随机生成的,因此示例如下:
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
解决方案
您的代码中有两个问题:
- 你返回一个数组元素
arr[0]
而不是数组本身arr
- 你不处理的情况
arr.length == 0
。它也应该返回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);
}
推荐阅读
- javascript - 如何让我的 HTML 表单日期输入仅允许使用 JavaScript、React 和 HTML 选择一周中的特定日期?
- markdown - 如何使用 Markdown 在表格的左上角单元格中绘制对角线?
- selenium-webdriver - 我无法编写 x 路径
- python - 如何用体素填充 3D 图形?
- asp.net - 美国 Zip+4 验证
- apache-spark - 如何在 spark.sql 中通过 (+) 使用外连接?
- javascript - Pipedream 上的 Outlook Node.js sendMail API 请求消息为空错误
- r - Is there a selective replace function? Should it be done using a If statement or For loop?
- php - 将多个 CodeIgniter 结果集合并到一个数组中
- python - Numpy 中的意外性能乘以 1