392

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

4

29 回答 29

313

快速排序具有 O( n 2 ) 最坏情况运行时间和 O( n log n ) 平均情况运行时间。但是，在许多情况下它都优于归并排序，因为许多因素会影响算法的运行时间，并且当将它们放在一起时，快速排序会胜出。

特别是，经常引用的排序算法运行时间是指对数据进行排序所需的比较次数或交换次数。这确实是一个很好的性能衡量标准，特别是因为它独立于底层硬件设计。然而，其他的东西——比如引用的局部性（即我们是否读取了很多可能在缓存中的元素？）——也在当前的硬件上扮演着重要的角色。特别是快速排序需要很少的额外空间并且表现出良好的缓存局部性，这使得它在许多情况下比合并排序更快。

此外，通过使用适当的枢轴选择，几乎可以完全避免快速排序的 O( n 2 ) 最坏情况运行时间——例如随机选择它（这是一个很好的策略）。

在实践中，许多现代的快速排序实现（特别是 libstdc++'s std::sort）实际上是introsort，其理论上的最坏情况是 O( n log n )，与归并排序相同。它通过限制递归深度并在超过 log n时切换到不同的算法（堆排序）来实现这一点。

于 2008-09-16T09:14:24.870 回答
302

正如许多人所指出的，快速排序的平均案例性能比归并排序更快。 但这仅在您假设恒定时间按需访问任何内存时才成立。

在 RAM 中，这个假设通常并不算太糟糕（由于缓存的原因并不总是如此，但也不算太糟糕）。但是，如果您的数据结构足够大，可以存储在磁盘上，那么快速排序会因为您的平均磁盘每秒执行 200 次随机搜索而被扼杀。但是同一个磁盘可以毫无问题地按顺序读取或写入每秒兆字节的数据。这正是合并排序所做的。

因此，如果必须在磁盘上对数据进行排序，那么您真的非常想在合并排序上使用一些变体。（通常你快速排序子列表，然后开始将它们合并到某个大小阈值以上。）

此外，如果您必须对这种大小的数据集做任何事情，请认真考虑如何避免寻找磁盘。例如，这就是为什么标准建议是在数据库中加载大量数据之前删除索引，然后再重建索引。在加载期间维护索引意味着不断地寻找磁盘。相反，如果您删除索引，那么数据库可以通过首先对要处理的信息进行排序（当然使用合并排序！）然后将其加载到索引的 BTREE 数据结构中来重建索引。（BTREE 自然而然地保持有序，因此您可以从已排序的数据集中加载一个，而无需对磁盘进行几次搜索。）

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

于 2008-09-18T06:19:50.607 回答
96

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

快速排序更受欢迎，因为它：

  1. 就地（MergeSort 需要与要排序的元素数量成线性关系的额外内存）。
  2. 有一个小的隐藏常数。
于 2008-09-16T08:41:02.123 回答
34

“然而大多数人使用 Quicksort 而不是 Mergesort。这是为什么呢？”

一个没有给出的心理原因仅仅是 Quicksort 的命名更巧妙。即良好的营销。

是的，具有三重分区的快速排序可能是最好的通用排序算法之一，但无法克服“快速”排序听起来比“合并”排序更强大的事实。

于 2009-11-13T04:53:23.077 回答
21

正如其他人所指出的，快速排序的最坏情况是 O(n^2)，而合并排序和堆排序保持在 O(nlogn)。然而，在平均情况下，这三个都是 O(nlogn)；所以它们在绝大多数情况下都是可比的。

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

于 2008-09-17T02:09:41.417 回答
9

我想补充一下到目前为止提到的三种算法（合并排序、快速排序和堆排序），只有合并排序是稳定的。也就是说，对于那些具有相同键的值，顺序不会改变。在某些情况下，这是可取的。

但是，说实话，在实际情况下，大多数人只需要良好的平均性能，而快速排序是......快速=）

所有排序算法都有其起伏。请参阅Wikipedia 文章以了解排序算法以获得良好的概述。

于 2008-09-16T08:47:45.633 回答
7

来自快速排序的维基百科条目：

快速排序还与合并排序竞争，这是另一种递归排序算法，但具有最坏情况 Θ(nlogn) 运行时间的优势。与快速排序和堆排序不同，合并排序是一种稳定的排序，并且可以很容易地适用于对存储在慢速访问介质（如磁盘存储或网络附加存储）上的链表和非常大的列表进行操作。尽管可以编写快速排序来对链表进行操作，但如果没有随机访问，它通常会受到糟糕的枢轴选择的影响。归并排序的主要缺点是，在对数组进行操作时，它在最佳情况下需要 Θ(n) 辅助空间，而具有就地分区和尾递归的快速排序变体仅使用 Θ(logn) 空间。（请注意，在对链表进行操作时，归并排序只需要少量的、恒定数量的辅助存储。）

于 2008-09-16T08:42:10.967 回答
7

亩！ 快速排序并不好，它非常适合于不同类型的应用程序，而不是合并排序。

如果速度至关重要，不能容忍最坏情况下的糟糕性能，并且有额外空间可用，则 Mergesort 值得考虑。1

你说他们«他们都是 O(nlogn) [...]»。这是错误的。«快速排序在最坏的情况下使用大约 n^2/2 比较。» 1 .

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

1 Sedgewick，算法

于 2008-09-16T09:13:40.597 回答
7

我想在现有的很好的答案中添加一些关于 QuickSort 在偏离最佳情况时如何执行的数学以及这种情况的可能性有多大，我希望这将帮助人们更好地理解为什么 O(n^2) 情况不是真实的关注更复杂的快速排序实现。

除了随机访问问题之外，还有两个主要因素会影响 QuickSort 的性能，它们都与枢轴与被排序数据的比较方式有关。

1）数据中的少量键。所有相同值的数据集将在普通 2 分区 QuickSort 上以 n^2 次排序，因为除了枢轴位置之外的所有值每次都放在一侧。现代实现通过使用 3 分区排序等方法解决了这个问题。这些方法在 O(n) 时间内在所有相同值的数据集上执行。因此，使用这样的实现意味着具有少量键的输入实际上可以提高性能时间并且不再是问题。

2) 极差的枢轴选择会导致最坏情况的性能。在理想情况下，枢轴将始终使 50% 的数据更小，50% 的数据更大，因此在每次迭代期间输入将被分成两半。这给了我们 n 次比较和交换时间 log​​-2(n) 递归 O(n*logn) 时间。

非理想枢轴选择对执行时间有多大影响？

让我们考虑一个始终选择枢轴的情况，使得 75% 的数据位于枢轴的一侧。它仍然是 O(n*logn) 但现在日志的基数已更改为 1/0.75 或 1.33。更改基数时的性能关系始终是由 log(2)/log(newBase) 表示的常数。在这种情况下，该常数为 2.4。因此，这种枢轴选择质量需要的时间是理想值的 2.4 倍。

这种情况恶化的速度有多快？

在枢轴选择变得（始终）非常糟糕之前不会很快：

  • 一侧 50%：（理想情况）
  • 一侧 75%：2.4 倍
  • 一侧 90%：6.6 倍
  • 一侧 95%：13.5 倍
  • 一侧 99%：69 倍

当我们在一侧接近 100% 时，执行的日志部分接近 n，整个执行渐近接近 O(n^2)。

在 QuickSort 的简单实现中，排序数组（对于第一个元素枢轴）或反向排序数组（对于最后一个元素枢轴）等情况将可靠地产生最坏情况的 O(n^2) 执行时间。此外，具有可预测枢轴选择的实现可能会受到旨在产生最坏情况执行的数据的 DoS 攻击。现代实现通过各种方法避免了这种情况，例如在排序前随机化数据，选择 3 个随机选择的索引的中位数等。在混合这种随机化的情况下，我们有 2 种情况：

  • 小数据集。最坏的情况是合理的，但 O(n^2) 不是灾难性的，因为 n 足够小，以至于 n^2 也很小。
  • 大数据集。理论上最坏的情况是可能的，但在实践中是不可能的。

我们看到糟糕表现的可能性有多大？

机会微乎其微。让我们考虑一种 5,000 个值：

我们假设的实现将使用 3 个随机选择的索引的中位数来选择一个枢轴。我们将把 25%-75% 范围内的支点视为“好”，将 0%-25% 或 75%-100% 范围内的支点视为“差”。如果您使用 3 个随机索引的中值查看概率分布，则每次递归都有 11/16 的机会以良好的支点结束。让我们做 2 个保守的（和错误的）假设来简化数学：

  1. 好的支点总是恰好在 25%/75% 的比例上，并在 2.4*理想情况下运行。我们永远不会得到理想的分割或任何比 25/75 更好的分割。

  2. 糟糕的支点总是最坏的情况，基本上对解决方案没有任何帮助。

我们的 QuickSort 实现将在 n=10 处停止并切换到插入排序，因此我们需要 22 个 25%/75% 的枢轴分区才能将 5,000 个值输入分解到那么远。(10*1.333333^22 > 5000) 或者，我们需要 4990 个最坏情况的枢轴。请记住，如果我们在任何时候积累了 22 个好的支点，那么排序就会完成，所以最坏的情况或任何接近它的情况都需要非常糟糕的运气。如果我们需要 88 次递归才能真正实现排序到 n=10 所需的 22 个良好枢轴，那将是 4*2.4*理想情况或理想情况执行时间的大约 10 倍。在 88 次递归之后，我们无法实现所需的 22 个良好枢轴的可能性有多大？

二项式概率分布可以回答这个问题，答案大约是 10^-18。（n 是 88，k 是 21，p 是 0.6875）您的用户在单击 [SORT] 的 1 秒内被闪电击中的可能性大约是他们看到 5,000 个项目排序运行得更糟的一千倍超过 10*理想情况。随着数据集变大，这个机会变小。以下是一些数组大小及其运行时间超过 10*ideal 的相应机会：

  • 640 个项目的数组：10^-13（需要 60 次尝试中的 15 个好的枢轴点）
  • 包含 5,000 个项目的数组：10^-18（需要 88 次尝试中的 22 个好的枢轴）
  • 40,000 个项目的数组：10^-23（需要 116 个中的 29 个好的枢轴）

请记住，这是基于 2 个比现实更糟糕的保守假设。所以实际性能更好，剩余概率的平衡比没有更接近理想。

最后，正如其他人所提到的，如果递归堆栈太深，即使是这些极其不可能的情况也可以通过切换到堆排序来消除。所以 TLDR 是，对于 QuickSort 的良好实现，最坏的情况并不真正存在，因为它已经被设计出来并且执行在 O(n*logn) 时间内完成。

于 2015-09-25T03:50:16.243 回答
6

快速排序是实践中最快的排序算法，但有许多病态情况可能使其性能与 O(n2) 一样糟糕。

堆排序保证在 O(n*ln(n)) 中运行，并且只需要有限的额外存储空间。但是有许多真实世界测试的引用表明堆排序平均比快速排序慢得多。

于 2008-09-16T08:41:30.220 回答
5

维基百科的解释是：

通常，快速排序在实践中比其他 Θ(nlogn) 算法快得多，因为它的内部循环可以在大多数架构上有效地实现，并且在大多数实际数据中，可以做出最小化需要二次时间的概率的设计选择.

快速排序

合并排序

我认为 Mergesort 所需的存储量（即 Ω(n)）也存在快速排序实现所没有的问题。在最坏的情况下，它们的算法时间相同，但归并排序需要更多的存储空间。

于 2008-09-16T08:43:02.540 回答
4

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

此外，合并排序会以原始顺序保留具有相同键的项目，这是一个有用的属性。

于 2008-09-16T22:29:46.080 回答
4

为什么快速排序很好？

  • QuickSort 在最坏情况下采用 N^2，在平均情况下采用 NlogN。最坏的情况发生在数据排序时。这可以通过在开始排序之前随机洗牌来缓解。
  • QuickSort 不会占用合并排序占用的额外内存。
  • 如果数据集很大并且有相同的项目，则快速排序的复杂性通过使用 3 路分区来降低。相同项目的数量越多，排序越好。如果所有项目都相同，则按线性时间排序。[这是大多数库中的默认实现]

快速排序总是比合并排序好吗？

并不真地。

  • Mergesort 是稳定的，但 Quicksort 不是。因此，如果您需要输出稳定性，您将使用 Mergesort。在许多实际应用中都需要稳定性。
  • 现在内存很便宜。因此，如果 Mergesort 使用的额外内存对您的应用程序并不重要，那么使用 Mergesort 并没有什么坏处。

注意：在 java 中，Arrays.sort() 函数对原始数据类型使用快速排序，对对象数据类型使用 Mergesort。因为对象消耗内存开销，所以为 Mergesort 添加一点开销从性能角度来看可能不是任何问题。

参考：观看Coursera 的普林斯顿算法课程第 3 周的 QuickSort 视频

于 2013-11-08T07:30:45.160 回答
4

与合并排序不同，快速排序不使用辅助空间。而合并排序使用辅助空间 O(n)。但是合并排序的最坏情况时间复杂度为 O(nlogn)，而快速排序的最坏情况复杂度为 O(n^2)，这发生在数组已经排序时。

于 2016-08-26T06:56:18.957 回答
4

这是面试中常见的一个问题，尽管合并排序的最坏情况性能更好，但快速排序被认为比合并排序更好，尤其是对于大输入。由于某些原因，快速排序更好：

1-辅助空间：快速排序是一种就地排序算法。就地分拣意味着不需要额外的存储空间来执行分拣。另一方面，合并排序需要一个临时数组来合并排序的数组，因此它不是就地的。

2-最坏情况：O(n^2)使用随机快速排序可以避免快速排序的最坏情况。通过选择正确的支点可以很容易地避免这种情况。通过选择正确的枢轴元素来获得平均案例行为，使其即兴发挥并变得与合并排序一样高效。

3- 引用的局部性：快速排序尤其表现出良好的缓存局部性，这使得它在许多情况下比合并排序更快，例如在虚拟内存环境中。

4- Tail recursion: QuickSort is tail recursive while Merge sort is not. A tail recursive function is a function where recursive call is the last thing executed by the function. The tail recursive functions are considered better than non tail recursive functions as tail-recursion can be optimized by compiler.

于 2020-03-19T15:49:33.583 回答
3

答案将稍微倾向于快速排序，以适应 DualPivotQuickSort 为原始值带来的变化。它在JAVA 7中用于在java.util.Arrays 中排序 

It is proved that for the Dual-Pivot Quicksort the average number of
comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n),
whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n)
respectively. Full mathematical proof see in attached proof.txt
and proof_add.txt files. Theoretical results are also confirmed
by experimental counting of the operations.

您可以在此处找到 JAVA7 实现 - http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/Arrays.java

DualPivotQuickSort 的进一步精彩阅读 - http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

于 2013-04-03T14:31:52.363 回答
3

在归并排序中，一般算法是：

  1. 对左子数组进行排序
  2. 对右子数组进行排序
  3. 合并 2 个已排序的子数组

在顶层，合并 2 个已排序的子数组涉及处理 N 个元素。

再下一层，步骤 3 的每次迭代都涉及处理 N/2 个元素，但您必须重复此过程两次。所以你仍然在处理 2 * N/2 == N 个元素。

再下一层，您将合并 4 * N/4 == N 个元素，依此类推。递归堆栈中的每个深度都涉及在对该深度的所有调用中合并相同数量的元素。

请考虑使用快速排序算法：

  1. 选择一个枢轴点
  2. 将轴心点放在数组中的正确位置，所有较小的元素都在左边，较大的元素在右边
  3. 对左子数组进行排序
  4. 对右子数组进行排序

在顶层，您正在处理一个大小为 N 的数组。然后您选择一个枢轴点，将其放在正确的位置，然后可以在算法的其余部分完全忽略它。

再下一层，您正在处理 2 个子数组，它们的组合大小为 N-1（即减去前面的枢轴点）。您为每个子阵列选择一个枢轴点，最多可有 2 个额外的枢轴点。

再下一层，您正在处理 4 个组合大小为 N-3 的子数组，原因与上述相同。

然后是 N-7... 然后是 N-15... 然后是 N-32...

递归堆栈的深度保持大致相同 (logN)。使用合并排序，您总是在递归堆栈的每一级处理 N 元素合并。但是，使用快速排序，您正在处理的元素数量会随着您向下堆栈而减少。例如，如果您查看递归堆栈中间的深度，您正在处理的元素数是 N - 2^((logN)/2)) == N - sqrt(N)。

免责声明：在合并排序中，因为每次将数组分成 2 个完全相同的块，递归深度正好是 logN。在快速排序中，由于您的枢轴点不太可能正好位于数组的中间，因此递归堆栈的深度可能略大于 logN。我还没有计算过这个因素和上述因素在算法复杂性中的实际作用有多大。

于 2016-03-12T13:51:03.890 回答
3

这是一个很老的问题，但由于我最近处理了这两个问题，这里是我的 2c：

合并排序平均需要 ~ N log N 次比较。对于已经（几乎）排序的排序数组，这下降到 1/2 N log N，因为在合并时我们（几乎）总是选择“左”部分 1/2 N 次，然后只复制右 1/2 N 个元素。此外，我可以推测已经排序的输入使处理器的分支预测器发光，但可以正确猜测几乎所有分支，从而防止管道停顿。

快速排序平均需要 ~ 1.38 N log N 比较。在比较方面，它并没有从已经排序的数组中受益匪浅（但是它在交换方面，可能在 CPU 内的分支预测方面）。

我在相当现代的处理器上的基准测试显示如下：

当比较函数是回调函数时（如在 qsort() libc 实现中），对于 64 位整数，快速排序在随机输入上比合并排序慢 15%，对于已经排序的数组慢 30%。

另一方面，如果比较不是回调，我的经验是快速排序优于合并排序高达 25%。

但是，如果您的（大）数组具有很少的唯一值，则合并排序在任何情况下都会开始超过快速排序。

所以也许底线是：如果比较是昂贵的（例如回调函数，比较字符串，比较结构的许多部分，主要是为了有所作为） - 你可能会更好与归并排序。对于更简单的任务，快速排序会更快。

前面所说的都是真的： - 快速排序可以是 N^2，但 Sedgewick 声称，一个好的随机实现比执行 N^2 的计算机执行排序更有可能被闪电击中 - 合并排序需要额外的空间

于 2016-08-25T23:55:17.400 回答
2

快速排序具有更好的平均案例复杂度，但在某些应用程序中它是错误的选择。快速排序容易受到拒绝服务攻击。如果攻击者可以选择要排序的输入，他可以很容易地构造一个集合，它的最坏情况时间复杂度为 o(n^2)。

Mergesort 的平均情况复杂度和最坏情况复杂度是相同的，因此不会遇到同样的问题。合并排序的这一特性也使其成为实时系统的最佳选择——正是因为没有导致它运行得慢得多、慢得多的病态案例。

由于这些原因，我更喜欢 Mergesort，而不是 Quicksort。

于 2008-09-16T08:42:05.273 回答
2

这很难说。MergeSort 最差的是 n(log2n)-n+1，如果 n 等于 2^k，这是准确的（我已经证明了这一点）。对于任何 n，它在 (n lg n - n + 1) 和 (n lg n + n + O(lg n))。但是对于 quickSort，最好的是 nlog2n（n 也等于 2^k）。如果将 Mergesort 除以 quickSort，当 n 是无限时它等于 1。所以就好像 MergeSort 最坏的情况比 QuickSort 的最好情况要好，为什么我们要使用快速排序？但是请记住，MergeSort 没有到位，它需要 2n 个内存空间。而且 MergeSort 还需要做很多数组副本，我们算法分析中不包括。一句话，理论上MergeSort确实比quicksort快，但实际上需要考虑内存空间，array copy的成本，merger比quick sort慢。我曾经做过一个随机类在 java 中给我 1000000 个数字的实验，合并排序用了 2610 毫秒，快速排序用了 1370 毫秒。

于 2011-09-10T15:33:06.913 回答
2

快速排序是最坏情况 O(n^2)，但是，平均情况始终优于执行合并排序。每个算法都是 O(nlogn)，但你需要记住，在谈论大 O 时，我们会忽略较低复杂度的因素。当涉及到常数因素时，快速排序比合并排序有显着的改进。

合并排序也需要 O(2n) 内存，而快速排序可以就地完成（仅需要 O(n)）。这是快速排序通常优于合并排序的另一个原因。

额外信息：

当枢轴选择不当时，会发生快速排序的最坏情况。考虑以下示例：

[5、4、3、2、1]

如果选择枢轴作为组中的最小或最大数字，则快速排序将在 O(n^2) 中运行。选择列表中最大或最小 25% 中的元素的概率为 0.5。这使算法有 0.5 的机会成为一个好的支点。如果我们采用典型的枢轴选择算法（比如选择一个随机元素），我们有 0.5 的机会为每个枢轴选择选择一个好的枢轴。对于大尺寸的集合，总是选择一个糟糕的枢轴的概率是 0.5 * n。基于此概率，快速排序对于平均（和典型）情况是有效的。

于 2013-07-09T20:12:19.500 回答
2

当我对这两种排序算法进行试验时，通过计算递归调用的次数，快速排序始终比归并排序具有更少的递归调用。这是因为快速排序具有枢轴，并且枢轴不包含在下一个递归调用中。这样，快速排序可以比归并排序更快地达到递归基本情况。

于 2017-02-12T01:49:13.710 回答
1

虽然它们都属于同一个复杂性类，但这并不意味着它们都具有相同的运行时。快速排序通常比归并排序更快，只是因为它更容易编写紧凑的实现并且它所做的操作可以更快。这是因为快速排序通常更快，人们使用它而不是合并排序。

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

于 2008-09-16T08:44:17.437 回答
1

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

我想知道为什么很少看到基数或桶排序。它们是 O(n)，至少在链表上，所需要的只是某种将键转换为序数的方法。（字符串和浮点数工作得很好。）

我认为原因与计算机科学的教学方式有关。我什至不得不向我的算法分析讲师证明，确实可以比 O(n log(n)) 更快地排序。（他有证据表明你不能比 O(n log(n)) 更快地进行比较排序，这是真的。）

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

编辑：实际上，这是一种将浮点数排序为整数的更恶毒的方法：http: //www.stereopsis.com/radix.html。请注意，无论您实际使用哪种排序算法，都可以使用位翻转技巧...

于 2008-09-28T00:45:48.963 回答
1

快速与合并排序的小补充。

它也可以取决于排序项目的种类。如果访问项目、交换和比较不是简单的操作，例如比较平面内存中的整数，那么归并排序可能是更可取的算法。

例如，我们在远程服务器上使用网络协议对项目进行排序。

此外，在像“链表”这样的自定义容器中，快速排序没有好处。
1.链表上的归并排序，不需要额外的内存。2.快速排序中对元素的访问不是顺序的（在内存中）

于 2014-11-05T09:32:26.680 回答
0

快速排序是一种就地排序算法，因此更适合数组。另一方面，归并排序需要额外的 O(N) 存储，更适合链表。

与数组不同，在like list中，我们可以在中间插入项目，空间为O(1)，时间为O(1)，因此合并排序中的合并操作可以在没有任何额外空间的情况下实现。但是，为数组分配和取消分配额外空间会对归并排序的运行时间产生不利影响。合并排序也有利于链表，因为数据是按顺序访问的，没有太多的随机内存访问。

另一方面，快速排序需要大量随机内存访问，并且使用数组，我们可以直接访问内存，而无需链表所要求的任何遍历。用于数组时的快速排序也具有良好的引用局部性，因为数组连续存储在内存中。

尽管两种排序算法的平均复杂度都是 O(NlogN)，但通常人们在处理普通任务时使用数组进行存储，因此快速排序应该是首选算法。

编辑：我刚刚发现合并排序最差/最好/平均情况总是nlogn，但快速排序可以从n2（元素已经排序的最坏情况）到nlogn（当pivot总是将数组分成两部分时的平均/最佳情况）一半）。

于 2016-06-28T19:49:17.567 回答
0

考虑时间和空间复杂度。对于合并排序：时间复杂度：O(nlogn)，空间复杂度：O(nlogn)

对于快速排序：时间复杂度：O(n^2)，空间复杂度：O(n)

现在，他们都在一个场景中获胜。但是，使用随机枢轴，您几乎总是可以将快速排序的时间复杂度降低到 O(nlogn)。

因此，在许多应用程序中，首选快速排序而不是合并排序。

于 2018-12-23T14:06:15.560 回答
-1

在 c/c++ 领域，当不使用 stl 容器时，我倾向于使用快速排序，因为它是内置在运行时的，而合并排序不是。

所以我相信在很多情况下，这只是阻力最小的路径。

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

于 2008-09-17T02:00:10.113 回答
-4

原因之一是更具哲学性。快速排序是自上而下的哲学。有 n 个要排序的元素，有 n! 可能性。对于互斥的 m 和 nm 的 2 个分区，可能性的数量会下降几个数量级。米！*（纳米）！比 n! 小几个数量级！独自的。想象5！VS 3！*2！。5！比 2 和 3 的 2 个分区多 10 倍的可能性。并推断为 100 万阶乘与 900K！*100K！vs. 所以不用担心在范围或分区内建立任何顺序，只需在分区中建立更广泛级别的顺序并减少分区内的可能性。如果分区本身不是互斥的，则在一个范围内较早建立的任何顺序都将在以后受到干扰。

任何自下而上的排序方法（如合并排序或堆排序）都类似于工人或员工的方法，在这种方法中，人们很早就开始在微观层面进行比较。但是，一旦稍后发现它们之间的元素，这个顺序肯定会丢失。这些方法非常稳定且非常可预测，但需要做一些额外的工作。

快速排序类似于管理方法，其中一个人最初不关心任何订单，只关心满足一个广泛的标准而不考虑订单。然后分区缩小，直到你得到一个排序集。快速排序中真正的挑战是当您对要排序的元素一无所知时，在黑暗中找到一个分区或标准。这就是为什么我们要么需要花费一些精力来找到一个中值，要么随机选择 1 或一些任意的“管理”方法。找到一个完美的中位数可能需要大量的努力，并再次导致愚蠢的自下而上的方法。所以 Quicksort 说只是选择一个随机枢轴，并希望它会在中间的某个地方，或者做一些工作来找到 3 、 5 或更多的中位数以找到更好的中位数，但不打算做到完美&不要' 不要在最初订购时浪费任何时间。如果你很幸运，或者当你没有得到中位数但只是抓住机会时有时会降级到 n^2，那似乎做得很好。任何方式的数据都是随机的。对。因此，我更同意快速排序的自上而下的逻辑方法，事实证明，它更早保存的关于枢轴选择和比较的机会似乎比任何细致而彻底的稳定自下而上的方法更有效，例如合并排序。但 它较早保存的比较似乎比任何细致而彻底的稳定自底向上方法（如合并排序）更有效。但 它较早保存的比较似乎比任何细致而彻底的稳定自底向上方法（如合并排序）更有效。但

于 2017-12-10T22:57:58.817 回答