1

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

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

链表类很简单，有两项，第一项只是一个正整数，第二项当然是列表中的下一项。当代码碰到最后一项时，代码在 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;
      }
   }
}
4

1 回答 1

2

问题是，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)))
);
于 2012-11-03T22:39:04.707 回答