排序鏈接列表的最佳方式是什麼？

-1

2009-11-14 Cory W.

您可能必須指定所需的語言（C或C++），因爲解決方案會有很大差異。 – 2009-11-14 06:28:37

也許約翰可以幫助你：http://stackoverflow.com/questions/1733420/where-can-i-get-cc-sample-code-for-merge-sort-a-link-list – 2009-11-14 07:14:10

這是一個重複http://stackoverflow.com/questions/1525117/whats-the-fastest-algorithm-for-sorting-a-linked-list – 2009-11-14 10:50:19

Merge sort。

更好的是，只需使用std::list及其sort()方法。

來源

2009-11-14 06:24:55

您想詳細說明合併排序的原因嗎？感謝您建議STL，但不能使用它，因爲它是作業 – 2009-11-14 06:27:32

@Cory：三種常見算法（heapsort，quicksort，mergesort）中的這是唯一一個沒有隨機訪問表現很好的人 – Christoph 2009-11-14 09:57:28

合併排序適合排序鏈接列表。一些細節here。樣品C代碼here。

它爲什麼適合？簡而言之，mergesort的主要組件 - 合併排序的子序列 - 可以很容易地在兩個鏈表上完成，因爲它需要比較頭元素，所以它不需要數組的隨機訪問。

此外，這裏有一篇名爲A COMPARATIVE STUDY OF LINKED LIST SORTING ALGORITHMS的文章，您可能會感興趣。

來源

2009-11-14 06:39:06

我不知道爲什麼人們保留鏈接到這個網站 - 實施太糟糕了，因爲它過於複雜並且不必要地遍歷列表;正在使用的算法等同於迭代的基於數組的版本 - 由於這些版本不允許隨機訪問，所以不適合鏈接列表 - 應該用基於堆棧的實現替換;即使香草遞歸的應該更好 – Christoph 2009-11-14 09:45:30

取決於你的意思是「最好的」。你的意思是最快實現，還是最有效的運行時？你正在分類的大小和特徵也起到一定的作用。排序10個項目與排序1000萬個項目可能會導致不同的「最佳」算法。對於「最好」意味着運行速度最快的大型數據集，我喜歡快速排序。

來源

2009-11-14 06:45:40

我想我記得聽說quicksort在排序（或接近排序）的數據上運行速度慢。所以，正如bpv所說，數據的特徵確實在你的決定中扮演着重要的角色。 – ialm 2009-11-14 07:26:44

@veol：一個天真的快速排序運行緩慢，大多數實際的實現使用隨機擺動。 – MAK 2009-11-14 07:30:55

@MAK：好像我在課堂上沒有重視:) – ialm 2009-11-14 08:22:20

基於堆棧的mergesort實現是選擇的武器。

前段時間，我需要對一個雙向鏈表進行排序。維基百科告訴我使用mergesort，因爲它是三種常用通用排序算法（heapsort，mergesort和quicksort）中唯一的一種，在隨機訪問速度較慢並且甚至提供鏈接到Simon Tatham's implementation時性能很好。

首先，我的re-implemented他的算法，這表明它基本上是衆所周知的迭代版本。這是一個糟糕的選擇，因爲它依賴於隨機訪問，因此表現不佳。

recursive version更適合鏈接列表，因爲它只是在分裂時不必要地遍歷其中一個列表，而不是兩者（正如Simon的變體）。

你應該使用的是一個stack-based version，因爲這個實現完全擺脫了不必要的列表遍歷。

來源

2009-11-14 10:15:12 Christoph

這是值得思考如何你到這一點。如果您需要以特定方式對項目進行排序，請考慮將列表保留排序並將它們直接插入排序列表中。這樣你就不需要在需要時對它進行分類。

來源

2009-11-14 11:49:59 Tim

排序鏈接列表的最佳方式是什麼？

回答

相關問題