Quick Sort Vs Merge Sort

为什么快速排序比合并排序更好？

257630 次浏览
小开
最佳答案

See 维基百科上的 Quicksort:

通常情况下，快速排序是非常重要的 faster in practice than other Θ(nlogn) 算法，因为它的内部循环可以 有效率地执行大部分 在大多数现实世界中 数据，使设计成为可能 使概率最小化的选择 需要二次时间。

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

小开

For Merge sort worst case is O(n*log(n)), for Quick sort: O(n2). For other cases (avg, best) both have O(n*log(n)). However Quick sort is space constant where Merge sort depends on the structure you're sorting.

参见 这个比较。

你也可以看到它 视觉上。

小开

虽然快速排序通常是比合并排序更好的选择，但从理论上讲，合并排序肯定是更好的选择。最明显的时间就是你的算法运行速度超过 O (n ^ 2)的时候。快速排序通常比这个更快，但是考虑到理论上最糟糕的可能输入，它可以在 O (n ^ 2)中运行，这比最糟糕的合并排序还要糟糕。

Quicksort is also more complicated than mergesort, especially if you want to write a really solid implementation, and so if you're aiming for simplicity and maintainability, merge sort becomes a promising alternative with very little performance loss.

小开

快速排序已经就位。您只需要很少的额外内存。这一点非常重要。

对中值的正确选择使它更加有效，但即使是对中值检疫 Θ (nlogn)的错误选择。

小开

我个人想亲自测试 Quick sort 和 merge sort 之间的区别，并查看了1,000,000个元素样本的运行时间。

快速排序能够在156毫秒内完成 合并排序在247毫秒内完成同样的操作

然而，如果数据是随机的，那么 Quick sort 数据就是随机的，而快速排序则执行得很好，因为与合并排序不同，也就是合并排序执行得一样，不管数据是否排序。 但是合并排序需要一个完整的额外空间，而快速排序不作为就地排序

我写了全面的工作程序为他们将说明性的图片太。

小开

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

实现不佳的快速排序可以是 安全隐患。

小开

当数据存储在内存中时，快速排序通常比合并排序快。然而，当数据集非常庞大并且存储在外部设备(如硬盘)上时，合并排序显然是速度方面的赢家。它最大限度地减少了外部驱动器的昂贵读取，也很适合并行计算。

小开

快速排序并不是更好。此外，这还取决于您所指的更好、内存消耗或速度。

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

从速度上看，以上几点如下。

小开

快速排序已经就位。您只需在分区函数执行期间交换数据的位置即可。 合并排序需要更多的数据复制 与原始数据数组的大小相同)。

小开

快排之所以叫快排是有原因的,

highlights : 两者都是稳定的排序，(只是一个实现问题) ，因此让我们继续讨论复杂性

它非常令人困惑，仅仅是大-oh 符号被泄露和“滥用”，两者的平均大小写复杂度都为0(nlogn) ,

but merge sort is always 0(nlogn) , whereas quicksort for bad partitions, ie skewed partitions like 1 element-10 element (which can happen due to sorted or reverse sorted list ) can lead to a 0(n^2)..

..所以我们有随机快排，我们随机选择轴心，避免这样的偏斜分区，从而使整个 n ^ 2场景无效 无论如何，即使对于像3-4这样中等偏斜的分区，我们有一个 nlog (7/4) n, 理想情况下，我们想要1-1分割，因此 O (nlog (2) n)的整个2。

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

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

小开

The answer would slightly tilt towards quicksort w.r.t to changes brought with DualPivotQuickSort for primitive values . It is used in JAVA 7 to sort in Java.util. 数组 

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上进一步的精彩阅读


提交答案