無限循環/遞歸時，在Java中實現快速排序

我試圖實現快速排序在Java才能算取得比較的次數，但我運行到一個無限循環/遞歸調用的情況，我不能很清楚它是從哪裏來的。無限循環/遞歸時，在Java中實現快速排序

經過調試我已經確定爲內循環運行但是很多時候，一切都只能進入「少」子表，然後遞歸調用快速排序來（少）

private ArrayList<Comparable> quickSort(ArrayList<Comparable> qList) { 
      ArrayList<Comparable> less = new ArrayList<Comparable>(); 
      ArrayList<Comparable> greater = new ArrayList<Comparable>(); 
      if (qList.size() <= 1) 
       return qList; 
      Comparable pivot = qList.get(qList.size()/2); 
      for (int i = 0; i < qList.size(); i++) { 
       if ((qList.get(i).compareTo(pivot)) <= 0) { 
        comps++; 
        less.add(qList.get(i)); 
       } else { 
        comps++; 
        greater.add(qList.get(i)); 
       } 
      } 

      ArrayList<Comparable> toReturn = new ArrayList<Comparable>(
        quickSort(less)); 
      toReturn.add(pivot); 
      toReturn.addAll(quickSort(greater)); 
      return toReturn; 

     }

做如果我只是運行與大小20的列表的代碼，我得到這個錯誤

Exception in thread "main" java.lang.StackOverflowError 
    at java.util.Arrays.copyOf(Unknown Source) 
    at java.util.ArrayList.ensureCapacity(Unknown Source) 
    at java.util.ArrayList.add(Unknown Source) 
    at file.quickSort(CMSC351P1.thisClass:40) 
    at file.quickSort(CMSC351P1.thisClass:48)

來源

2011-04-15 Rowhawn

的問題是，你的轉動部件本身添加到「少」列表中，這樣的基本情況永遠不會終止。

示例：您使用您的算法對列表[0，0]進行排序。主元素是... 0.算法生成的'less'列表又是[0，0]，並且您進入無限循環。

來源

2011-04-15 01:08:28

在我看來，實際的問題是，對分裂較高和較低的列表時樞轉不從列表中刪除;你在每次迭代中都添加一個元素... – bdares 2011-04-15 01:11:10

是的，那麼只有在遞歸之後。 – 2011-04-15 01:12:26

啊，沒錯。我應該使用刪除而不是得到。謝謝！ – Rowhawn 2011-04-15 01:15:57

你不排除從以下/越大的子列表樞軸 - 其實，你明確地將其包含在子表集。我懷疑這意味着在很多情況下你會遇到兩個被無限排序的列表。您需要從少子列表中排除樞軸。

來源

2011-04-15 01:09:46

你不確保您，使大名單的尺寸減少了1個或多個或較少列表的大小由1個或多個分區下降的列表。

在某些時候，如果轉角是在列表中的最大元素，那麼一切都將進入「少」名單。

當你調用它，同樣的事情會再次發生。

來源

2011-04-15 01:19:50

無限循環/遞歸時，在Java中實現快速排序

回答

相關問題