timsort和quicksort之间的比较

• Z时代
• 2024-01-10
• 分类：问答

当Timsort（根据Wikipedia）的性能似乎好得多时，为什么我最常听说Quicksort是最快的整体排序算法？Google似乎没有进行任何比较。

回答：

TimSort是高度优化的mergesort，它比旧的mergesort稳定且速度更快。

与quicksort相比，它有两个优点：

1. 对于几乎排序的数据序列（包括反向排序的数据），它的速度令人难以置信。
2. 最坏的情况仍然是O（N * LOG（N））。

老实说，我认为＃1并不是优势，但确实给我留下了深刻的印象。

这是QuickSort的优势

1. QuickSort非常非常简单，即使是高度优化的实现，我们也可以在20行内写下其pseduo代码；
2. 在大多数情况下，QuickSort最快。
3. 内存消耗为LOG（N）。

当前，Java 7 SDK实现了timsort和一个新的quicksort变体：Dual Pivot QuickSort。

如果您需要稳定的排序，请尝试使用timsort，否则请从quicksort开始。

以上是 timsort和quicksort之间的比较 的全部内容， 来源链接： utcz.com/qa/424161.html