遞歸算法中的無限循環

Question

我需要做一個數據透視排序算法，其中基本上你把鏈表的第一項，排序成兩個單獨的列表，其中一個項目大於或等於第一個項目，另一個項目小於第一項，然後遞歸排序，直到您到達已經排序的大小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; 
     } 
    } 
} 

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