編寫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; 
}