为什么我大多数时候听说快速排序是最快的整体排序算法，但根据维基百科，Timsort似乎表现更好？
Timsort和快速排序的比较
87
- chenglou
9
36因为人们选择忽略快速排序在最坏情况下的时间复杂度为O(n^2)。 - Patrick87
5可能的答案之一是：“你和错误的人说话了。” 但正如其他答案已经暗示的，qsort更古老，因此在更多的库中使用 - 而且你知道：不要碰一个正在运行的系统。如果平均运行时间（意思是：在使用它的人的用例中）与不同算法（如timsort）的运行时间差别不大，那么人们通常会太懒惰（或者有更好的事情要做）改变某些在相同时间内完成相同任务的东西。在一些应用程序中（例如Python），timsort已经成为默认算法。 - flolo
2@Patrick87：事实远非如此。你忽略了O(n)的最佳情况。这不是关于基本上从不发生的最坏情况，而是关于实际发生的最佳情况。当timsort遇到一个已排序的范围时，它做得很好。 - Rob Neuhaus
1@RobNeuhaus：我认为（简单实现的）快速排序最糟糕的情况经常发生。只需对已经（几乎）排好序的列表进行排序即可。 - Martin Thoma
4仅对于快速排序的极差实现，排序过的列表才会产生最坏情况的结果。随机或中位数分区选择实现可以避免对于已排序或近乎排序的列表的最坏情况。但它们仍然无法达到Timsort的O(n)行为。 Timsort的稳定性也是人们忽视的一个关键属性。在许多情况下，它非常有用，特别是对于多关键字排序。 - Jeremy West
显示剩余4条评论
6个回答
66
TimSort是一种高度优化的归并排序，它是稳定的，并且比旧的归并排序更快。
与快速排序相比，它有两个优点：
- 对于几乎排序好的数据序列（包括逆序数据），它的速度非常快；
- 最坏情况下的时间复杂度仍然是O(N*LOG(N))。
老实说，我不认为#1是一个优点，但它确实给我留下了深刻的印象。
以下是快速排序的优点：
- 快速排序非常简单，即使是高度优化的实现，我们也可以在20行内写出其伪代码；
- 在大多数情况下，快速排序是最快的；
- 记忆消耗是LOG(N)。
目前，Java 7 SDK实现了timsort和新的快速排序变体：即双轴快速排序。
如果你需要稳定排序，请尝试timsort，否则请从快速排序开始。
- Chang
7
18#1 能够 是一个巨大的优势。如果你需要经常重新排序数据列表（因为有项目被插入、追加或修改），那么拥有一种可以非常便宜地重新排序这些数据的算法是非常有用的。当然，这取决于具体情况，但在某些情况下，它是非常重要的，也很明显：几乎排好序的列表不应该很难排序。 - Jeremy West
8如果你知道数据已经排序，那么插入新值时应该使用二分查找。不要反复进行排序。 - Eric Duminil
19二分查找很快，但在数组中间插入元素则不然。有很多应用场景，最简单（并且通常最有效）的解决方案是在需要排序时重新对大部分已排序的列表进行排序，否则就让它保持未排序状态。或者当您读取大部分已排序的数据，然后需要对其进行排序时。我并不是建议这总是最好的解决方案，但在某些情况下确实是。这也是为什么对于标准库而言，在大部分已排序的列表上表现良好的排序算法更可取的原因之一。 - Jeremy West
4谢谢你的精彩回答。 - Eric Duminil
1@Groo 是的，如果你只是将一个元素插入到已排序的列表中，那是可以的。这并不是我提到的唯一应用。显然，根据你要解决的问题，结果会有所不同。 - Jeremy West
显示剩余2条评论
29
更或者少地说，这与Timsort是一种混合排序算法有关。这意味着虽然它使用的两种基本排序方法（Mergesort和Insertion sort）在许多类型的数据上都不如Quicksort好，但Timsort只在有利时使用它们。
在稍微深入一点的层面上，正如Patrick87所述，快速排序是一种最坏情况下为O(n²)的算法。选择一个好的枢轴并不hard，但保证O(n log n)的快速排序通常会以平均较慢的排序为代价。
有关Timsort的更多细节，请参见this answer和链接的博客文章。它基本上假设大多数数据已经部分排序，并构造了排序数据的“runs”，以便使用mergesort进行高效合并。
在稍微深入一点的层面上，正如Patrick87所述，快速排序是一种最坏情况下为O(n²)的算法。选择一个好的枢轴并不hard，但保证O(n log n)的快速排序通常会以平均较慢的排序为代价。
有关Timsort的更多细节，请参见this answer和链接的博客文章。它基本上假设大多数数据已经部分排序，并构造了排序数据的“runs”，以便使用mergesort进行高效合并。
- brc
22
一般来说，快速排序是适用于原始数组的最佳算法。这是因为它具有内存局部性和高速缓存。
JDK7使用TimSort来处理对象数组。对象数组只保存对象引用，而对象本身存储在堆中。要比较对象，我们需要从堆中读取对象。这就好像从堆的一个部分读取一个对象，然后从另一个部分随机读取对象。这将导致大量的高速缓存未命中。我猜这就是为什么内存局部性不再重要的原因。也许这就是JDK为什么只对对象数组使用TimSort而不对原始数组使用的原因。
这只是我的猜测。
- jason zhang
1
我认为这就是Timsort成为Python标准排序算法的原因之一，因为在Python中一切都是对象。 - Alan Evangelista
6
如果您需要进行保序排序或对复杂数组（比较基于堆的对象）进行排序，那么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)，这成为最坏情况的时间复杂度。
但是在实践中，大多数实现都认为随机选取枢轴就足够了，因此不会搜索中位数。
- MarkE
5
以下是我的计算机（i7-6700 CPU，3.4GHz，Ubuntu 16.04，gcc 5.4.0，参数：SIZE=100000 and RUNS=3）的基准测试数据：
基准测试来自 Swenson 的 sort 项目，他在其中使用 C 实现了几种排序算法。大概，他的实现足够代表性，但我没有调查过。
$ ./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，但是时代已经改变。或者 qsort 总是最快的，但 timsort 在非随机数据上胜过它。或者 Swenson 的代码并不那么好，更好的程序员会使 timsort 更有优势。或者也许是我糟糕透顶，没有在编译代码时使用正确的 CFLAGS。或者...你明白我的意思。
- Björn Lindqvist
4
4Timsort的性能取决于要排序的数据类型：在随机数据上最慢，在排序数据上最快。奇怪的是，这个答案和项目自述文件都没有提到数据的性质。所以我看了看代码，发现数据是随机的。（相比之下，快速排序在大多数情况下具有一致的速度，除了在特制的对抗性情况和实现不良的情况下 - 例如总是将第一个或最后一个元素作为枢轴是大忌）。 - Qwertie
6我想补充一点，Timsort 的目的从来不是要超越 Quicksort，而是成为一种快速的稳定排序算法（Quicksort 不稳定），同时最小化比较操作（在 Python 中这很慢）。然而，当数据已经排好序或接近排好序时，它应该会比 Quicksort 更快。（详见） - Qwertie
你知道Timsort在哪些基准测试中是最快的吗？我反对所有没有基准测试数据支持的性能声明。:) Swenson基准测试使用随机数据的观点很好 - 我没有仔细检查它。 - Björn Lindqvist
2@Qwertie：TimSort对已经（部分）排序的数据的处理也很重要，因为Python没有明显的方法来合并排序的数据，而不明显的方法（
heapq.merge）并不是很高效（其中大部分是用Python而不是C实现的）。因此，合并已经排序的数据或将未排序的数据添加到排序的数据的常见方法是只需执行：sortedlist += newdata; sortedlist.sort()（或一行代码，sortedlist = sorted(sortedlist + newdata)）。如果TimSort不使用现有的排序，则这将非常低效。 - ShadowRanger0
Timsort是一种流行的混合排序算法，由Tim Peters于2002年设计。它结合了插入排序和归并排序。它被开发出来以在各种真实世界的数据集上表现良好。它是一种快速、稳定和自适应的排序技术，平均和最坏情况下的性能为O(n log n)。
Timsort的工作原理
- 首先，输入数组被分成子数组/块，称为Run。
- 使用简单的插入排序对每个Run进行排序。
- 使用归并排序将排序后的Runs合并成一个数组。
Timsort的优点
- 它在几乎有序的数据上表现更好。
- 它非常适合处理真实世界的数据。
Quicksort是一种高效的排序算法，它将大型数据数组分成较小的数组，并基于分治的概念。Tony Hoare于1959年设计了这种排序算法，平均性能为O(n log n)。
Quicksort的工作原理
- 选择任意一个元素作为枢轴。
- 根据枢轴将数组分成若干个子集。
- 对左侧子集递归地应用快速排序。
- 对右侧子集递归地应用快速排序。
快速排序的优点
- 与Timsort相比，在随机数据上表现更好。
- 当空间有限时，它非常有用。
- 它非常适合大型数据集。
- Abdul Alim Shakir
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接