调试归并实施
好吧，我知道这个问题不显示的研究工作，但我已经太多次经历这种code和我无法弄清楚是我做错了。我知道有很多归并实现的例子，但我想我的方式去做。任何帮助是AP preciated，谢谢。
进口java.util.Scanner中;
公共类归并
{
公共静态INT []归并（INT [] ARR）
{
如果（arr.length→1）
{
INT [] ARR1 = splitLeft（ARR）;
INT [] ARR2 = splitRight（ARR）;
ARR1 =归并（ARR1）;
ARR2 =归并（ARR2）;
回合并（ARR1，ARR2）;
}
其他
返回ARR;
}
公共静态INT [] splitLeft（INT [] ARR）
{
INT中间= arr.length / 2;
INT [] newarr =新INT [中];
的for（int i = 0; I＆LT;中部;我++）
newarr [i] =改编[I]
返回newarr;
}
公共静态INT [] splitRight（INT [] ARR）
{
INT中间= arr.length / 2;
INT [] newarr =新INT [arr.length - 中部]。
的for（int i = 0;我+中＆LT; arr.length;我++）
newarr [i] =改编[I +中];
返回newarr;
}
公共静态INT []合并（INT [] ARR1，INT [] ARR2）
{
INT []排序=新INT [arr1.length + arr2.length]。
INT的i1 = 0;
INT I2 = 0;
INT I = 0;
而（I1＆LT; arr1.length和放大器;＆安培; I2＆LT; arr2.length）
{
如果（ARR1 [I1]＆LT; ARR2 [12]）
{
排序[我] = ARR1 [I1]
I1 ++;
}
其他
{
排序[我] = ARR2 [12];
I2 ++;
}
我++;
}
而（I1＆LT; arr1.length）
{
排序[我] = ARR1 [I1]
I1 ++;
我++;
}
而（I2＆LT; arr2.length）
{
排序[我] = ARR1 [12];
I2 ++;
我++;
}
返回排序;
}
公共静态INT getNum（INT X）
{
INT NUM =（int）的（的Math.random（）* X + 1）;
返回NUM;
}
公共静态无效printArr（INT [] ARR）
{
的System.out.println（）;
的for（int i = 0; I＆LT; arr.length;我++）
的System.out.println（ARR [I]）;
}
静态扫描仪读卡器=新的扫描仪（System.in）;
公共静态无效的主要（字串[] args）
{
INT I;
的System.out.println（键入数组的长度）;
INT N = reader.nextInt（）;
的System.out.println（输入随机数发生器的范围）;
INT范围= reader.nextInt（）;
INT [] ARR =新INT [N];
对于（I = 0; I＆n种;我+ +）
改编[I] = getNum（范围）;
printArr（ARR）;
INT []排序=新INT [N];
排序=归并（ARR）;
printArr（排序）;
}
}
解决方案
我认为这个问题是在你的 splitRight 功能。考虑这个code：
的for（int i =中间; I＆LT; arr.length;我++）
newarr [i] =改编[I]
这会尝试复制我个自改编元素的我个 newarr 的位置，但是这是不正确。例如，如果阵列改编有十个元素，你要复制的元素5改编定位0 newArr 的元素6改编来定位1 newarr ，等等。
要解决这个问题，可以考虑尝试是这样的：
的for（int i = 0;我+中＆LT; arr.length;我++）
newarr [i] =改编[I +中];
希望这有助于！
Okay, I know this question doesn't show research effort, but I've been going through this code so many times and I couldn't figure out was I was doing wrong. I know there are many Mergesort implementation examples but I wanted to do it my way. Any help is appreciated, thanks.
import java.util.Scanner;
public class MergeSort
{
public static int[] mergeSort(int[] arr)
{
if (arr.length > 1)
{
int[] arr1 = splitLeft(arr);
int[] arr2 = splitRight(arr);
arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);
return merge(arr1, arr2);
}
else
return arr;
}
public static int[] splitLeft(int[] arr)
{
int middle = arr.length / 2;
int[] newarr = new int[middle];
for (int i = 0; i < middle; i++)
newarr[i] = arr[i];
return newarr;
}
public static int[] splitRight(int[] arr)
{
int middle = arr.length / 2;
int[] newarr = new int[arr.length - middle];
for (int i = 0; i + middle < arr.length; i++)
newarr[i] = arr[i + middle];
return newarr;
}
public static int[] merge(int[] arr1, int[] arr2)
{
int[] sorted = new int[arr1.length+arr2.length];
int i1 = 0;
int i2 = 0;
int i = 0;
while (i1 < arr1.length && i2 < arr2.length)
{
if (arr1[i1] < arr2[i2])
{
sorted[i] = arr1[i1];
i1++;
}
else
{
sorted[i] = arr2[i2];
i2++;
}
i++;
}
while (i1 < arr1.length)
{
sorted[i] = arr1[i1];
i1++;
i++;
}
while (i2 < arr2.length)
{
sorted[i] = arr1[i2];
i2++;
i++;
}
return sorted;
}
public static int getNum(int x)
{
int num = (int)(Math.random()*x + 1);
return num;
}
public static void printArr(int[] arr)
{
System.out.println();
for (int i = 0; i < arr.length; i++)
System.out.println(arr[i]);
}
static Scanner reader = new Scanner(System.in);
public static void main(String [ ] args)
{
int i;
System.out.println("Type the length of the array");
int n = reader.nextInt();
System.out.println("Type the range of the random numbers generator");
int range = reader.nextInt();
int[]arr = new int[n];
for (i = 0; i < n; i++)
arr[i] = getNum(range);
printArr(arr);
int[] sorted = new int[n];
sorted = mergeSort(arr);
printArr(sorted);
}
}
解决方案
I think the problem is in your splitRight function. Consider this code:
for (int i = middle; i < arr.length; i++)
newarr[i] = arr[i];
This tries to copy the ith element from arr to the ith position of newarr, but this is incorrect. For example, if the array arr has ten elements, you want to copy element 5 of arr to position 0 of newArr, element 6 of arr to position 1 of newarr, etc.
To fix this, consider trying something like this:
for (int i = 0; i + middle < arr.length; i++)
newarr[i] = arr[i + middle];
Hope this helps!
