用Java对链表进行排序

Question

我写了一个气泡排序算法来对链表进行排序。我是一名Java初学者，并试图学习数据结构。我很困惑为什么我的第二个元素没有正确排序。

编辑

class SListNode { 
    Object item; 
    SListNode next; 


    SListNode(Object obj) { 
    item = obj; 
    next = null; 
    } 


    SListNode(Object obj, SListNode next) { 
    item = obj; 
    this.next = next; 
    } 

} 
public class SList { 

    private SListNode head; 
    private SListNode temp; 

    public void sortList() { 
     SListNode node = head,i,j; 
     head = node; 
     i = node; 
     j = node.next; 
     while(i.next != null) { 
      while(j.next != null) { 
       if((Integer)i.item < (Integer)j.item) { 
        temp = i.next; 
        i.next = j.next; 
        j.next = temp; 
       } 
       j = j.next; 
      } 
      i = i.next; 
     } 
    } 
} 

这是我得到

List after construction: [ 3 6 9 4 12 15 ] 
After sorting: [ 3 4 9 12 6 15 ] 

输出此外，我知道冒泡排序的最坏情况是O（n ）。我可以在链表上使用mergesort来获得更好的时间复杂度吗？

谢谢！

Answer 1

有很多排序算法在链表上工作，mergesort在这种情况下工作得很好。我写了an earlier answer to a question about sorting linked lists，探索链表上的许多经典排序算法，以及它们的时间和空间复杂性。您可以在链接列表上使用插入排序，选择排序，合并排序和快速排序。有一点欺骗，你也可以让heapsort工作。我的旧回答详细介绍了如何做到这一点。

关于您的代码，请注意，在您的内循环中，您前进j，直到next指针变为null。此时，您永远不会将j重置为其他任何内容，因此在外部循环的每个未来迭代中内部循环都不会执行。您应该在每次迭代开始时设置j = i.next。此外，当j.next为空时，而不是j为空时，您可能不想让循环停止，否则会跳过数组的最后一个元素。

此外，您在这里写的排序算法是selection sort而不是冒泡排序，因为你是在找你还没有定位在最小元素的链表使得很多遍。我不知道这是否是一个问题，但我不确定你是否知道这一点。也就是说，我认为这可能是一件好事，因为在大多数情况下，冒泡排序比选择排序效率低（除非列表已经接近排序）。

希望这会有所帮助！