什么是sorting链接列表最快的algorithm？
我很好奇，如果O（N日志）是最好的链表可以做的。
期望在运行时间内不能比O（N log N）做得更好是合理的。
然而，有趣的部分是调查你是否可以在原地 ， 稳定地sorting，最坏的情况下等等。
Putty名声中的Simon Tatham解释了如何使用合并sorting对链表进行sorting 。 他总结了以下意见：
像任何自尊的sortingalgorithm一样，它的运行时间为O（N log N）。 因为这是Mergesort，所以最差的运行时间仍然是O（N log N）。 没有病理情况。
辅助存储的要求很小且不变（即在sorting例程中有几个variables）。 由于数组链表的固有不同行为，Mergesort实现避免了与algorithm相关的O（N）辅助存储成本。
C中还有一个示例实现，可用于单向和双向链表。
正如@JørgenFogh在下面提到的，大O符号可能会隐藏一些常量因素，这些因素可能会导致一个algorithm由于内存局部性而更好地执行，因为项目数量较less等。
根据多种因素，将列表复制到数组然后使用Quicksort可能会更快。
这可能会更快的原因是一个数组比链接列表有更好的caching性能。 如果列表中的节点分散在内存中，则可能会在整个地方生成caching未命中。 然后再次，如果数组很大，反正会得到caching未命中。
Mergesort并行更好，所以如果这是你想要的，它可能是一个更好的select。 如果直接在链表上执行，速度也会更快。
由于两种algorithm都以O（n * log n）运行，因此做出明智的决定将涉及在您希望运行它们的计算机上对其进行分析。
—编辑
我决定testing一下我的假设，写了一个C程序来测量时间（使用clock() ）来对一个链表进行sorting。 我尝试了一个链接列表，其中每个节点都分配了malloc()和一个链接列表，其中的节点按照线性排列在一个数组中，所以caching性能会更好。 我将它们与内置的qsort进行了比较，其中包括将碎片列表中的所有内容都复制到一个数组中，然后再次将结果复制回来。 每个algorithm在相同的10个数据集上运行，结果取平均值。
这是结果：
N = 1000：
合并sorting的分段列表：0.000000秒
具有qsort的数组：0.000000秒
打包列表与合并sorting：0.000000秒
N = 100000：
合并sorting的碎片列表：0.039000秒
arrays与qsort：0.025000秒
打包列表合并sorting：0.009000秒
N = 1000000：
合并sorting的碎片列表：1.162000秒
arrays与qsort：0.420000秒
打包列表合并sorting：0.112000秒
N = 100000000：
合并sorting的碎片列表：364.797000秒
arrays与qsort：61.166000秒
打包列表合并sorting：16.525000秒
结论：
至less在我的机器上，复制到一个数组对于提高caching性能是非常值得的，因为在现实生活中很less有完整的链接列表。 需要说明的是，我的机器有2.8GHz的Phenom II，但是只有0.6GHz的RAM，所以caching非常重要。
比较sorting（即基于比较元素的sorting）不可能比n log n更快。 不pipe底层的数据结构是什么。 参见维基百科 。
其他types的利用列表中有很多相同的元素（比如计数sorting），或者列表中元素的一些预期分布，速度更快，尽pipe我想不出任何特别好的工作在一个链表上。
如前所述，基于比较的一般数据sorting的下界将是O（n log n）。 简要回顾这些论点，有n！ 列表可以按不同的方式sorting。 任何一种比较树都有n！ （这是在O（n ^ n））可能的最后sorting将需要至lesslog（n！）作为其高度：这给你一个O（log（n ^ n））的下界，这是O（n日志n）。
因此，对于链表上的一般数据，对可以比较两个对象的任何数据进行处理的最佳sorting是O（n log n）。 然而，如果你有一个更有限的领域的工作，你可以改善所需的时间（至less与n成正比）。 例如，如果使用不大于某个值的整数，则可以使用Counting Sort或Radix Sort ，因为它们使用您正在sorting的特定对象来降低与n成比例的复杂度。 但要小心，这些添加一些其他的事情，你可能不会考虑的复杂性（例如，计数sorting和基数sorting都添加基于您正在sorting的数字大小的因素，O（n + k ）其中k是Counting Sort的最大数量的大小）。
另外，如果碰巧有一个完美散列的对象（或者至less是一个哈希，它将不同的值映射到所有的值），你可以尝试在它们的散列函数上使用计数或基数sorting。
这是一个关于这个话题的不错的小论文。 他的实证结论是，树木是最好的，其次是Quicksort和Mergesort。 泥沙分类，冒泡sorting，selectsortingperformance非常糟糕。
清光县链接列表分类algorithm的比较研究
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.9981
基数sorting特别适用于链接列表，因为很容易制作与数字的每个可能值相对应的头指针表。
合并sorting不需要O（1）访问，并且是O（n ln n）。 没有已知的sorting一般数据的algorithm比O（n ln n）好。
只要你使用一个不同的O（1）访问结构作为临时存储，那么诸如基数sorting（限制数据大小）或者直方图sorting（统计离散数据）等特殊数据algorithm就可以对具有较低增长函数的链表进行sorting。
另一类特殊数据是几乎sorting的k元素无序列表的比较sorting。 这可以在O（kn）操作中进行sorting。
将列表复制到数组并返回将是O（N），因此如果空间不是问题，则可以使用任何sortingalgorithm。
例如，给定一个包含uint_8 ，这个代码将使用直方图sorting在O（N）时间sorting：
#include <stdio.h> #include <stdint.h> #include <malloc.h> typedef struct _list list_t; struct _list { uint8_t value; list_t *next; }; list_t* sort_list ( list_t* list ) { list_t* heads[257] = {0}; list_t* tails[257] = {0}; // O(N) loop for ( list_t* it = list; it != 0; it = it -> next ) { list_t* next = it -> next; if ( heads[ it -> value ] == 0 ) { heads[ it -> value ] = it; } else { tails[ it -> value ] -> next = it; } tails[ it -> value ] = it; } list_t* result = 0; // constant time loop for ( size_t i = 255; i-- > 0; ) { if ( tails[i] ) { tails[i] -> next = result; result = heads[i]; } } return result; } list_t* make_list ( char* string ) { list_t head; for ( list_t* it = &head; *string; it = it -> next, ++string ) { it -> next = malloc ( sizeof ( list_t ) ); it -> next -> value = ( uint8_t ) * string; it -> next -> next = 0; } return head.next; } void free_list ( list_t* list ) { for ( list_t* it = list; it != 0; ) { list_t* next = it -> next; free ( it ); it = next; } } void print_list ( list_t* list ) { printf ( "[ " ); if ( list ) { printf ( "%c", list -> value ); for ( list_t* it = list -> next; it != 0; it = it -> next ) printf ( ", %c", it -> value ); } printf ( " ]\n" ); } int main ( int nargs, char** args ) { list_t* list = make_list ( nargs > 1 ? args[1] : "wibble" ); print_list ( list ); list_t* sorted = sort_list ( list ); print_list ( sorted ); free_list ( list ); }
不是您的问题的直接答案，但如果您使用跳过列表 ，它已经sorting并具有O（日志N）search时间。
据我所知，无论容器如何，最好的sortingalgorithm是O（n * log n） – 已经certificate广义的sorting（mergesort / quicksort等等）不能越低越好。 使用链表不会给你一个更好的运行时间。
在O（n）中运行的唯一一种algorithm是依靠计数值而不是实际sorting的“黑客”algorithm。
Mergesort是你可以在这里做的最好的。
这是一个遍历列表一次的实现，收集运行，然后按照mergesort相同的方式安排合并。
复杂性是O（n log m），其中n是项目数量，m是运行次数。 最好的情况是O（n）（如果数据已经sorting），最坏的情况是O（n log n）。
它需要O（log m）临时内存; sorting在列表上就地完成。
（更新如下，评论者在这里描述一个很好的观点）
algorithm的要点是：
while list not empty accumulate a run from the start of the list merge the run with a stack of merges that simulate mergesort's recursion merge all remaining items on the stack
积累运行并不需要太多的解释，但是利用这个机会积累上升运行和下降运行（颠倒）是很好的。 在此，它预先比运行的头部更小的项目，并附加大于或等于运行结束的项目。 （请注意，预先应该使用严格的小于，以保持sorting的稳定性。）
在这里粘贴合并代码是最简单的：
int i = 0; for ( ; i < stack.size(); ++i) { if (!stack[i]) break; run = merge(run, stack[i], comp); stack[i] = nullptr; } if (i < stack.size()) { stack[i] = run; } else { stack.push_back(run); }
考虑sorting列表（dagibecfjh）（忽略运行）。 堆栈状态如下进行：
[ ] [ (d) ] [ () (ad) ] [ (g), (ad) ] [ () () (adgi) ] [ (b) () (adgi) ] [ () (be) (adgi) ] [ (c) (be) (adgi ) ] [ () () () (abcdefgi) ] [ (j) () () (abcdefgi) ] [ () (hj) () (abcdefgi) ]
然后，最后，合并所有这些列表。
请注意，堆栈[i]中的项目数（运行）为零或2 ^ i，堆栈大小以1 + log2（nruns）为界。 每个元素在每个堆栈级别合并一次，因此O（n log m）比较。 Timsort在这里有一个类似的Timsort，尽pipeTimsort使用类似Fibonacci序列的东西来维护它，这里使用了两个幂。
累积运行利用了任何已经sorting的数据，因此对于已经sorting的列表（一次运行），最好的情况复杂度是O（n）。 由于我们正在累计升序和降序运行，因此运行总是至less为2（这会将最大堆栈深度减less至less一个，支付首先查找运行的代价）。最差的情况复杂度是如预期的那样，O（n log n）用于高度随机化的数据。
（嗯…第二次更新。）
或者只是看到自下而上的mergesort维基百科。
