什么是最快的算法进行排序的链接列表？ [英] 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日​​志N）中的运行时间的。

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

不过，最有趣的部分是调查，如果你能排序就地，的stably ，最坏情况下的行为等。

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

西蒙·泰胜中，腻子成名，介绍了如何排序链表合并排序。他最后提出了以下意见：

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

像任何自我尊重的排序算法，这已运行时间为O（N日志N）。因为这是归并，运行时间最坏情况下仍然是O（N日志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.

辅助存储要求是小而恒定（即几内的排序例程变量）。由于从数组链表的本质不同的行为，该归并的实施避免了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.

如下@耶尔·福格·提到，大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屋！