排序链接列表的最佳方式是什么？

-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

排序链接列表的最佳方式是什么？

回答

相关问题