用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而不是冒泡排序，因爲你是在找你還沒有定位在最小元素的鏈表使得很多遍。我不知道這是否是一個問題，但我不確定你是否知道這一點。也就是說，我認爲這可能是一件好事，因爲在大多數情況下，冒泡排序比選擇排序效率低（除非列表已經接近排序）。

希望這會有所幫助！