雙鏈表上的氣泡排序

在這裏已經試了幾個小時試圖讓氣泡排序的實現工作在雙鏈表上。我的代碼似乎只能通過一次，但是沒有完成排序就提前完成。任何指導將不勝感激。雙鏈表上的氣泡排序

public void bubbleSort() 
{ 
    Node cur = head.getNext(); 
    boolean done = false; 

    while (!done) 
    { 
     done = true; 
     while(cur != tail) 
     { 
      if (cur.getNext().getCount()>cur.getCount()) 
      { 
       swap(cur.getNext(),cur); 
       done=false; 
      } 
      cur = cur.getNext(); 
     } 
    } 
}

我使用的交換方法似乎破壞了節點的位置，直到它是兩個節點之間的循環環路。

private void swap(Node n1, Node n2) 
{ 
    Node b1, b2, a1, a2; 
    System.out.println("Swapping n1: " + n1 + " with n2: " + n2); 
    b1 = n2.getPrev(); 
    if (b1 == n1) // handle adjacent nodes 
     b1 = n2; 
    a1 = n2.getNext(); 

    b2 = n1.getPrev(); 
    if (b2 == n2) // handle adjacent nodes 
     b2 = n1; 
    a2 = n1.getNext(); 

    // swap 

    n1.setPrev(b1); 
    n1.setNext(a1); 

    n2.setPrev(b2); 
    n2.setNext(a2); 

    b1.setNext(n1); 
    a1.setPrev(n1); 

    b2.setNext(n2); 
    a2.setPrev(n2); 
}

感謝

來源

2013-02-24 efnx

爲什麼不寫一個比較器http://javarevisited.blogspot.com/2011/06/comparator-and-comparable-in-java.html – lichengwu 2013-02-24 03:29:53

在一個鏈表中，交換一個元素及其直接後繼是一個特例。那個案例經過測試？您需要返回到外循環的每次迭代的列表的開頭。 – 2013-02-24 03:41:51

爲簡單列表逐步運行代碼，並觀察其行爲。 – 2013-02-24 04:31:55

我在你的代碼中看到的問題：

您應該從head開始，而不是從head.getNext()。
您應重新啓動Node cur迭代每while(!done)。

有了這些變化，你的代碼應該是

public void bubbleSort() { 
    boolean done = false; 
    while (!done) { 
     Node cur = head; 
     done = true; 
     while(cur != tail) { 
      if (cur.getNext().getCount()>cur.getCount()) { 
       swap(cur.getNext(),cur); 
       done=false; 
      } 
      cur = cur.getNext(); 
     } 
    } 
}

此代碼假定您swap方法的工作，沒有任何問題。使用int count作爲Node類中的數據進行測試，在列表中分配10000個int值。

編輯：根據你的問題的編輯，我做了我Node類swap功能是這樣的：

private static class Node { 
    int count; 
    Node next; 
    //getters and setters... 
} 

//this function just swaps data, no need to swap the nodes prev and next 
//(note that yours is an algorithm design issue) 
private void swap(Node node1, Node node2) { 
    int aux = node1.getCount(); 
    node1.setCount(node2.getCount()); 
    node2.setCount(aux); 
}

不需要做您在swap實施所做的所有樣板代碼。

來源

2013-02-24 05:46:34

+1 goos answer！ – alfasin 2013-02-24 09:30:57

然後我得到一個空指針錯誤，因爲頭部和尾部是標記標記。這是我很確定的交換方法。 – efnx 2013-02-24 14:22:27

@efnx我想你的LinkedList實現中有一個問題，儘管= \。我做了一個快速測試，像魅力一樣工作。 – 2013-02-24 14:23:12

在外環的開頭添加cur = head.getNext();爲我實現鏈表的正常工作。所以問題來自swap方法或者你的列表的實現。

根據您的bubbleSort方法，swap方法只交換節點的數據，而不是節點本身。我的意思是，它只是交換價值count。如果不是這種情況，swap方法是問題所在。否則，你的雙鏈表的實現有問題。

來源

2013-02-24 03:44:59

感謝您的幫助。這絕對是交換方法。現在我只需要弄清楚什麼是錯的。對於一個簡單的n <100列表，它工作正常，但對於我測試的n = 1000列表，我有失敗。 – efnx 2013-02-24 04:45:02

你肯定需要在外循環的末尾保留cur = head.getNext();，否則在第二次循環時，inner while循環將被完全跳過，並且結果爲真。

您是否考慮過氣泡排序的運行時間？我注意到在你對MD.Unicorn的回答中，它適用於列表< 100，但不適用於列表1000.列表1000的預期運行時間至少比列表小於100的列表慢100倍。您不可以給它足夠的時間來完成。

需要多長時間才能對100個列表進行排序？

來源

2013-02-24 05:44:16

100個元素需要4390ms到5038ms，我的電腦需要1000個元素需要12740ms和13608ms。 – 2013-02-24 05:56:21

雙鏈表上的氣泡排序

回答

相關問題