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

本文介绍了双枢轴快速排序和快速排序有什么区别？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

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?

推荐答案

我在java doc中找到了这个。

I find this in the java doc.

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

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.

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

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

从数组中选择一个名为pivot的元素。

对数组进行重新排序，使得所有小于枢轴的元素都位于枢轴之前，所有大于枢轴的元素都在它之后（相等的值可以去）两种方式）。在此分区之后，pivot元素处于其最终位置。

递归排序较小元素的子数组和较大元素的子数组。

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

In comparison,dual-pivot quick sort:

对于小数组（长度<17），请使用插入排序算法。

选择两个数据透视表元素P1和P2。例如，我们可以得到第一个元素a [left]为P1，最后一个元素a [right]为P2。

P1必须小于P2，否则它们被交换了。所以，有以下几个部分：

• 第一部分，索引从左+ 1到L-1，含元素，小于P1，
• 第二部分，指数从L到K-1，其元素大于或等于P1且小于或等于P2，
• 第三部分带指数从G + 1到右1，元素大于P2，
• 第四部分包含要检查的其余元素，从K到G的索引。
• For small arrays (length < 17), use the Insertion sort algorithm.
• 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.
• 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.