2

我在尝试为链表构建排序算法时遇到堆栈溢出异常。在那里，我的排序无限期地卡在同一个支点上，我无法弄清楚为什么它没有达到基本情况。

//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);
    }
  }

这应该类似于构造中的合并排序，对吧？我的个人功能似乎工作正常。我只是设置递归错误吗？

4

1 回答 1

0

想象一下，你有一个由数字 137 的两个副本组成的列表，让我们看看这个算法会做什么。

首先，您将查看第一个元素并注意到它存在（它不为空）并且列表不只有一个元素（下一个指针也不为空）。然后将第一项拆分为枢轴，因此枢轴为 137。

现在，看看接下来会发生什么。该lower列表由小于主元的所有元素组成，在本例中为空列表。该upper列表由大于或等于枢轴的所有元素组成，在这种情况下，枢轴是 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);
    }
  }
于 2015-08-24T23:05:46.353 回答