快速排序 vs 归并排序

Question

快速排序 vs 归并排序

algorithmsorting

124

为什么快速排序可能比归并排序更好？

- Ganesh M

1

@ qrdl：排序算法的属性远不止速度。 - Georg Schölly

在一个有16个寄存器的处理器上，比如64位模式下的PC，对于像排序伪随机整数数组这样的情况，四路归并排序可以与标准快速排序一样快或稍微快一些。4路归并排序执行的总操作次数与2路相同，但是它的比较次数是1.5倍，移动次数是0.5倍，并且比较的缓存友好性比移动高一些。公平地说，由于使用4路归并排序是一种优化，因此双轴快速排序应该会更快一点。大多数计算机都有几千兆字节的内存，所以归并排序的空间开销通常不是问题。 - rcgldr

11个回答

91

快速排序通常比归并排序更快，当数据存储在内存中时。然而，当数据集非常庞大且存储在外部设备（如硬盘）上时，归并排序在速度方面是明显的赢家。它最小化了对外部驱动器的昂贵读取，并且也非常适合并行计算。

- Michael

1

快速排序与归并排序一样适合并行计算。快速排序是自上而下的，而归并排序是自下而上的。我本来想说这对并行化无关紧要，但现在我认为快速排序稍微更适合并行化。我认为自上而下的方法更适合在分叉加入框架中进行工作窃取，这在超现代CPU（如英特尔Alder Lake和最新的智能手机芯片）上发挥作用，它们具有不对称核心。 - M.J. Rayburn

我也不确定归并排序是否更适合缓存本地性。首先，从磁盘到RAM的原理与从RAM到缓存是相同的，因此您会在两个地方看到相同的现象。此外，快速排序和归并排序之间的根本区别再次在于一个自上而下，而另一个则是自下而上，这在总体引用局部性甚至能够将所有内容放在某个地方方面没有任何区别。归并排序可以在开始时分成小块，而快速排序可以在结束时完成。为什么时间的安排很重要呢？ - M.J. Rayburn

据我理解，快速排序更快是因为它具有（稍微）更好的引用局部性，因为它可以在单个数组内执行，而高效的归并排序实现将在两个数组之间来回交替。当然，这也节省了内存和内存分配/释放。 - M.J. Rayburn

好的，经过进一步思考，我撤回了我关于并行化的声明中所说的快速排序在工作窃取的情况下比归并排序稍微计算上优越的部分。你可以同样有效地为两者都实现fork join框架。然而，我相信在快速排序上使用fork join会更加简单。 - M.J. Rayburn

64

对于归并排序，最坏情况的时间复杂度为 O(n*log(n))，而对于快速排序，则为 O(n²)。在其他情况下（平均情况和最佳情况），两者时间复杂度均为 O(n*log(n))。然而，快速排序是一个空间常数算法，而归并排序则取决于您正在排序的结构。

您可以查看此处进行比较。

您也可以通过可视化界面来查看它。

- Marcin Gil

4

错误的。快速排序的可接受实现方式是先对最小的子范围进行排序。 - Stephan Eggermont

确实是一篇非常好的比较文章。既详细解释了，也提供了简单的实现方法。 - extraneon

1

@Stephan Eggermont：你说得对——快速排序至少使用O(log n)和最多使用O(n)的额外空间，因为每次分割（递归）需要常量空间来存储枢轴位置，并且必须至少有log2(n)个这样的分割。我可能混淆了，错误地加入了n的额外因素。 - j_random_hacker

归并排序可以使用两个大小为n的数组来实现（无论您要排序的数组内容如何），算法在每个递归级别时在这两个数组之间来回切换。 - M.J. Rayburn

12

虽然快速排序通常比归并排序更好，但在某些情况下，理论上归并排序可能是更好的选择。最明显的情况是当算法比O(n^2)更快非常重要时。快速排序通常比这个更快，但是在理论上最坏的情况下，它可能以O(n^2)的时间运行，这比最坏的归并排序更糟。

相比之下，快速排序比归并排序更复杂，尤其是如果您想编写一个真正稳健的实现，因此，如果您的目标是简单性和可维护性，则归并排序成为一个很有前途的替代方案，并且几乎没有性能损失。

- CaptainAwesomePants

7

归并排序的优点在于当你需要稳定排序（相等元素不会被重新排列）或者使用顺序访问而非随机访问“内存”时（例如，你可以利用磁带驱动器有效地进行归并排序）。 - j_random_hacker

6

@j_random_hacker：您的磁带驱动器示例有点晦涩；更常见的例子可能是在接收自网络连接的数据时对其进行排序，或对不允许有效的随机访问（如链表）的数据结构进行排序。 - Christoph

你从未回答过这个问题。 - M.J. Rayburn

一种高效的快速排序版本实际上比一个高效的归并排序版本稍微简单一些，因为高效的归并排序版本在两个大小为n的数组之间来回交替以避免昂贵的内存分配和释放。因此，它们必须像快速排序一样跟踪索引，并且除此之外还必须具有在两个数组之间交替的逻辑。也许你指的是类似于Intro Sort这样的算法，如果快速排序的递归深度超过log(n)，则切换到堆排序。 - M.J. Rayburn

11

我个人想测试快速排序和归并排序之间的差异，并查看1,000,000个元素样本的运行时间。

快速排序用了156毫秒而归并排序用了247毫秒

然而，快速排序数据是随机的，如果数据是随机的，则快速排序表现良好，而归并排序不是这种情况，即无论数据是否排序，归并排序都执行相同。但是，归并排序需要一个额外的完整空间，而快速排序不需要，因为它是原地排序。

我为它们编写了详细的工作程序，并附有说明图片。

- bragboy

奇怪。我也写了一个Java程序来对一百万个元素进行快速排序和归并排序。我的快速排序执行时间与你的差不多，但我的归并排序需要大约12分钟...有什么原因吗？你能看看我的代码吗？ - compski

@compski：你能给我指一下你的代码吗？ - bragboy

http://pastebin.com/sYs4u6Kd - compski

2

@compski：我在你的代码第14行看到了一个问题。你不应该创建无数个数组来代替一个额外的数组空间，这会消耗大量内存。这里有一个例子，只使用了一个额外的数组（请参见第24行）。http://tech.bragboy.com/2010/01/merge-sort-in-java.html 如果这个解决方案不能解决你的问题，请告诉我，我可以提供更多帮助。 - bragboy

你从未回答过这个问题。 - M.J. Rayburn

8

快速排序是原地排序算法。在划分函数期间，您只需要交换数据的位置即可。归并排序需要更多的数据复制。您需要另一个临时存储（通常与原始数据数组大小相同）用于合并函数。

- Peter Leong

5

除其他算法之外：归并排序对于诸如链表之类的不可变数据结构非常高效，因此对于（纯）函数式编程语言来说是一个很好的选择。

一个实现不良的快速排序可能会成为安全风险。

- Dario

2

链表的问题不在于可变性，而在于缺乏高效的随机访问，也就是说你只能使用在线算法（归并排序、插入排序）。 - Christoph

@Christoph：快速排序不需要随机访问；链表可以高效地进行快速排序。当你看快速排序的工作原理时，它实际上从数组中定义的起始点有效地增加了几个“列表”。（另一方面，堆排序确实需要O（1）的随机访问。） - j_random_hacker

@j_random_hacker：如果没有随机访问，快速排序会受到枢轴选择不当的影响。 - Christoph

@Christoph：我也考虑过这个问题，但我认为它唯一会影响的是选择枢轴的策略（尽管这种情况很常见），即从开头、中间和结尾选取三个元素的中位数变体。即使进行O(n)扫描以找到这3个元素，也不会改变分区步骤的O(n)时间复杂度：它应该导致总体减速<2倍。而且，通过在“父”递归调用构建每个分区时确定这3个值（对于中点元素，每2次迭代更新指针），甚至可以消除这种情况。 - j_random_hacker

你从未回答过这个问题。 - M.J. Rayburn

显示剩余2条评论

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的更多信息，可以参考这篇文章。

- appbootup

3

快速排序之所以被命名为快速，是有原因的。

重点如下：两者都是稳定排序（仅仅是实现上的麻烦），所以让我们继续看复杂度。

只用大O符号表示很容易混淆和误用，两者的平均情况时间复杂度都是O(nlogn)，但归并排序总是O(nlogn)，而快速排序对于不良分区（即偏斜分区，例如1个元素-10个元素，可能由于已排序或反向排序列表而发生）会导致O(n^2)的情况。

因此，我们有随机化快速排序，其中我们随机选择枢轴并避免这种偏斜分区，从而消除了整个n^2的情况。即使对于中等程度的偏斜分区，如3-4，我们也有O(nlog(7/4)n)，理想情况下，我们希望1-1分区，因此整个复杂度为O(nlog(2)n)的2部分。

因此，它几乎总是O(nlogn)，与归并排序不同，隐藏在“大O”符号下的常数对于快速排序比对于归并排序更好...而且它不像归并排序那样使用额外的空间。

但要使快速排序运行完美需要调整和重新构造，快速排序提供了调整的机会...

- idexi

快速排序可以变得稳定，查看此帖子：https://dev59.com/2HVD5IYBdhLWcg3wBm1h#1675152。希望这有所帮助。 - idexi

“与归并排序不同，快速排序下隐藏在“大O符号”下的常数比归并排序更好”这种说法不仅不能算作答案，而且更重要的是它甚至不正确。归并排序将始终比快速排序少进行比较。你所说的这个比较次数从哪里来？在任何一种情况下都不存在。由于快速排序是内联的，因此具有稍微更好的引用局部性，而（高效实现的）归并排序在两个数组之间来回交替，并且它可以节省内存分配。” - M.J. Rayburn

3

快速排序更好并不是真的。另外，这取决于你所说的更好是什么，内存消耗还是速度。

就内存消耗而言，在最坏情况下，快速排序可以使用n^2的内存（即每个分区为1到n-1），而归并排序使用nlogn的内存。

在速度方面，上述内容也适用。

- Jason

快速排序在最坏情况下只会使用O(n)的内存。是的，时间复杂度在最坏情况下可能为O(n^2)。要理解这一点，请查看递归堆栈的最大大小。这等于DFS树中的最大级别数。即使每个分区都是1，n-1，级别的数量也将是n（n，n-1，n-2，n-3 ... 1）。 - mlfan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Benoît · Accepted Answer

请参考维基百科上有关快速排序的内容：

通常情况下，与其他Θ(nlogn)算法相比，快速排序实际上的运行速度要快得多，因为它的内部循环可以在大多数架构中得到有效的实现，在大多数实际的数据中，我们可以进行设计选择，从而最小化需要二次时间的概率。

需要注意的是，非常低的内存需求也是一个重要的优点。