合并排序优先于快速排序？

Question

在许多情况下,快速排序比合并排序要好得多.但是,何时合并排序可能比快速排序更好？

例如,当数据无法一次加载到内存时,合并排序比快速排序更有效.还有其他案件吗？

编辑:建议的重复问题列表的答案快速排序合并排序的所有优点.我在这里询问可能的情况和使用合并排序的应用程序比使用快速排序更有利.

Answer 1

我应该首先提一下,如果你不能同时将所有内容都安装到内存中,那么quicksort和mergesort都可以正常工作.您可以通过选择一个数据透视表来实现快速排序,然后将元素从磁盘流入内存,并根据该元素与数据透视表的比较将元素写入两个不同文件中的一个.如果使用双端优先级队列,实际上可以通过一次将最大数量的可能元素拟合到内存中来更有效地执行此操作.

其他人已经提到mergesort是最坏情况O(n log n)的好处,这绝对是正确的.也就是说,您可以轻松修改quicksort以生成introsort算法,即quicksort,插入排序和heapsort之间的混合,这是最坏情况的O(n log n),但在大多数情况下仍保持快速排序的速度.

看看为什么quicksort通常比mergesort更快可能会有所帮助,因为如果您了解原因,您可以很快找到mergesort明显胜出的一些情况.Quicksort通常比mergesort更好,原因有两个:

1. Quicksort具有比mergesort更好的引用位置,这意味着在quicksort中执行的访问通常比mergesort中的相应访问更快.

2. Quicksort使用最坏情况的O(log n)内存(如果正确实现),而mergesort需要O(n)内存,因为合并的开销.

但是,有一种情况是这些优势消失了.假设您要对元素的链接列表进行排序.链表元素分散在整个内存中,因此优势(1)消失(没有引用的位置).其次,链接列表只能与O(1)空间开销合并而不是O(n)空间开销,因此优势(2)消失.因此,您通常会发现mergesort是一种用于对链表进行排序的优秀算法,因为它可以减少总比较,并且不易受较差的数据透视选择的影响.

希望这可以帮助!

Answer 2

合并排序比快速排序的一个最重要的优点是它的稳定性:比较的元素保持其原始顺序.

Answer 3

1. MergeSort在设计上是稳定的,相同的元素保持其原始顺序.
2. MergeSort非常适合并行(多线程)实现.
3. MergeSort使用(约30%)比QuickSort更少的比较.这是一个经常被忽视的优点,因为比较可能非常昂贵(例如,在比较数据库行的几个字段时).

Answer 4

快速排序是平均情况O（n log n），但最坏情况是O（n ^ 2）。合并排序始终为 O（n log n）。除了渐近的最坏情况和mergesort的内存加载之外，我无法想到其他原因。

快速排序比合并排序更糟糕的情况：

1. 数组已排序。
2. 数组中的所有元素都相同。
3. 数组以相反的顺序排序。

如果您对数据一无所知，则将合并排序优先于快速排序。

Answer 5

合并排序的保证上限为O（N log ₂ N）。快速排序也有这样的限制，但它要高得多-它是O（N ²）。当您需要保证代码时序的上限时，请使用合并排序而非快速排序。

例如，如果您为依赖排序的实时系统编写代码，则合并排序将是一个更好的选择。