排序链表最快的算法是什么？

Question

我很好奇O（n log n）是否是链表可以做的最好的事情。

Answer 1

可以合理地预期，在运行时您不能做得比O（N log N）好。

但是，有趣的部分是研究您是否可以就地，稳定地对其进行排序，其最坏情况下的行为等等。

Putty名气的Simon Tatham解释了如何使用merge sort对链表进行排序。他总结了以下评论：

像任何自重排序算法一样，它的运行时间为O（N log N）。因为这是Mergesort，所以最坏情况下的运行时间仍然是O（N log N）。没有病理病例。

辅助存储需求小且恒定（即排序例程中的一些变量）。由于数组中链表的本质不同，Mergesort实现避免了通常与算法相关的O（N）辅助存储成本。

C语言中还有一个示例实现，可用于单链表和双链表。

就像@JørgenFogh在下面提到的那样，big-O表示法可能会隐藏一些恒定因素，这些因素可能会导致一种算法由于内存局部性，项目数量少等原因而表现更好。

Answer 2

根据许多因素，将列表复制到数组然后使用Quicksort实际上可能更快。

之所以会更快，是因为数组的缓存性能要比链表好得多。如果列表中的节点分散在内存中，则可能是整个地方都生成高速缓存未命中。再说一次，如果数组很大，无论如何都会遇到缓存未命中的情况。

Mergesort可以更好地并行化，因此如果您要这样做，可能是更好的选择。如果直接在链接列表上执行它，则速度也更快。

由于这两种算法都在O（n * log n）中运行，因此要做出明智的决定，就需要在要运行它们的计算机上对它们进行性能分析。

-编辑

我决定检验我的假设，并编写了一个C程序，该程序测量（使用clock()）对一个int链接列表进行排序所花费的时间。我尝试了一个分配有每个节点malloc()的链表和一个将节点线性排列在一个数组中的链表，因此缓存性能会更好。我将它们与内置的qsort进行了比较，后者包括将所有内容从碎片列表复制到数组，然后将结果再次复制回去。每种算法都在相同的10个数据集上运行，并对结果取平均值。

结果如下：

N = 1000：

带有合并排序的片段列表：0.000000秒

qsort数组：0.000000秒

合并排序的装箱单：0.000000秒

N = 100000：

具有合并排序的片段列表：0.039000秒

带qsort的数组：0.025000秒

合并排序的装箱单：0.009000秒

N = 1000000：

带有合并排序的片段列表：1.162000秒

带qsort的数组：0.420000秒

合并排序的装箱单：0.112000秒

N = 100000000：

具有合并排序的片段列表：364.797000秒

带qsort的数组：61.166000秒

带合并排序的装箱清单：16.525000秒

结论：

至少在我的机器上，复制到数组中以提高缓存性能非常值得，因为在现实生活中很少有完全打包的链表。应该注意的是，我的机器有一个2.8GHz的Phenom II，但是只有0.6GHz的RAM，因此缓存非常重要。

Answer 3

如许多次所述，一般数据的基于比较的排序的下限将为O（n log n）。为了简要地概括这些参数，有n！列表的不同排序方式。任何具有n的比较树！（位于O（n ^ n）中）可能的最终排序将至少需要log（n！）作为其高度：这为您提供了O（log（n ^ n））下限，即O（n登录n）。

因此，对于链表上的常规数据，将对所有可以比较两个对象的数据进行处理的最佳排序将是O（n log n）。但是，如果您要处理的工作域更有限，则可以缩短所需时间（至少与n成正比）。例如，如果您使用的整数不大于某个值，则可以使用Counting Sort或Radix Sort，因为它们使用要排序的特定对象来降低与n成正比的复杂度。不过请注意，这些会增加您可能不会考虑的复杂性（例如，Counting Sort和Radix sort都添加基于您要排序的数字的大小的因子O（n + k） ），其中k是例如“计数排序”的最大数字的大小）。

另外，如果碰巧具有完美散列的对象（或至少具有不同映射所有值的散列），则可以尝试在其散列函数上使用计数或基数排序。