爲什麼這種排序算法只排序爲最終整數的值？

Question

每當我嘗試對這個鏈表進行排序時，它只會將它排序到列表中的最後一個數字。例如，對於[5,8,4,9,0,1,2,3,7,6]的鏈表，唯一的返回值是[0,1,2,3,4,5,6]。我覺得在這裏某處有一個愚蠢的錯誤，儘管最後一小時試圖找到它，但我一直無法確定。

這裏是我的代碼：

class SortyList 
{ 
    { 
     private int key; 
     private Node next; 

     private Node(int key, Node next) 
     { 
      this.key = key; 
      this.next = next; 
     } 
    } 

    private Node head; 
    private Node first; 

    public SortyList() 
    { 
     head = new Node(0, null); 
    } 

    public SortyList(int first, int ... rest) 
    { 
     Node last = new Node(first, null); 
     this.first = last; 
     for (int index = 0; index < rest.length; index += 1) 
     { 
      last.next = new Node(rest[index], null); 
      last = last.next; 
     } 
     head = new Node(0, null); 
    } 

    public SortyList sort() 
    { 
     first = sort(first); 
     return this; 
    } 

    private Node sort(Node unsorted) 
    { 

     if (unsorted == null || unsorted.next == null || unsorted.next.next == null) { 
      return unsorted; 
     } 
     Node left = unsorted; 
     Node lo = left; 
     unsorted = unsorted.next; 
     Node right = unsorted; 
     Node ro = right; 
     unsorted = unsorted.next; 
     for (int i = 0; unsorted != null; i++) { 
      if (i % 2 == 0) { 
       Node temp = left; 
       left = unsorted; 
       temp.next = left; 
      } else { 
       Node temp = right; 
       right = unsorted; 
       temp.next = right; 
      } 
      unsorted = unsorted.next; 
     } 
     Node r = lo; 

     left = sort(lo); 
     right = sort(ro); 
     Node merged; 
     Node end; 
     if (left.key > right.key) { 
      merged = right; 
      right = right.next; 
     } else { 
      merged = left; 
      left = left.next; 
     } 
     end = merged; 
     while (left != null && right != null) { 
      if (left.key > right.key) { 
       end.next = right; 
       right = right.next; 
      } else { 
       end.next = left; 
       left = left.next; 
      } 
      end = end.next; 
     } 

     if (left != null) { 
      end = left; 

     } else if (right != null) { 
      end = right; 
     } 

     return merged; 
    } 

    public String toString() 
    { 
     StringBuilder builder = new StringBuilder(); 
     builder.append('['); 
     if (first != null) 
     { 
      Node temp = first; 
      builder.append(temp.key); 
      temp = temp.next; 
      while (temp != null) 
      { 
       builder.append(", "); 
       builder.append(temp.key); 
       temp = temp.next; 
      } 
     } 
     builder.append(']'); 
     return builder.toString(); 
    } 

    public static void main(String[] args) 
    { 
     System.out.println(new SortyList(5, 8, 4, 9, 0, 1, 2, 3, 7, 6).sort()); 
    } 
} 

Answer 1

我還沒有研究你的算法，但它似乎有一些問題，你的代碼，例如，

1. 爲Node類名。

2. 您使用head節點，但它在你的代碼似乎沒有什麼用處。

3. if (unsorted == null || unsorted.next == null || unsorted.next.next == null)

   如葉蘭提到這個條件不正確。如果你刪除最後一個條件在運行時程序會做無休止的遞歸：

   left = sort(lo);

   ，這就是爲什麼你有一個堆棧溢出異常。

4. Node end;

   end是一個局部變量，它無助於在sort(Node unsorted)函數的最後幾行的值賦給它：

   // it does nothing if (left != null) { end = left; } else if (right != null) { end = right; }

5. ...