从维基百科上阅读这篇关于排序算法的文章，smoothsort 似乎是最好的排序算法。它在所有类别中都具有最佳性能：最佳、平均和最差。在任何类别中都没有什么能比得上它。它还具有恒定的内存要求。唯一的缺点是不稳定。
它在内存方面胜过 timsort，在最坏情况下的性能和内存方面都胜过 quicksort。
但我从来没有听说过smoothsort。没有人提到它，而且大多数讨论似乎都围绕着其他排序算法。
这是为什么？
问问题
9135 次
3 回答
34
Big-O 性能非常适合发表论文，但在现实世界中，我们也必须查看常量。长期以来，快速排序一直是不稳定、就地、内存中排序的首选算法，因为我们可以非常有效地实现它的内部循环，并且它对缓存非常友好。即使您可以像快速排序一样高效或几乎同样高效地实现平滑排序的内循环，您也可能会发现它的缓存未命中率使其变慢。
我们通过花更多的精力选择好的支点（以减少病理病例的数量）和检测病理病例来减轻快速排序的最坏情况性能。查找introsort。Introsort 首先运行快速排序，但如果检测到过度递归（这表明快速排序的病态情况），则切换到堆排序。
于 2012-12-22T09:22:08.047 回答
9
更好的渐近并不意味着更好的性能（尽管通常结果如此）。隐藏常数可能大几倍，导致在相对较小的数组（实际上，相对较小的数组可能是任意大小，10 100，对于例子。那是渐近分析）。但我对平滑排序隐藏常量一无所知。
例如，有一个 O(n) 最坏情况时间算法来查找 k 阶统计量，但它非常复杂，以至于 O(n log n) 最坏情况版本在大多数情况下都优于它。
此外，还有一个有趣的比较：
…如您所见，Timsort 和 Smoothsort 都没有切芥末。Smoothsort 在所有情况下都比 STL 排序差（即使将 std:bitset 替换为原始位操作）......</p>
于 2012-12-22T09:14:32.147 回答
1
好吧，首先我要说的是，它不像 Smoothsort 没有名气。这取决于用户的需要，也取决于用户是否使用它。
平滑排序的优点是，如果输入已经排序到某种程度，它会更接近 O(n) 时间，而不管初始排序状态如何，堆排序平均 O(n log n)。
从文档中： -
平滑排序算法需要能够在内存中保存字符串中所有堆的大小。由于所有这些值都是不同的，因此通常使用位向量来完成。此外，由于序列中最多有 O(log n) 个数，因此这些位可以用 O(1) 个机器字编码，假设是跨二分机器模型。
于 2012-12-22T08:36:20.933 回答