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

What's the difference of dual pivot quick sort and quick sort?

提问by Brutal_JL

I've never seen dual pivot quick sort before. If it is a upgrade edition of quick sort?
And what is the difference of dual pivot quick sort and quick sort?

我以前从未见过双枢轴快速排序。如果是quick sort的升级版？
双枢轴快速排序和快速排序有什么区别？

采纳答案by Brutal_JL

I find this in the Java doc.

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

The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

排序算法是 Vladimir Yaroslavskiy、Jon Bentley 和 Joshua Bloch 的双枢轴快速排序。该算法在许多数据集上提供 O(n log(n)) 性能，导致其他快速排序降级为二次性能，并且通常比传统（单轴）快速排序实现更快。

Then I find this in the Google search result. Thoery of quick sort algorithm:

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

1. Pick an element, called a pivot, from the array.
2. Reorder the array so that all elements, which are less than the pivot, come before the pivot and all elements greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot element is in its final position.
3. Recursively sort the sub-array of lesser elements and the sub-array of greater elements.

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

In comparison, dual-pivot quick sort:

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

()

( )

1. For small arrays (length < 17), use the Insertion sort algorithm.
2. Choose two pivot elements P1 and P2. We can get, for example, the first element a[left] as P1 and the last element a[right] as P2.
3. P1 must be less than P2, otherwise they are swapped. So, there are the following parts:
   • part I with indices from left+1 to L–1 with elements, which are less than P1,
   • part II with indices from L to K–1 with elements, which are greater or equal to P1 and less or equal to P2,
   • part III with indices from G+1 to right–1 with elements greater than P2,
   • part IV contains the rest of the elements to be examined with indices from K to G.
4. The next element a[K] from the part IV is compared with two pivots P1 and P2, and placed to the corresponding part I, II, or III.
5. The pointers L, K, and G are changed in the corresponding directions.
6. The steps 4 - 5 are repeated while K ≤ G.
7. The pivot element P1 is swapped with the last element from part I, the pivot element P2 is swapped with the first element from part III.
8. The steps 1 - 7 are repeated recursively for every part I, part II, and part III.

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

回答by Anatoly Yakimchuk

For those who are interested, take a look how they implemented this algorithm in Java:

有兴趣的可以看看他们是如何在 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

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

As stated in source:

如来源所述：

"Sorts the specified range of the array using the given workspace array slice if possible for merging

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

The algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations."

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

回答by Duong Nguyen

I just want to add that from the algorithm point of view (i.e. the cost only considers the number of comparisons and swaps), 2-pivot quicksort and 3-pivot quicksort is not better than classical quicksort (which uses 1 pivot), if not worse. However, they are faster in practice since they take the benefits of modern computer architecture. Specifically, their numbers of cache misses are smaller. So if we remove all caches and there are only CPU and main memory, in my understanding, 2/3-pivot quicksort is worse than classical quicksort.

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

References: 3-pivot Quicksort: https://epubs.siam.org/doi/pdf/10.1137/1.9781611973198.6Analysis of why they perform better than classical Quicksort: https://arxiv.org/pdf/1412.0193v1.pdfA complete and not-too-much-details reference: https://algs4.cs.princeton.edu/lectures/23Quicksort.pdf

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