我无法弄清楚为什么我的代码出现 IndexOutOfBoundsException
。我想知道是否有人可以成为我的额外眼睛来帮助我发现错误。我正在手动尝试这个,但我认为在浏览代码时我遗漏了一些东西。
代码:
package Algorithms;
import java.util.ArrayList;
public class quickSort {
public static ArrayList<Integer> mergeArrayList(ArrayList<Integer> min, int pivot, ArrayList<Integer> max) {
ArrayList<Integer> mergedList = new ArrayList<Integer>();
//mergedList.addAll(min);
for (int i : min) {
mergedList.add(i);
}
mergedList.add(pivot);
//mergedList.addAll(max);
for (int j : max) {
mergedList.add(j);
}
return mergedList;
}
public static ArrayList<Integer> quicksort(ArrayList<Integer> array, int min, int max) {
if (array.size() <= 1) {
return array;
}
int pivot = (min + max)/2;
ArrayList<Integer> less = new ArrayList<Integer>();
ArrayList<Integer> greater = new ArrayList<Integer>();
for (int i : array) {
if (i <= array.get(pivot)) {
less.add(i);
}
else {
greater.add(i);
}
}
return mergeArrayList(quicksort(less,min,pivot - 1), array.get(pivot), quicksort(greater, pivot + 1, max));
}
public static void main(String[] args) {
ArrayList<Integer> arr1 = new ArrayList<Integer>();
int[] arr = {1,2,3,4,5};
for (int i : arr) {
arr1.add(i);
}
System.out.println(quicksort(arr1,0,arr1.size() - 1));
}
}
错误:
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 3, Size: 2
at java.util.ArrayList.rangeCheck(ArrayList.java:635)
at java.util.ArrayList.get(ArrayList.java:411)
at Algorithms.quickSort.quicksort(quickSort.java:30)
at Algorithms.quickSort.quicksort(quickSort.java:37)
at Algorithms.quickSort.main(quickSort.java:46)
最佳答案
返回中的quicksort(greater,pivot + 1, max)将导致:
int pivot = (max + pivot + 1) /2; //pseudocode
pivot 将大于数组的长度(是原始长度的一半),导致当您请求 array.get(pivot) 时出现越界异常
关于java - IndexOutOfBoundsException 和快速排序算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22773193/