80

为什么当 Timsort（根据维基百科）似乎表现得更好时，我大多听说 Quicksort 是最快的整体排序算法？谷歌似乎没有进行任何比较。

4

5 回答 5

58

TimSort 是一个高度优化的归并排序，它比旧归并排序更稳定、更快。

与快速排序相比，它有两个优点：

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

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

以下是 QuickSort 的优势

  1. QuickSort 非常非常简单，即使是高度优化的实现，我们可以在 20 行内写下它的伪代码；
  2. 在大多数情况下，快速排序是最快的；
  3. 内存消耗为 LOG(N)。

目前，Java 7 SDK 实现了 timsort 和一个新的快速排序变体：即 Dual Pivot QuickSort。

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

于 2013-10-25T10:25:14.210 回答
27

或多或少，这与Timsort是一种混合排序算法有关。这意味着虽然它使用的两种底层排序（合并排序和插入排序）对于许多类型的数据都比快速排序更差，但Timsort仅在这样做有利时才使用它们。

在更深层次上，正如Patrick87所说，快速排序是最坏情况的 O(n 2 ) 算法。选择一个好的支点并不难，但保证 O(n log n) 快速排序的代价是平均排序通常较慢。

有关 Timsort 的更多详细信息，请参阅此答案和链接的博客文章。它基本上假设大多数数据已经部分排序，并构造排序数据的“运行”，允许使用合并排序进行有效合并。

于 2011-10-14T16:13:23.560 回答
19

一般来说，快速排序是原始数组的最佳算法。这是由于内存局部性和缓存。

JDK7 对 Object 数组使用 TimSort。对象数组只保存对象引用。对象本身存储在堆中。要比较对象，我们需要从堆中读取对象。这就像从堆的一部分读取一个对象，然后从堆的另一部分随机读取对象。会有很多缓存未命中。我想出于这个原因，内存局部性不再重要。这可能是 JDK 只对 Object 数组使用 TimSort 而不是原始数组的原因。

这只是我的猜测。

于 2014-11-17T02:01:40.230 回答
5

以下是我机器上的基准测试数据（i7-6700 CPU，3.4GHz，Ubuntu 16.04，gcc 5.4.0，参数：SIZE=100000 和 RUNS=3）：

$ ./demo 
Running tests
stdlib qsort time:                 12246.33 us per iteration
##quick sort time:                  5822.00 us per iteration
merge sort time:                    8244.33 us per iteration
...    
##tim sort time:                    7695.33 us per iteration
in-place merge sort time:           6788.00 us per iteration    
sqrt sort time:                     7289.33 us per iteration    
...
grail sort dyn buffer sort time:    7856.67 us per iteration

基准来自 Swenson 的排序项目，他在其中用 C 语言实现了几种排序算法。据推测，他的实现足以具有代表性，但我还没有研究过它们。

所以你真的说不出来。基准数字最多只能保持两年的相关性，然后您必须重复它们。2011 年，当有人问到这个问题时，timsort 可能击败了 qsort waaay，但时代已经改变。或者 qsort 总是最快的，但 timsort 在非随机数据上击败了它。或者 Swenson 的代码不是那么好，一个更好的程序员会扭转局面，有利于 timsort。CFLAGS或者也许我在编译代码时很烂并且没有使用正确的。或者……你明白了。

于 2017-09-24T20:45:36.733 回答
3

如果您需要保持顺序的排序，或者如果您正在对复杂数组（比较基于堆的对象）而不是原始数组进行排序，则 Tim Sort 非常有用。正如其他人所提到的，快速排序从数据的局部性和原始数组的处理器缓存中受益匪浅。

提出了快速排序的最坏情况是 O(n^2) 的事实。幸运的是，您可以使用快速排序实现 O(n log n) 时间的最坏情况。快速排序最坏情况发生在枢轴点是最小值或最大值时，例如当枢轴是已排序数组的第一个或最后一个元素时。

我们可以通过将枢轴设置为中值来实现 O(n log n) 最坏情况快速排序。由于可以在线性时间 O(n) 内找到中值。由于 O(n) + O(n log n) = O(n log n)，这成为最坏情况的时间复杂度。

然而，在实践中，大多数实现发现随机枢轴就足够了，因此不要搜索中值。

于 2019-09-27T04:07:11.250 回答