Java合并排序算法
public class mergesort {
public static int[] mergesort (int[] input) {
int length = input.length;
if (length <= 1) {
return input;
}
int median = length/2;
int[] left = new int[median];
int[] right = new int[length-median];
for (int x = 0; x< median; x++) {
left[x] = input[x];
}
for (int y = median; y < length; y++) {
right[y-median] = input[y];
}
mergesort(left);
mergesort(right);
merge(left, right, input);
return input;
}
public static int[] merge (int[] left, int[] right, int[] input) {
int a = 0;
int b = 0;
int c = 0;
int leftlength = left.length;
int rightlength = right.length;
while (a<leftlength && b<rightlength) {
if (left[a] < right[b]) {
input[c] = left[a];
a++;
} else {
input[c] = right[b];
b++;
}
c++;
}
return input;
}
public static void main(String[] args) {
int[] inputArr = {45,23,11,89,77,98,4,28,65,43};
mergesort mms = new mergesort();
inputArr = mms.mergesort(inputArr);
for(int i = 0; i < inputArr.length; i ++){
System.out.print(inputArr[i]);
System.out.print(" ");
}
}以上是我对合并排序算法的尝试。main(String[] args)的最后一个代码块是一个测试运行，看看我的算法是否有效。
代码仍然打印出一个数组(之前，它只是抛出了一个错误)。然而，虽然算法应该打印出来
4, 11, 23, 28, 43, 45, 65, 77, 89,and 98, 代码打印如下：
4 4 11 23 23 28 65 43 65 43, 这显然不是预期的结果。
我如何修复我的代码？
这是我在这里的第一篇文章，所以如果我不被允许发布这些材料，请告诉我。
编辑:这是(令人惊讶的)原始代码的编辑版本。以前，代码抛出了一个错误，但至少现在它打印了一些东西。操作代码的一小部分(例如，将中位数更改为median+1等)没有起作用，我认为发布对某些人来说无关紧要的过多试验和失败结果并不是很重要。
是的，我真的不知道该怎么做。我请我的朋友审查代码，他使用调试器检查代码，但没有任何有意义的发现，因此这篇文章。
回答 1
Stack Overflow用户
发布于 2018-04-30 19:22:37
合并步骤的编写方式使其无法使用其整个输入。一旦要合并到一起的一个数组被完全消耗，循环就会终止，这不是我们所希望的。这可以通过在后续步骤中使用任一数组来修复，如下所示。
public static int[] merge(int[] left, int[] right, int[] input)
{
int a = 0;
int b = 0;
int c = 0;
int leftlength = left.length;
int rightlength = right.length;
while (a < leftlength && b < rightlength)
{
if (left[a] < right[b])
{
input[c] = left[a];
a++;
}
else
{
input[c] = right[b];
b++;
}
c++;
}
while (a < leftlength) // subsequent consumption of left
{
input[c] = left[a];
a++;
c++;
}
while (b < rightlength) // subsequent consumption of right
{
input[c] = right[b];
b++;
c++;
}
return input;
}注意，循环也可以放在单个循环中；有必要分别根据leftlength和rightlength检查a和b，以确定是应该进行比较还是必须附加单个元素。在更紧凑的C语言形式中，这可能如下所示。
public static int[] merge(int[] left, int[] right, int[] input)
{
int a = 0;
int b = 0;
int c = 0;
int cval = 0;
int leftlength = left.length;
int rightlength = right.length;
while (a < leftlength || b < rightlength) // <-- note the changed condition
{
if (a == leftlength)
{
cval = right[b++];
}
else if (b == rightlength)
{
cval = left[a++];
}
else
{
cval = left[a] < right[b] ? left[a++] : right[b++];
}
input[c++] = cval;
}
return input;
}https://stackoverflow.com/questions/50099154
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号