java - Yaroslavskiy 的双枢轴快速排序算法

Question

我正在研究我发现的双枢轴快速排序 here (幻灯片第 20 页)

比较:

Yaroslavskiy needs = 1.9 n ln n on average.

Classic Quicksort needs = 2 n ln n comparisons!

交换:

Swaps for Yaroslavskiy’s algorithm = 0.6 n ln n

Swaps for classic Quicksort=0.3 n ln n

结果

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

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

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

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

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

/* 注意:- 以上结果以纳秒为单位，并使用 intel core 2 duo 在 java lang 中执行 */

如果我们将交换成本和比较成本结合起来，经典快速排序将击败 Yaroslavskiy 快速排序 除了在字符串的情况下，我们使用指针数组进行交换，这需要 88 纳秒。这里 Yaroslavskiy 的算法利用了 1.9 n ln n 比较，因为与字符串情况下的交换相比，比较成本太高。

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

Answer 1

我不知道你从哪里得到的数字。根据this page :

It is proved that for the Dual-Pivot Quicksort the average number of comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n), whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n) respectively.

看起来双枢轴总是更好。