快速排序与合并排序[重复]

看见 Quicksort on wikipedia

通常,快速排序非常重要 实践中比其他(nlogn)更快 在大多数情况下都能有效地实施 体系结构,以及在大多数现实世界中 最小化概率的选择 需要二次时间。

请注意,非常低的内存需求也是一大优势。

O(n*log(n)) ,以便快速排序: O(n ^2. ) . 对于其他情况(平均值,最佳值),两者都有 . 但是,快速排序是空间常量,其中合并排序取决于正在排序的结构。

看见 this comparison .

你也可以看到它 visually

快速排序也比合并排序更复杂,特别是如果您想编写一个真正可靠的实现,因此如果您的目标是简单性和可维护性,合并排序将成为一个很有前途的替代方案,而且性能损失很小。

我个人想亲自测试快速排序和合并排序之间的区别,并查看了1000000个元素样本的运行时间。

Quick sort was able to do it in 156 milliseconds Merge sort did the same in 247 milliseconds

但是,快速排序数据是随机的,如果数据是随机的,则快速排序的性能良好,而合并排序的情况并非如此,即合并排序的性能相同,无论数据是否排序。

我已经为他们编写了全面的工作程序,还将提供说明性图片。

除其他外:合并排序对于链表这样的不可变数据结构非常有效,因此对于(纯)函数式编程语言来说是一个很好的选择。

security risk .

Mergesort需要更多的数据复制。您需要另一个临时存储(通常为 与合并函数的原始数据数组大小相同)。

“快速排序”之所以如此命名是有原因的,

亮点: 两者都是稳定类型(只是一个实现麻烦),所以让我们继续讨论复杂性

.. 所以我们有了随机快速排序,在这里我们随机选择轴并避免这种扭曲的分区,从而使整个n^2场景无效 理想情况下,我们需要1-1部分,因此O(nlog(2)n)的整个2。

所以它是O(nlogn),几乎总是和merge-sort不同的是,隐藏在“big-oh”符号下的常量对于快速排序比对于merge-sort更好。而且它不像merge-sort那样占用额外的空间。

但要让快速排序完美运行,需要调整、重新措辞,快速排序为您提供了调整的机会。。。。

答案将略微倾向于快速排序w.r.t,以应对原始值的DualPivotQuickSort带来的变化。它被用于 java.util.Array

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.

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

快速排序不是更好的说法。此外,这取决于您所说的更好、内存消耗或速度。

就内存消耗而言,在最坏的情况下,快速排序可以使用n^2内存(即每个分区是1到n-1),而合并排序使用nlogn。

就速度而言,上述情况如下。

快速排序已就位。你只需要很少的额外记忆。这是非常重要的。

好的中位数选择会使它更加有效,但即使是坏的中位数选择也会保证θ(nlogn)。