我试图使用Java实现合并排序,但它的意思是:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3
at HelloWorld.merge(HelloWorld.java:42)
at HelloWorld.sort(HelloWorld.java:30)
at HelloWorld.sort(HelloWorld.java:28)
at HelloWorld.sort(HelloWorld.java:29)
at HelloWorld.sort(HelloWorld.java:28)
at HelloWorld.main(HelloWorld.java:10)
因此,我尝试将原始数组复制到merge子例程中的helper数组中,我认为这是我用于helper数组的长度弄乱了所有内容,不是“ r-l + 1”这个helper数组的长度吗?
如果我将100作为辅助数组的长度,则代码可以工作,但是显然,当原始数组的大小变大时,它将无法工作。
请帮助并提前致谢。
public class HelloWorld{
public static void main(String []args){
HelloWorld ms = new HelloWorld();
int arr[] = new int[]{4,3,0,1,3,2,4,20,13,22,10};
ms.sort(arr, 0, arr.length - 1);
ms.printArr(arr);
}
void printArr(int arr[])
{
int n = arr.length;
for(int i = 0; i<n; i++){
System.out.print(" "+arr[i]);
}
}
void sort(int arr[], int l, int r)
{
if(l<r){
int m = (l+r)/2;
sort(arr, l, m);
sort(arr, m+1, r);
merge(arr, l, m, r);
}
}
void merge(int arr[], int l, int m, int r)
{
//find out helper array length
int helper[] = new int[r-l+1];
// Your code here
for(int i=l; i<=r; i++){
helper[i] = arr[i];
}
int i = l;
int k = l;
int j = m+1;
while(i<=m && j<=r){
if(helper[i]<=helper[j]){
arr[k]=helper[i];
i++;
}else{
arr[k]=helper[j];
j++;
}
k++;
}
while(i<=m){
arr[k]=helper[i];
i++;
k++;
}
}
}
如果我了解您尝试为合并排序算法正确实现MERGE子例程的方式,则可以将数组的相关部分(从index l
,包括index l
,包括index ,包括index ,包括在内)复制到helper数组中,然后修改原始数组使用复制到帮助程序数组中的数据。
在这种情况下,辅助数组确实应该具有length r-l+1
。但是,看看将原始数组部分复制到帮助程序数组中的代码,您并没有在for
循环中偏移索引。正确的方法是:
int helper[] = new int[r-l+1];
for (int i = l; i <= r; i++){
helper[i-l] = arr[i];
}
不要忘记数组是零索引!
但是,如果确实必须复制数组,我建议继续使用更现代的复制数组的方法。在这种情况下,我认为最适合的方法是system call System.arraycopy(arr, l, helper, 0, r-l+1)
。如果您想了解有关Java中复制数组(完全或部分)的不同方法的更多信息,请查看此答案。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句