我在尝试为链表构造排序算法时遇到堆栈溢出异常。我的排序无限期地停留在同一个支点上,我不明白为什么它没有达到基本情况。
//Intlist 是一个简单的单链表类,有一个int var ".item"和一个.next 指针
pivotS(Intlist thisList){
if (thisList == null || thisList.next == null){
return thisList;
} else{
int pivot = thisList.item;
Intlist lower = lowerThanPivot(pivot, thisList);
Intlist upper = greaterOrEqualPivot(pivot, thisList);
lower = pivotS(lower);
upper = pivotS(upper);
return appendLists(lower, upper);
}
}
这在构造上应该类似于合并排序,对吗?我的个人功能似乎运行良好。我只是设置了错误的递归吗?
最佳答案
假设您有一个由数字 137 的两个副本组成的列表,让我们看看这个算法会做什么。
首先,您会查看第一个元素并注意到它存在(它不为空)并且列表不只有一个元素(下一个指针也不为空)。然后,您将第一项拆分为枢轴,因此枢轴为 137。
现在,看看接下来会发生什么。 lower
列表由小于主元的所有元素组成,在本例中为空列表。 upper
列表由大于或等于 pivot 的所有元素组成,在本例中它是 137 的两个副本。然后您在两个列表上递归调用 pivotS
。但是,这里有一个问题 - upper
列表等于您需要排序的原始列表,因此递归的进行方式与以前完全相同。这最终会导致堆栈溢出。
要解决此问题,请更新您的代码以将输入列表分成三个 组 - 小于主元的元素、等于主元的元素和大于主元的元素。这可能看起来像这样:
pivotS(Intlist thisList){
if (thisList == null || thisList.next == null){
return thisList;
} else{
int pivot = thisList.item;
Intlist lower = lowerThanPivot(pivot, thisList);
Intlist equal = equalToPivot(pivot, thisList);
Intlist upper = greaterThanPivot(pivot, thisList);
return appendLists(appendLists(pivotS(lower), equal), pivotS(upper);
}
}
关于java - 为什么我没有达到我的主元排序算法中的基本情况?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13131655/