我想知道如何在單鏈表上實現氣泡排序。比方說,例如,我們有列表,它包含以下節點:鏈接列表氣泡排序
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