采访中有人问我这个问题。它们都是O(nlogn)，但是大多数人使用Quicksort而不是Mergesort。这是为什么？

解决方案

回答

实际上，QuickSort是O(n2)。它的平均运行时间为O(nlog(n))，但最差的运行时间为O(n2)，这是在包含很少唯一项目的列表上运行时发生的。随机化为O(n)。当然，这不会改变最坏的情况，它只是防止恶意用户使排序花费很长时间。

QuickSort之所以受欢迎，是因为它：

• 是就地的(MergeSort需要额外的内存与要排序的元素数量成线性关系)。
• 有一个小的隐藏常数。

回答

Quicksort是实践中最快的排序算法，但由于存在许多病理情况，因此其性能可能与O(n2)一样差。

保证Heapsort在O(n * ln(n))中运行，并且仅需要有限的添加存储。但是，现实世界中的许多测试表明，平均而言，堆排序要比快速排序慢得多。

回答

Quicksort具有更好的平均案例复杂性，但是在某些应用程序中，这是错误的选择。 Quicksort容易受到拒绝服务攻击。如果攻击者可以选择要分类的输入，则他可以轻松构建一个集合，该集合的时间复杂度为o(n ^ 2)。

Mergesort的平均大小写复杂度和最坏情况的复杂度是相同的，因此不会遇到相同的问题。正是由于没有病态的情况下，合并排序的这种特性也使其成为实时系统的绝佳选择，因此运行速度要慢得多。

由于这些原因，我比Mergesort更喜欢Mergesort。

回答

从Quicksort上的Wikipedia条目中：

Quicksort also competes with
  mergesort, another recursive sort
  algorithm but with the benefit of
  worst-case Θ(nlogn) running time.
  Mergesort is a stable sort, unlike
  quicksort and heapsort, and can be
  easily adapted to operate on linked
  lists and very large lists stored on
  slow-to-access media such as disk
  storage or network attached storage.
  Although quicksort can be written to
  operate on linked lists, it will often
  suffer from poor pivot choices without
  random access. The main disadvantage
  of mergesort is that, when operating
  on arrays, it requires Θ(n) auxiliary
  space in the best case, whereas the
  variant of quicksort with in-place
  partitioning and tail recursion uses
  only Θ(logn) space. (Note that when
  operating on linked lists, mergesort
  only requires a small, constant amount
  of auxiliary storage.)

回答

维基百科的解释是：

Typically, quicksort is significantly faster in practice than other Θ(nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data it is possible to make design choices which minimize the probability of requiring quadratic time.

快速排序

合并排序

我认为Mergesort所需的存储量(即(n))也存在一些问题，而quicksort实施则没有。在最坏的情况下，它们的算法时间相同，但是mergesort需要更多的存储空间。

回答

虽然它们都在同一复杂度类中，但这并不意味着它们都具有相同的运行时。 Quicksort通常比mergesort快，这是因为编写紧凑的实现更容易，而且它执行的操作可以更快。这是因为快速排序通常使人们使用它而不是合并排序更快。

然而！我个人经常会使用mergesort或者quicksort变体，当quicksort表现不佳时会降级为mergesort。记住。 Quicksort平均仅为O(n log n)。最坏的情况是O(n ^ 2)！合并排序始终为O(n log n)。如果必须具有实时性能或者响应能力，并且输入数据可能来自恶意源，则不应使用简单的快速排序。

回答

我想补充一下到目前为止提到的三个算法(mergesort，quicksort和堆排序)，只有mergesort是稳定的。也就是说，对于具有相同键的那些值，顺序不会更改。在某些情况下，这是理想的。

但是，说实话，在实际情况下，大多数人只需要良好的平均表现，而quicksort是... quick =)

所有排序算法都有其起伏。请参阅Wikipedia文章中有关排序算法的文章，以获取很好的概述。

回答

亩！
Quicksort并不是更好，它比mergesort更适合于其他类型的应用程序。

Mergesort is worth considering if speed is of the essence, bad worst-case performance cannot be tolerated, and extra space is available.1

我们说他们？他们都是O(nlogn)[]？这是错误的。 ？在最坏的情况下，Quicksort使用大约n ^ 2/2的比较。

但是，根据我的经验，最重要的属性是在使用带有命令式范式的编程语言时在排序时可以轻松使用顺序访问。

1 Sedgewick，算法

回答

Quicksort具有O(n2)最坏情况运行时和O(nlogn)平均情况运行时。但是，它在许多情况下优于合并排序，因为有许多因素会影响算法的运行时间，并且综合考虑这些因素时，快速排序将胜出。

特别地，经常引用的排序算法的运行时是指执行比较或者对数据进行排序所需的交换次数。这确实是性能的一个很好的衡量标准，尤其是因为它独立于底层硬件设计。但是，其他因素(例如参考位置)(即我们是否读取了很多可能在缓存中的元素？)在当前硬件上也起着重要作用。特别是Quicksort，几乎不需要额外的空间，并且具有良好的缓存局部性，因此在许多情况下，它比合并排序要快。

此外，它很容易避免的快速排序最坏情况下的运行时间为O(N2)几乎完全通过枢轴的一个合适的选择？例如随机选择(这是一种极好的策略)。

实际上，quicksort的许多现代实现(尤其是libstdc ++的std :: sort`)实际上都是内省型，其理论上最坏的情况是O(nlogn)，与合并排序相同。它通过限制递归深度并在超过logn时切换到其他算法(堆排序)来实现此目的。

回答

动画排序算法在4种不同的初始条件(随机，几乎排序，反向，很少唯一)上显示了许多算法，可能会有所帮助。

回答

Quicksort并不比mergesort好。使用O(n ^ 2)(最罕见的情况，很少发生)，快速排序可能比合并排序的O(nlogn)慢得多。 Quicksort的开销较小，因此对于n较小且速度较慢的计算机，它会更好。但是今天的计算机是如此之快，以至于合并排序的额外开销可以忽略不计，而且非常慢的快速排序的风险在大多数情况下远远超过合并排序的无关紧要的开销。

此外，合并排序还可以使项目按其原始顺序具有相同的键，这是一个有用的属性。

回答

在c / c ++领域中，当不使用stl容器时，我倾向于使用quicksort，因为它是内置的
进入运行时，而mergesort不是。

因此，我认为，在许多情况下，这只是阻力最小的途径。

此外，对于整个数据集不适合工作集的情况，使用快速排序可以提高性能。

回答

正如其他人指出的那样，Quicksort的最坏情况是O(n ^ 2)，而mergesort和heapsort保持在O(nlogn)。但是，在一般情况下，这三个都是O(nlogn)。因此，它们在绝大多数情况下都是可比的。

使Quicksort平均更好的原因是，内部循环意味着将多个值与一个值进行比较，而在另外两个值上，每次比较这两个术语都不相同。换句话说，Quicksort进行的读操作是其他两种算法的一半。在现代CPU上，性能在很大程度上取决于访问时间，因此最终Quicksort成为了绝佳的首选。

回答

正如许多人所指出的，Quicksort的平均案例性能要比mergesort更快。但这只有在假设我们有恒定的时间按需访问任何内存时才是正确的。

在RAM中，此假设通常不太差(由于高速缓存，它并不总是正确的，但也不太糟)。但是，如果数据结构足够大，可以驻留在磁盘上，则快速排序会因平均磁盘每秒执行200次随机搜索的事实而被杀死。但是，同一个磁盘没有顺序顺序读取或者写入每秒兆字节数据的麻烦。这正是mergesort所做的。

因此，如果必须在磁盘上对数据进行排序，那么我们真的很想在mergesort上使用一些变体。 (通常，我们先对子列表进行快速排序，然后再将它们合并到某个大小阈值以上。)

此外，如果我们必须对如此大小的数据集执行任何操作，请认真考虑如何避免寻找磁盘。例如，这就是为什么这样的建议，即在数据库中进行大量数据加载之前先删除索引，然后再重建索引，这是标准建议的原因。在加载期间保持索引意味着不断寻找磁盘。相反，如果删除索引，则数据库可以通过以下方式重建索引：首先对要处理的信息进行排序(当然使用mergesort！)，然后将其加载到该索引的BTREE数据结构中。 (BTREE本质上是保持顺序的，因此我们可以从排序的数据集中装入一个，而很少有磁盘寻道。)

在很多情况下，了解如何避免磁盘寻道使我使数据处理作业花费了数小时而不是数天或者数周。

回答

在所有条件都相同的情况下，我希望大多数人使用最方便的方式，这往往是qsort(3)。除了快速排序之外，众所周知，快速排序在数组上也非常快，就像mergesort是列表的常见选择一样。

我想知道的是为什么看到基数或者存储桶排序如此罕见。它们是O(n)，至少在链表上，它所要做的只是将密钥转换为序数的某种方法。 (字符串和浮点数很好用。)

我在想原因与计算机科学的教学有关。我什至不得不向我的算法分析讲师证明，确实有可能比O(n log(n))更快地排序。 (他证明了我们不能比O(n log(n))进行比较排序，这是对的。)

在其他新闻中，浮点数可以按整数排序，但是之后必须将负数转过来。

编辑：
实际上，这是对floats-as-integers进行排序的一种更恶性的方法：http://www.stereopsis.com/radix.html。请注意，无论我们实际使用哪种排序算法，都可以使用位翻转技巧。

回答

"但是大多数人使用Quicksort而不是Mergesort。为什么会这样？"

尚未给出的心理原因之一就是Quicksort的命名更加巧妙。即良好的营销。

是的，具有三重分割的Quicksort可能是最好的通用排序算法之一，但是" Quick"排序听起来比" Merge"排序强大得多。