在Java中实现quicksort时的无限循环/递归
||
我正在尝试在Java中实现quicksort,以便计算进行比较的次数,但是我遇到了无限循环/递归调用的情况,我无法弄清楚它的去向从。
通过调试,我确定了内部for循环运行了很多次,并且所有内容仅输入到“ less \”子列表中,然后对quicksort(less)进行了递归调用。
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)
没有找到相关结果
已邀请:
3 个回复
桑娠贯涤
募磷
丧泉缝锋