为什么这种排序算法只排序为最终整数的值？

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. ...