java - 如何在 Quicksort (DualPivotQuicksort) 的 java 实现中引入随机性

Question

我正在研究 java 中 DualPivotQuicksort 类的实现细节。

就算法而言，它肯定是快速排序的一种变体，尽管没有意义的是在枢轴选择中引入随机性的方式，从而确保算法在预期<中运行/strong> O(n lg (n)) 的运行时间。

我引用了几篇论文，但它们或多或少地解释了算法，而不是解决如何处理枢轴选择的随机性或者不是很明确:

https://arxiv.org/pdf/1403.6602

Answer 1

您没有说哪个 Java 实现，所以我假设您指的是 java.util.DualPivotQuicksort。

该类(class)不会随机选择枢轴。事实上，它从子数组中选取 7 个等距的候选主元，对它们进行排序，并使用第 3 个和第 5 个作为(双)主元。

异常(exception)情况:

• 小数组/子数组使用插入排序进行排序。
• byte 数组使用插入排序或计数排序进行排序。

(注意:这是基于Java 7/8中的实现)