无限循环/递归时，在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中实现快速排序

回答

相关问题