csl*_*csl 95
在运行时间期望你不能比O(N log N)做得更好是合理的.
然而,有趣的部分是调查您是否可以就地排序,稳定,最坏情况下的行为等等.
Putty成名的Simon Tatham解释了如何使用合并排序对链表进行排序.他最后总结了以下评论:
与任何自尊排序算法一样,它具有运行时间O(N log N).因为这是Mergesort,最坏情况下的运行时间仍为O(N log N); 没有病理病例.
辅助存储要求很小且不变(即排序例程中的一些变量).由于链接列表与数组的固有不同行为,这种Mergesort实现避免了通常与算法相关的O(N)辅助存储成本.
C中还有一个示例实现,适用于单链接和双链接列表.
正如@JørgenFogh在下面提到的那样,big-O表示法可能会隐藏一些常数因素,这些因素会导致一个算法由于内存局部性而更好地执行,因为项目数量较少等.
Jør*_*ogh 70
根据许多因素,将列表复制到数组然后使用Quicksort实际上可能会更快.
这可能更快的原因是数组具有比链表更好的缓存性能.如果列表中的节点分散在内存中,则可能会在整个位置生成缓存未命中.然后,如果数组很大,你仍然会得到缓存未命中.
Mergesort更好地并行化,因此如果您想要的话,它可能是更好的选择.如果直接在链表上执行它也会快得多.
由于两种算法都在O(n*log n)中运行,因此做出明智的决定将涉及在您想要运行它们的机器上对它们进行分析.
---编辑
我决定测试我的假设并写了一个C程序,它测量了clock()对一组链接列表进行排序的时间(使用).我尝试了一个链接列表,其中每个节点都被分配了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,所以缓存非常重要.
小智 6
这是关于这个主题的一篇很好的小论文.他的实证结论是Treesort是最好的,其次是Quicksort和Mergesort.沉积物排序,冒泡排序,选择排序表现非常糟糕.
Ching-Kuang Shene的链接列表排序算法比较研究
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.9981
如上所述,基于比较的一般数据排序的下限将是O(n log n).简要地重新阐述这些论点,有n!列表可以排序的不同方式.任何一种有n的比较树!(这是为O(n ^ n))的可能最终各种各样的人都需要至少数作为其高度(N!):这给你一个O(日志(N ^ n))的下限,这是O(n记录n).
因此,对于链表上的一般数据,对可以比较两个对象的任何数据起作用的最佳排序将是O(n log n).但是,如果您有一个更有限的工作领域,您可以缩短所需的时间(至少与n成比例).例如,如果使用的是不大于某个值的整数,则可以使用Counting Sort或Radix Sort,因为这些使用您要排序的特定对象以降低与n成比例的复杂性.要小心,虽然,这些添加一些其他的事情要复杂,你可能不考虑(例如,计数排序和基数的是基于你排序,澳数字的大小排序的因素都加(N + K )其中k是Counting Sort的最大数量的大小,例如).
此外,如果您碰巧拥有具有完美哈希的对象(或者至少是以不同方式映射所有值的哈希),您可以尝试对其哈希函数使用计数或基数排序.