實現鏈接列表的快速排序？

我需要使用除插入排序之外的任何東西來對雙重鏈接列表進行排序，該排序也運行在更好的時間，然後O（n^2）。我正在考慮使用快速排序，但在理解算法時遇到問題。你能否指出我可以幫助我開始的任何易於理解的文檔？實現鏈接列表的快速排序？

[視頻使用Hungerian民族舞快速排序的可視化的]（http://www.youtube.com/watch?v=ywWBy6J5gz8）的算法的一個極好的高級描述。 – 2012-03-26 22:24:05

您是否允許將其提取到不同的數據結構中以對其進行排序，或者您是否需要對其進行排序？提取到一個數組，執行快速排序，並放回到鏈表中應該是2n + nlogn，它仍然小於n平方。 – captncraig 2012-03-26 22:25:37

不，我不能使用任何其他數據結構來存儲節點。 – 2012-03-26 22:29:19

我實際上會推薦一個merge sort。它感覺像雙鏈表更有意義，它具有O（n log n）的運行時間。基本上，你會找到中間的東西，並將列表分成兩半，每半個人排列一次，然後將兩者按線性時間組合。

有一個線程here在C++中有一個很好的工作實現，如果你正在學習java，可能不是最容易閱讀的，但可能是一個很好的起點。

還有一個在this site.

2012-03-27 16:08:51 captncraig

重要的一點是*最差情況*運行時也是'O（n * log n）'，與快速排序相反。此外，它很容易實現:) – 2012-03-27 16:11:19

回答