编写QuickSort算法时出现索引超出范围

Question

我目前正在编写快速排序算法的修改版本，即使我的ArrayList输入中包含元素，我也会得到索引超出范围异常。

希望有人能告诉我，我要去哪里错了...

以下是错误代码：

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 
4, Size: 4 at java.util.ArrayList.rangeCheck(ArrayList.java:635) at> java.util.ArrayList.get(ArrayList.java:411)  at 
Lab4.quickSort(Lab4.java:36) at Lab4.main(Lab4.java:113) 

这是我目前使用的代码：

public void quickSort(ArrayList<Integer> S){ 
    if(S.size() <= 1) return; 

    int middle = (S.size() - 1)/2; 
    int pivot = S.get(middle); 
    ArrayList<Integer> L = new ArrayList<Integer>(); //less 
    ArrayList<Integer> E = new ArrayList<Integer>(); //equal 
    ArrayList<Integer> G = new ArrayList<Integer>(); //greater 

    int i = 0; 
    while(!S.isEmpty()) { 
     int next = S.get(i); 
     if(next == pivot) E.add(next); 
     else if(next > pivot) G.add(next); 
     else if(next < pivot) L.add(next); 
     i++; 
    } 

    quickSort(L); 
    quickSort(G); 

    S.addAll(L); 
    S.addAll(E); 
    S.addAll(G); 
} 

我目前用来测试这个方法的ArrayList如下（想想你可能也需要这个部分）：

ArrayList<Integer> arr2 = new ArrayList<Integer>(); 
arr2.add(3); 
arr2.add(1); 
arr2.add(6); 
arr2.add(5); 
sort.quickSort(arr2); 
System.out.println("\n\nQuickSort (should be sorted): "); 
printIntArrayList(arr2); 

Answer 1

如果S包含值d.isEmpty()永不返回false。所以你在无限循环中运行。如果我将S.size()放大，如果使用get()函数，则会得到ArrayIndexOutOfBoundException。

变化：

while(!S.isEmpty()) { 

到：

while (i<S.size()) { 

Answer 2

问题是与此代码：

int i = 0; 
while(!S.isEmpty()) { 
    int next = S.get(i); 
    if(next == pivot) E.add(next); 
    else if(next > pivot) G.add(next); 
    else if(next < pivot) L.add(next); 
    i++; 
} 

从S，您没有去除所述元件，因此你将满足条件。随着每次迭代，你增加了i值，当你尝试读取第n + 1个元素时，你会得到异常。

你可能需要检查边界和循环，直到那时（像while (i<S.size())）？

Answer 3

问题就出在这个循环中

int i = 0; 
    while(!S.isEmpty()) { 
     int next = S.get(i); 
     if(next == pivot) E.add(next); 
     else if(next > pivot) G.add(next); 
     else if(next < pivot) L.add(next); 
     i++; 
    } 

变量“我”是没有任何限制的增加，你必须小心限制多少增加，也while循环不会打破你不是删除任何东西

Answer 4

这里的问题是，你的S永远不是空的，ArrayList的函数只返回值而不删除它，你应该做的是改变你的条件而在：while(i<S.size()))也这不是最好的在列表上循环的方式，而不是你可能想迭代列表：for (Integer x : S) a nd使用x你的元素。

Answer 5

你的问题是你的while循环。你可以调用!S.isEmpty()作为你的布尔表达式，然后遍历S.这里的错误是S永远不会是空的，所以你的方法一旦到达列表的末尾就会一直出界。相反，尝试检查列表是否包含下一个项目。我建议在循环结尾处添加以下内容：

if(S.get(i+1) == null){ 
return; 
}