timsort和quicksort之间的比较

Question

为什么当timsort(根据维基百科)表现得更好时,我大多听说quicksort是最快的整体排序算法？谷歌似乎没有发现任何比较.

Answer 1

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和一个新的快速排序变体:即Dual Pivot QuickSort.

如果你需要稳定的排序,请尝试timsort,否则从quicksort开始.

Answer 2

或多或少,它与Timsort是混合排序算法的事实有关.这意味着虽然它使用的两个基础排序(Mergesort和插入排序)对于许多种类的数据都比Quicksort差,但Timsort只在有利的时候才使用它们.

在稍微深一些的层面上,正如Patrick87所述,quicksort是一种最坏情况的O(n ²)算法.选择一个好的支点并不难,但保证O(n log n)快速排序的代价是平均排序通常较慢.

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

Answer 3

一般来说,quicksort是原始数组的最佳算法.这是由于内存位置和缓存.

JDK7使用TimSort for Object数组.对象数组仅包含对象引用.对象本身存储在Heap中.要比较对象,我们需要从堆中读取对象.这就像从一个对象的堆的一部分读取,然后从堆的另一部分随机读取对象.将会有很多缓存未命中.我想因为这个原因记忆局部性不再重要了.这可能是JDK仅使用TimSort for Object数组而不是原始数组的原因.

这只是我的猜测.

Answer 4

如果您需要保留顺序的排序，或者您要对复杂数组（比较基于堆的对象）而不是原始数组进行排序，那么 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)，这成为最坏情况的时间复杂度。

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

Answer 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的sort项目，在该项目中他用C语言实现了几种排序算法。想必，他的实现足以代表用户，但我尚未对其进行研究。

所以你真的不知道。基准数字最多只保持两年有效，然后您必须重复它们。当问到这个问题时，timsort可能在2011年击败了qsort waaay，但时代已经变了。或者qsort总是最快的，但timsort在非随机数据上胜过它。否则，Swenson的代码不是很好，而一个更好的程序员会逆转timsort的潮流。也许我CFLAGS在编译代码时很烂，没有使用正确的代码。或者...你明白了。