的StackOverflowError的快速排序的Java

Question

我測試一個快速排序的代碼我寫的，但我不知道爲什麼我收到

錯誤：

Exception in thread "main" java.lang.StackOverflowError 
    at java.util.ArrayList$Itr.<init>(ArrayList.java:820) 
    at java.util.ArrayList.iterator(ArrayList.java:814) 
    at practice.Quicksort.quicksort(Quicksort.java:15) 
    at practice.Quicksort.quicksort(Quicksort.java:25) 
    at practice.Quicksort.quicksort(Quicksort.java:25) 
    at practice.Quicksort.quicksort(Quicksort.java:25) 

，其中第15行是：

for (int n : arr) { 

並且第25行是：

more = quicksort(more); 

c ode：

public class Quicksort { 
    public static List<Integer> quicksort(List<Integer> arr) { 
     if (arr.size() <= 1) { 
      return arr; 
     } 
     List<Integer> less = new ArrayList<Integer>(); 
     List<Integer> more = new ArrayList<Integer>(); 
     int pivotIndex = arr.size()/2; 
     int pivot = arr.get(pivotIndex); 
     for (int n : arr) { 
      if (n < pivot) { 
       less.add(n); 
      } 
      else { 
       more.add(n); 
      } 
     } 
     // recursively sort 
     less = quicksort(less); 
     more = quicksort(more); 

     // concatenate all 
     less.add(pivot); 
     less.addAll(more); 
     return less; 
    } 

    public static void main(String[] args) { 
     List<Integer> test = new ArrayList<Integer>(); 
     int[] arr = {2,4,1,4,5,2,-10,3,0,33,23}; 
     for (int c : arr) { 
      test.add(c); 
     } 
     System.out.println(quicksort(test)); 
    } 
} 

Answer 1

您的代碼有一個基本缺陷，這增加了名爲more的列表在兩次後續迭代中的可能性。可能存在的問題在於代碼的下面部分：

int pivotIndex = arr.size()/2; 
    int pivot = arr.get(pivotIndex); 
    for (int n : arr) { 
     if (n < pivot) { 
      less.add(n); 
     } 
     else { 
      more.add(n); 
     } 
    } 

不要在more或less列表中添加的支點。此外，您可以瞭解如何選擇變體here on the blog

Answer 2

列表more不應包含數據透視表。如果它運行的風險是more與傳入的列表完全相同，並且在程序用完堆棧空間之前得到無限遞歸循環。

一種常用技術是將交換點與列表中的第一個項目交換，然後從第二個項目開始創建less和more的列表。