雅罗斯拉夫斯基的双轴快速排序算法

Question

我正在研究双轴快速排序，我在这里找到了相关资料（第20页）。

比较：

Yaroslavskiy算法平均需要1.9 n ln n次比较。 经典快速排序需要2 n ln n次比较！

交换：

Yaroslavskiy算法所需的交换次数为0.6 n ln n。 经典快速排序所需的交换次数为0.3 n ln n。

结果：

数据类型-----比较次数-------交换次数 int-------------591纳秒---------802纳秒 float-----------838纳秒---------873纳秒 double--------873纳秒---------1047纳秒 char----------593纳秒---------837纳秒

注意：上述结果以纳秒为单位，在Java语言下使用Intel Core 2 Duo进行操作。

如果我们将交换和比较的成本相加，那么除了字符串外，经典快速排序都比Yaroslavskiy快速排序更好。对于字符串，我们使用指针数组来交换，这会花费88纳秒。在字符串的情况下，Yaroslavskiy算法利用了1.9 n ln n的比较优势，因为与交换相比，比较太昂贵了。

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

- asd

---

Java在哪里使用这个算法？根据Javadoc，Collections.sort使用修改后的归并排序。 - Zavior

该算法在许多数据集上提供O(n log(n))的性能，而其他快速排序算法则会降至二次性能，并且通常比传统（单轴）快速排序实现更快。我猜这就是为什么。除此之外，您需要询问将其包含在库中的人。 - Zavior

@Zavior Collections.sort 可能使用归并排序，但是 Arrays.sort（用于原始类型数组的操作）使用快速排序。这与排序的稳定性有关 - 在原始类型容器上进行稳定或不稳定的排序对结果没有影响，但在对象上有影响。 - Bernhard Barker

如果对于其他数据类型也是正确的，那么为什么我的结果除了字符串以外的其他数据类型都不匹配？ - asd

抱歉，我给你提供了错误信息。归并排序用于大型数组（大于286）。 - Oroboros102

Answer 1

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

证明对于双轴快速排序，平均比较次数为2*n*ln(n)，平均交换次数为0.8*n*ln(n)，而经典的快速排序算法分别为2*n*ln(n)和1*n*ln(n)。

看起来双轴快速排序总是更好。

- ElKamina

Answer 2

我测试了双轴Java快速排序与许多其他快速排序算法。它的速度至少比其他算法快10％至15％。除了双轴之外，它还使用了许多其他优化技巧：

• 5点轴选择
• 对小子数组进行插入排序退化处理
• 数据属性检测（而不是洗牌）

- Oroboros102