双轴快速排序和快速排序有什么区别？

Question

我以前从未见过双轴心快速排序。它是快速排序的升级版吗？

双轴快速排序和快速排序的区别是什么？

Answer 1

我只想补充一下，从算法的角度来看(即成本只考虑比较和交换的次数)，2轴快速排序和3轴快速排序并不比经典的快速排序(使用1轴)更好，如果不是更差的话。然而，它们在实践中速度更快，因为它们利用了现代计算机体系结构的优点。具体地说，它们的缓存未命中数量较少。因此，如果我们删除所有缓存，只有CPU和主存，在我的理解中，2/3轴快速排序比经典快速排序更差。

参考资料:3轴快速排序：https://epubs.siam.org/doi/pdf/10.1137/1.9781611973198.6分析为什么它们比经典快速排序性能更好：https://arxiv.org/pdf/1412.0193v1.pdf完整且不太详细的参考资料：https://algs4.cs.princeton.edu/lectures/23Quicksort.pdf

Answer 2

对于那些感兴趣的人，看看他们是如何在Java中实现这个算法的：

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/DualPivotQuicksort.java#DualPivotQuicksort.sort%28int%5B%5D%2Cint%2Cint%2Cint%5B%5D%2Cint%2Cint%29

如源代码中所述：

“如果可以合并，则使用给定的工作区数组切片对指定范围的数组进行排序。

该算法在许多数据集上提供O(n log(n))性能，这些数据集导致其他快速排序性能降级为二次性能，并且通常比传统的(单轴)快速排序实现更快。