我试图在不查看任何源代码的情况下实现mergesort。每当我尝试运行我的程序时,我都会得到这个异常:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 5
at Mergesort.merge_halves(Mergesort.java:40)
at Mergesort.mergesort(Mergesort.java:31)
at Mergesort.mergesort(Mergesort.java:29)
at Mergesort.main(Mergesort.java:15)
这是我的程序:
public class Mergesort {
private static int [] tempArr;
public static void main(String [] args) {
int [] arr = new int[5];
arr[0] = 2;
arr[1] = 4;
arr[2] = 9;
arr[3] = 11;
arr[4] = 3;
Mergesort sorter = new Mergesort();
sorter.mergesort(arr, arr[0], arr.length - 1);
for(int i = 0; i < tempArr.length - 1; i++) {
System.out.print(tempArr[i] + " ");
}
}
public void mergesort(int [] arr, int low, int high) {
if(low >= high) {
return;
}
int mid = (low + high) / 2;
mergesort(arr, low, mid);
mergesort(arr, mid + 1, high);
merge_halves(arr, low, mid, high);
}
public void merge_halves(int [] arr, int low, int mid, int high) {
tempArr = new int[arr.length];
int i = 0;
while(i < tempArr.length) {
if(arr[i] <= arr[i + 1]) {
tempArr[i] = arr[i];
i++;
} else {
tempArr[i] = arr[i + 1];
i++;
}
}
}
}
我试图通过改变while循环中的条件来修复错误,以使程序正确运行
while(i < tempArr.length - 1)
但是当我编译这个并打印tempArr时,我得到的数组缺少一个元素:
2 4 9 3
我该如何解决这个问题?
不确定这是否是唯一的错误,但在对mergeSort
的第一次调用中,您传递的是数组的第一个数字,而不是数组的第一索引。
更改
sorter.mergesort(arr, arr[0], arr.length - 1);
至
sorter.mergesort(arr, 0, arr.length - 1);
实际上merge_halves
也有一个问题。当i==tempArr.length-1时,arr[i + 1]
将导致ArrayIndexOutOfBoundsException。
缺少的元素来自打印方式:显式循环到array.length-1。
您的合并函数不会合并任何内容。您应该首先将arr复制到temp,然后再次按顺序组装arr中的元素。(或者在temp中组装它们,然后复制回arr。(你的工作数组应该总是arr。
你也没有正确地进行合并。您有三个数组:排序较低的数组"a"、排序较高的数组"b"和结果数组"r",当然也应该对它们进行排序。
在开始时,a
和b
在arr
中彼此相邻,a
在arr[low ... mid]
中并且b
在arr[mid ... high]
中。(这里,arr[i ... j]
是指从索引i
到但不包含j
的子阵列。(
合并后,arr
应包含r
。
比较两个相邻的数组元素arr[i]
和arr[i + 1]
,但应将a
的当前元素与b
的当前元素进行比较,直到用完其中一个数组为止。所以你需要三个索引,每个数组一个。