java我有一个快速排序方法的基本情况,但我仍然得到一个堆栈溢出错误?
我有一个快速排序类,它可以处理较小的列表大小,但在较大的列表大小上不断出现错误,即使我有一个基本情况。我有一个类似这样的快速排序类:
public class QuickSorter extends Sorter
{
@Override
public void sort(WordList toSort, Comparator<String> comp) throws NullPointerException{
// TODO
int front = 0;
int back = toSort.length() -1;
quickSortRec(toSort, comp, front, back);
}
private void quickSortRec(WordList list, Comparator<String> comp, int start, int end){
// TODO
if (start >= end) {
return;
}
int pivotPoint = partition(list, comp, start, end);
quickSortRec(list, comp, start, pivotPoint - 1);
quickSortRec(list, comp, pivotPoint + 1, end);
}
private int partition(WordList list, Comparator<String> comp, int start, int end){
// TODO
String pivotSpot = list.get(end);
int pivotIndex = start;
for(int i = start; i < end; i++) {
if(comp.compare(list.get(i), pivotSpot) < 0) {
list.swap(i, pivotIndex);
}
}
list.swap(end, pivotIndex);
return pivotIndex;
}
}
我的代码在需要排序的较小列表上运行良好,但第36行出现了重复的StackOverflow异常
堆栈跟踪如下所示:
Exception in thread "main" java.lang.StackOverflowError
at hw2.AlphabetComparator.compare(AlphabetComparator.java:1)
at hw2.Sorter$CountingComparator.compare(Sorter.java:272)
at hw2.QuickSorter.partition(QuickSorter.java:53)
at hw2.QuickSorter.quickSortRec(QuickSorter.java:32)
at hw2.QuickSorter.quickSortRec(QuickSorter.java:36)
at hw2.QuickSorter.quickSortRec(QuickSorter.java:36)
at hw2.QuickSorter.quickSortRec(QuickSorter.java:36)
at hw2.QuickSorter.quickSortRec(QuickSorter.java:36)
字母比较仪:
int length = b.length(); // holds smallest length of both strings so I don't get an out of bounds exception with my for loop
if (a.length() < b.length()) // default length will be String b's length if b is less than a or a and b are ==
{
length = a.length();
}
for (int i = 0; i < length; i++)
{
if (a.charAt(i) != b.charAt(i)) // if character at same index in both strings aren't equal
{
if (alphabet.isValid(a.charAt(i)) == true && alphabet.isValid(b.charAt(i)) == true) // if both characters are valid in the alphabet
{
return alphabet.getPosition(a.charAt(i)) - alphabet.getPosition(b.charAt(i)); // return negative or positive
}
}
}
if (a.length() != b.length())
{
if (length == a.length())
{
return -1;
} else
return 1;
}
return 0;
}
```
# 1 楼答案
使用递归进行排序,堆栈不是无限的。对于足够小的数组,递归保持在限制之内。但对于足够大的阵列,它会破坏堆栈。通常情况下,在无限循环的情况下会发生堆栈溢出,但在您的情况下,由于数组太宽,很可能只是递归太深
参考https://freecontent.manning.com/stack-safe-recursion-in-java/#:~:text=Default%20stack%20size%20varies%20between,case%20is%20recursive%20method%20calls
你的下一个问题可能会在这里得到回答: How to increase the Java stack size?