对链表进行排序的最快算法是什么? [英] What's the fastest algorithm for sorting a linked list?

问题描述

我很好奇 O(n log n) 是否是链表所能做的最好的事情.

I'm curious if O(n log n) is the best a linked list can do.

推荐答案

在运行时间中，期望你不能做得比 O(N log N) 更好是合理的.

It is reasonable to expect that you cannot do any better than O(N log N) in running time.

然而，有趣的部分是调查您是否可以对它进行排序就地、稳定、其最坏情况的行为等.

However, the interesting part is to investigate whether you can sort it in-place, stably, its worst-case behavior and so on.

Putty 成名的 Simon Tatham 解释了如何排序链接合并排序的列表.他最后发表了以下评论:

Simon Tatham, of Putty fame, explains how to sort a linked list with merge sort. He concludes with the following comments:

与任何自尊排序算法一样，它的运行时间为 O(N log N).因为这是Mergesort，最坏情况的运行时间仍然是O(N log N)；没有病理性病例.

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.

辅助存储要求小且恒定(即排序例程中的一些变量).由于链表与数组的固有行为不同，这种 Mergesort 实现避免了通常与算法相关的 O(N) 辅助存储成本.

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 语言实现的示例实现，它适用于单链表和双链表.

There is also an example implementation in C that work for both singly and doubly linked lists.

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

As @Jørgen Fogh mentions below, big-O notation may hide some constant factors that can cause one algorithm to perform better because of memory locality, because of a low number of items, etc.

这篇关于对链表进行排序的最快算法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！