java - 为什么我没有达到我的主元排序算法中的基本情况？

Question

我在尝试为链表构造排序算法时遇到堆栈溢出异常。我的排序无限期地停留在同一个支点上，我不明白为什么它没有达到基本情况。

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

这在构造上应该类似于合并排序，对吗？我的个人功能似乎运行良好。我只是设置了错误的递归吗？

Answer 1

假设您有一个由数字 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);
    }
  }