鏈接列表氣泡排序

我想知道如何在單鏈表上實現氣泡排序。比方說，例如，我們有列表，它包含以下節點：鏈接列表氣泡排序

struct node { 
    int value; 
    struct node* next; 
}

我認爲有2種方法來acomplish此：

1)to directly exchange `values` in memory 
2)to change `nexts`, to point to a different nodes

哪種方法更高效，並能有人給我關於如何做的一些例子？我知道使用Bubble Sort與其他排序算法相比效率不高。

只要你沒有給出有關perf的聲音：只需從列表中創建一個數組，按照排序的數組重新創建列表。 – 2011-05-30 18:25:14

我希望看到*內存局部性*與算法相關的問題 - 假設一個相對較大的'n'。在上面的例子中，值是一個int，因此（大概）不大於指針的大小，所以讓我們假設＃1和＃2在處理器指令方面「相同」。 – 2011-05-30 18:27:35

我想不出在鏈表上實現冒泡排序的好理由。陣列上的算法本身已經* fracking *慢，爲什麼使用鏈表更難以懲罰自己？ – karlphillip 2011-05-30 18:31:05

你的值非常小，所以我期望交換它們比改變指針結構更高效。與往常一樣，您必須測量用例中的實際性能。

2011-05-30 18:14:25

但是如果我在結構中有幾個值呢？ – 2011-05-30 18:16:08

@Melvin對於某些值大小，更改指針結構時交換值變得效率較低。確切點取決於你的平臺和用例。 – 2011-05-30 18:17:59

如果您更換nexts，您必須考慮各種特殊情況。這使它比改變value s慢一點點。如果你的值有更多的結構，你可以選擇實現next -version或者用指針替換值。

2011-05-30 18:15:26 Howard

回答