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

EN

这是一篇关于这个主题的很好的小论文。他的经验结论是Treesort是最好的，其次是Quicksort和Mergesort。沉淀物排序、冒泡排序、选择排序的性能非常差。

Ching-Kuang Shene链表排序算法的比较研究

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.9981

比较排序(即基于比较元素的排序)不可能比n log n快。底层数据结构是什么并不重要。参见Wikipedia。

其他类型的排序利用列表中有许多相同的元素(例如计数排序)，或者列表中元素的一些预期分布，速度更快，尽管我想不出任何在链表上工作得特别好的排序。

正如多次提到的，对一般数据进行基于比较的排序的下限将是O(n log n)。简单地总结一下这些论点，有n！列表可以以不同的方式排序。任何类型的比较树，具有n！(在O(n^n)中)可能的最终排序至少需要log(n!)作为它的高度:这给出了一个O( log (n^ n) )的下界，即O(n Log N)。

因此，对于链表上的一般数据，对任何可以比较两个对象的数据的最佳排序将是O(n log n)。然而，如果你有一个更有限的工作领域，你可以改善它所需的时间(至少与n成比例)。例如，如果您正在处理不大于某个值的整数，您可以使用Counting Sort或Radix Sort，因为这些对象使用您要排序的特定对象来降低复杂度，并与n成比例。但是，请注意，这会增加一些您可能没有考虑到的复杂性(例如，计数排序和基数排序都会添加基于要排序的数字大小的因子，例如，O(n+k)，其中k是计数排序的最大数的大小)。

此外，如果您碰巧有一个完美散列的对象(或者至少有一个以不同方式映射所有值的散列)，您可以尝试对它们的散列函数使用计数或基数排序。