java - 递归算法中的无限循环

Question

我需要做一个枢轴排序算法，基本上你取一个链表的第一项，将它分类成两个单独的列表，一个的项目大于或等于第一个项目，另一个项目小于第一个项目，然后递归地对它们进行排序，直到到达一个大小为 1 的链表，其中它已经排序，然后将小于和大于列表合并在一起以形成一个排序列表。

我的算法在无限循环中一直卡在最后一个项目上，我现在已经有大约 23 个小时没有 sleep 了，需要一双新的眼睛来发现我在哪里犯了错误。如果您能提供帮助，我将不胜感激。

链表类很简单，有两项，第一项只是一个正整数，第二项当然是列表中的下一项。当代码到达最后一个项目并且没有将最后一个项目附加在一起时，代码会被 Sort() 函数捕获

public class PivotSort {
   public static void main(String[] args) {
      try {
         intList x = intList.CreateFromUserInput(); // just makes a linked list
                                                    // from numbers I type in
         x = Sort(x);
         x.PrintList();
      } catch (Exception e) {
         System.out.println(e);
      }
   }

   public static intList Sort(intList list) {
      if (list == null || list.item == null)
         return list;
      return Append(Sort(Part_Less(list.item, list)),
            Sort(Part_Greater(list.item, list)));
   }

   public static intList Part_Less(int N, intList L1) {
      if (L1 == null)
         return null;
      if (L1.item < N)
         return new intList(L1.item, Part_Less(N, L1.next));
      else
         return Part_Less(N, L1.next);
   }

   public static intList Part_Greater(int N, intList L1) {
      if (L1 == null)
         return null;
      if (L1.item >= N)
         return new intList(L1.item, Part_Greater(N, L1.next));
      else
         return Part_Greater(N, L1.next);
   }

   public static intList Append(intList L1, intList L2) {
      try {
         if (L1 == null)
            return L2;
         if (L2 == null)
            return L1;
         for (intList curr = L1; curr != null; curr = curr.next) {
            if (curr.next == null) {
               curr.next = L2;
               break;
            }
         }
         return L1;
      } catch (Exception e) {
         System.out.println(e);
         return null;
      }
   }
}

Answer 1

问题是，第二次调用永远无法达到您的 Sort 基本情况:

Sort(Part_Greater(list.item, list))

Part_Greater() 函数将首先构造一个列表，其中包含大于或等于第一项的所有项。假设这是您的原始列表:

10 5 7 11 15 7 16 20

Part_Greater() 将构造一个列表，其中包含 10 11 15 16 20。当您将其传递给 Sort 时，它将再次对该列表调用 Part_Greater()，结果就是该列表。

由于在第一次调用 Part_Greater() 后没有删除任何元素，因此您进入了无限递归。

您需要做的是从列表中删除枢轴元素。这确保了在每个递归步骤中，您的数字列表都会至少缩短一个，最终在列表为空时达到基本情况。

return Append(
    Sort(Part_less(list.item, list.next)),
    new intList(list.item, Sort(Part_Greater(list.item, list.next)))
);