timsort和quicksort的比较

Question

为什么我经常听说 Quicksort 是最快的整体排序算法，根据 Wikipedia ，Timsort 好像表现好多了？

Answer 1

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

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

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

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

QuickSort 的优点如下：

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

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

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

Answer 2

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

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

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

Answer 3

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

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

这只是我的猜测。

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 实现了多种排序算法。 大概，他的实现足够好，具有代表性，但我还没有调查它们。

所以你真的说不出来。基准数据最多只能保持两年的相关性，然后你就必须重复它们。也许早在 2011 年提出这个问题时，timsort 就击败了 qsort waaay，但时代已经变了。或者 qsort 总是最快的，但 timsort 在非随机数据上击败了它。或者 Swenson 的代码不太好，更好的程序员会扭转局势，对 timsort 有利。或者也许我很糟糕，在编译代码时没有使用正确的 CFLAGS 。或者...你明白了。

Answer 6

Timsort 是一种流行的混合排序算法，由 Tim Peters 于 2002 年设计。它是插入排序和归并排序的结合。它的开发是为了在各种现实世界数据集上表现良好。它是一种快速、稳定和自适应的排序技术，平均和最坏情况下的性能为 O(n log n)。

Timsort 的工作原理

1. 首先，输入数组被分成称为 Run 的子数组/块。
2. 使用简单的插入排序对每个运行进行排序。
3. 合并排序用于将排序后的运行合并到单个数组中。

Timsort的优点

• 它在接近有序的数据上表现更好。
• 它非常适合处理现实世界的数据。

快速排序是一种非常有用且高效的排序算法，它将大量数据划分为较小的数据，它基于分而治之的概念。 Tony Hoare 在 1959 年设计了这种排序算法，平均性能为 O(n log n)。

快速排序的工作原理

1. 选择任意元素作为基准。
2. 根据主元将数组划分为多个分区。
3. 递归地将快速排序应用于左侧分区。
4. 递归地将快速排序应用于正确的分区。

Quicksort 的优点

• 与 Timsort 相比，它在随机数据上的表现更好。
• 当可用空间有限时，它非常有用。
• 它更适合大型数据集。