Yaroslavskiy的双支点快速排序算法 [英] Yaroslavskiy’s dual pivot quick sort algorithm

问题描述

我在双支点快速排序工作，我发现这里（页无在幻灯片-20）

I am working on dual pivot quick sort I found here (page no-20 in slide)

比较：

Yaroslavskiy需要= 1.9ñLN N于平均水平。

Yaroslavskiy needs = 1.9 n ln n on average.

经典的快速排序需要= 2 N LNñ比较！

Classic Quicksort needs = 2 n ln n comparisons!

互换：

有关Yaroslavskiy算法互换= 0.6正LNñ

Swaps for Yaroslavskiy’s algorithm = 0.6 n ln n

互换经典的快速排序=为0.3N LNñ

Swaps for classic Quicksort=0.3 n ln n

结果

数据类型-----补偿-------交换

Data type-----comp-------swap

INT ------------- 591ns --------- 802ns

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

浮法----------- ---------- 838ns 873ns

float-----------838ns----------873ns

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

double -------873ns----------1047ns

字符---------- ----------- 593ns 837ns

char ----------593ns-----------837ns

/ *注： - 上述结果在纳秒和Java的郎执行使用英特尔Core 2 Duo * /

/* note :- above results in nanosecond and performed in java lang using intel core 2 duo */

如果我们把交换和比比较经典的快速排序的成本击败Yaroslavskiy快速排序 除了在案件串在这里我们使用指针数组来交换需要88 nanosecond.Here Yaroslavskiy的算法，取​​1.9ñLN n个比较优势，因为比较是比较的情况下串交换太多昂贵。

if we combine the cost of swap and comparison than Classic Quicksort beats Yaroslavskiy Quicksort except in case of string where we use array of pointer to swap which require 88 nanosecond.Here Yaroslavskiy’s algorithm take advantage of 1.9 n ln n comparison because comparison is too much expensive compare to swap in case of string.

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

i want to know why java uses Yaroslavskiy Quicksort ? is main focus of inbuilt library sort are string what if it is not good on others data type?

推荐答案

我测试双Java的支点快速排序对许多其他快速排序。它是在最低速度快10〜15％。此外doublepivotness，它使用了大量其它的优化的：

I tested dual java's pivot quicksort against many other quicksorts. It was 10~15% faster at minimum. Besides doublepivotness, it uses a lot of other optimisations:

• 5分的支点选择
• 插入排序沦落为小型子阵
• 的数据性能检测（而不是改组）

这篇关于Yaroslavskiy的双支点快速排序算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！