双枢轴快速排序和快速排序有什么区别？
Bru*_*_JL 56 java sorting quicksort
我以前从未见过双枢轴快速排序.如果是快速排序的升级版？
双枢轴快速排序和快速排序有什么区别？
Bru*_*_JL 78
我在java doc中找到了这个.
排序算法是Vladimir Yaroslavskiy,Jon Bentley和Joshua Bloch的Dual-Pivot Quicksort.该算法在许多数据集上提供O(n log(n))性能,导致其他快速降序降级为二次性能,并且通常比传统(单枢轴)Quicksort实现更快.
然后我在谷歌搜索结果中找到了这个.快速排序算法的理论:
- 从数组中选择一个称为pivot的元素.
- 对数组进行重新排序,使得所有小于枢轴的元素都位于枢轴之前,所有大于枢轴的元素都在它之后(相同的值可以是任意一种).在该分区之后,枢轴元件处于其最终位置.
- 递归地排序较小元素的子数组和较大元素的子数组.
相比之下,双枢轴快速排序:
- 对于小型数组(长度<17),请使用插入排序算法.
- 选择两个枢轴元素P1和P2.例如,我们可以得到第一个元素a [left]作为P1,最后一个元素a [right]作为P2.
- P1必须小于P2,否则交换它们.所以,有以下几个部分:
- 第一部分,索引从左+ 1到L-1,元素小于P1,
- 第二部分,指数从L到K-1,其元素大于或等于P1且小于或等于P2,
- 第三部分,指数从G + 1到右一,元素大于P2,
- 第IV部分包含要检查的其余元素,索引从K到G.
- 将来自部分IV的下一个元素a [K]与两个枢轴P1和P2进行比较,并将其放置到相应的部分I,II或III.
- 指针L,K和G在相应的方向上改变.
- 当K≤G时,重复步骤4-5.
- 枢轴元件P1与来自部件I的最后一个元件交换,枢轴元件P2与来自部件III的第一元件交换.
- 对于每个部分I,部分II和部分III,递归地重复步骤1-7.
- 这就是为什么我们非常感谢Java Library设计师,我们不必实现自己的排序算法,否则我们都会使用冒泡排序;-) (51认同)
- @ abksrv,MergeSort是`O(n log n)`,InsertionSort是`O(n ^ 2)`,但这实际上是`C1*n*log(n)`和`C2*n*n`*(其中C1和C2是一些常数)*.当`n`很大时,常数是无关紧要的.当`n`很小时,它们可能是相关的.据推测,实施者调查并发现17是临界点,其中:`C1*log(17)> C2*17`,但是`C1*log(18)<C2*18`. (5认同)
- Yaroslovsky的原始论文（http://codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf）将使用插入排序的阈值设置为27，而不是17。另一方面，Yaroslovsky，Bentley和Bloch在Java 8中的实现（http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/tip/src/share/classes/java/util/ DualPivotQuicksort.java）使用47作为阈值。 (2认同)
小智 5
我只想补充一点，从算法的角度（即成本只考虑比较和交换的次数），2-pivot quicksort 和 3-pivot quicksort 并不比经典快速排序（使用 1 pivot）好，如果不是更差。然而，它们在实践中速度更快，因为它们利用了现代计算机体系结构的好处。具体来说，它们的缓存未命中数较少。因此，如果我们删除所有缓存并且只有 CPU 和主内存，在我的理解中，2/3-pivot 快速排序比经典快速排序差。
参考文献：3-pivot Quicksort：https ://epubs.siam.org/doi/pdf/10.1137/1.9781611973198.6 为何比经典Quicksort表现更好的分析：https : //arxiv.org/pdf/1412.0193v1.pdf 完整且不太详细的参考：https : //algs4.cs.princeton.edu/lectures/23Quicksort.pdf