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

Question

我很好奇 O(n log n) 是否是链表的最佳性能。

Answer 1

有理由期​​望您在运行时间 内不能比 O(N log N) 做得更好。

然而，有趣的部分是调查您是否可以对它进行排序in-place , stably ，其最坏情况下的行为等等。

以 Putty 闻名的 Simon Tatham 解释了如何 sort a linked list with merge sort .他总结了以下评论:

Like any self-respecting sort algorithm, this has running time O(N log N). Because this is Mergesort, the worst-case running time is still O(N log N); there are no pathological cases.

Auxiliary storage requirement is small and constant (i.e. a few variables within the sorting routine). Thanks to the inherently different behaviour of linked lists from arrays, this Mergesort implementation avoids the O(N) auxiliary storage cost normally associated with the algorithm.

还有一个用 C 编写的示例实现，它适用于单链表和双向链表。

正如@Jørgen Fogh 在下面提到的，大 O 表示法可能隐藏了一些常量因素，这些因素可能会导致一种算法由于内存局部性、项目数量少等原因而表现更好。