我正试图在 Java 中实现快速排序以计算比较次数,但我遇到了无限循环/递归调用情况,我无法完全弄清楚它的来源。
通过调试我确定内部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)
最佳答案
问题是您将主元元素本身添加到“less”列表中,因此基本情况永远不会终止。
示例: 您使用算法对列表 [0, 0] 进行排序。枢轴元素是 ... 0。您的算法生成的“较少”列表再次为 [0, 0],并且您进入了无限循环。
关于java - 在java中实现快速排序时的无限循环/递归,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5671388/