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

我在Java文档中找到了这个。

排序算法是Vladimir Yaroslavskiy，Jon Bentley和Joshua Bloch的Dual-Pivot Quicksort。此算法在许多数据集上提供 O（n log（n）） 性能，这些数据集会导致其他快速排序降级为二次性能，并且通常比传统的（单透视）快速排序实现更快。

然后我在谷歌搜索结果中找到这个。快速排序算法理论：

1. 从数组中选取一个称为透视的元素。
2. 对数组重新排序，以便所有小于透视的元素都位于透视表之前，而所有大于透视表的元素都位于透视表之后（相等的值可以位于任一方向）。在此分区之后，透视元素将处于其最终位置。
3. 以递归方式对较小元素的子数组和较大元素的子数组进行排序。

相比之下，双枢轴快速排序：

1. 对于小型数组（长度< 17），请使用插入排序算法。
2. 选择两个透视元素 P1 和 P2。例如，我们可以将第一个元素a[left]作为P1，最后一个元素a[right]作为P2。
3. P1 必须小于 P2，否则将交换它们。因此，有以下几个部分：
   • 第 I 部分，索引从左 +1 到 L–1，元素小于 P1，
   • 第二部分，索引从L到K-1，元素大于或等于P1，小于或等于P2，
   • 第 III 部分，索引从 G+1 到右–1，元素大于 P2，
   • 第四部分载有其余要检查的要素，索引从K到G。
4. 将第四部分的下一个元素a[K]与两个枢轴P1和P2进行比较，并放置在相应的第一，二或三部分。
5. 指针 L、K 和 G 在相应的方向上更改。
6. 重复步骤 4 - 5，而 K ≤ G。
7. 枢轴元素 P1 与第 I 部分中的最后一个元素交换，透视元素 P2 与第 III 部分中的第一个元素交换。
8. 步骤 1 - 7 对每个部分 I、第 II 部分和第 III 部分都以递归方式重复。

我只想补充一点，从算法的角度来看（即成本只考虑比较和交换的数量），2-pivot快速排序和3-pivot快速排序并不比经典的快速排序（使用1个枢轴）更好，如果不是更糟的话。但是，它们在实践中更快，因为它们具有现代计算机体系结构的优势。具体来说，它们的缓存未命中数较小。因此，如果我们删除所有缓存并且只有CPU和主内存，那么在我的理解中，2/3-pivot快速排序比经典的快速排序更糟糕。

参考文献：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