Yaroslavskiy的双枢轴快速排序算法

我正在研究我在这里找到的双枢轴快速排序（幻灯片中的第20页）

比较：

Yaroslavskiy平均需要= 1.9 n nn。

Classic Quicksort需要= 2 n n n n n比较！

互换：

Yaroslavskiy算法的互换= 0.6 n nn

经典Quicksort的掉期= 0.3 n nn

结果

数据类型—– comp ——- swap

int ————- 591ns ——— 802ns

浮———– ———- 838ns 873ns

双——- 873ns ———- 1047ns

char ———- 593ns ———– 837ns

/ *注意： – 上面的结果是纳秒，并使用intel core 2 duo * /在java lang中执行

如果我们将交换和比较的成本结合起来比Classic Quicksort击败Yaroslavskiy Quicksort，除非在字符串的情况下我们使用指针交换的数组需要88纳秒。这里Yaroslavskiy的算法利用1.9 nnn nn n比较，因为比较太贵了比较字符串的情况下的交换。

我想知道为什么java使用Yaroslavskiy Quicksort？是内置库排序的主要焦点是字符串，如果它对其他数据类型不好？

我不知道你从哪里得到你的号码。根据这个页面：

certificate了对于Dual-Pivot Quicksort，平均比较次数是2*n*ln(n) ，平均交换次数是0.8*n*ln(n) ，而经典Quicksort算法有2*n*ln(n)和1*n*ln(n) 。

看起来双枢轴总是更好。

我测试了双java的pivot quicksort与许多其他quicksort。最低速度提高了10~15％。除了doublepivotness，它还使用了许多其他优化：