java Quicksort (DualPivotQuicksort) 实现中如何引入随机性
How is randomness introduced in java implementation of Quicksort (DualPivotQuicksort)
我在 java 中查看了 DualPivotQuicksort class 的实现细节。
就算法而言，它肯定是 Quicksort 的变体，尽管没有意义的是在基准选择中引入随机性的方式，从而确保算法在 预期 运行 O (n lg (n)) 的时间。
我参考了几篇论文，但它们或多或少地解释了算法，而不是解决如何处理枢轴选择的随机性或者不是很明确：
简单快速排序实现的最坏情况发生在输入已经根据你的主元策略排序时，比如如果选择主元作为子数组的第一个元素，你将得到最坏的情况运行 时间，如果你的元素已经有序。因为我们经常对 "mostly sorted" 的数组进行排序，首先通过随机化主元选择，您可以在实践中更接近预期的 运行 时间。
理想情况下，您希望选择一个能够平均划分子问题的支点，这有多种变体，其中选择随机元素只是其中之一。另一个，我见过的另一种策略是对数组进行采样，选择 5 个元素，然后使用中位数。 （编辑：从另一个回答来看，DualPivotQuicksort实际上是这种风格，有7个样本点，然后分成三个分区。这种方法没有随机性，而是抽样。）
最后，这就是为手头的特定任务找到最快或最有效的变体。如果您对所排序内容的底层结构有更多信息，则可以调整算法的变体，使其在您的数据集上更成功。在图书馆中，您通常希望速度很快，但在面对 "misuse" 时也可以预测。这就是为什么像这样在已经排序的数组上具有良好性能的方法是一个很好的选择。
你没有说 哪个 Java 实现所以我假设你指的是 java.util.DualPivotQuicksort.
class 不会选择随机枢轴。事实上，它从子数组中选取 7 个等距的候选主元，对它们进行排序，并使用第 3 个和第 5 个作为（双）主元。
例外情况：
- 小数组/子数组使用插入排序进行排序。
byte 的数组使用插入排序或计数排序进行排序。
（注意：这是基于Java 7 / 8 中的实现）
我在 java 中查看了 DualPivotQuicksort class 的实现细节。
就算法而言，它肯定是 Quicksort 的变体，尽管没有意义的是在基准选择中引入随机性的方式，从而确保算法在 预期 运行 O (n lg (n)) 的时间。
我参考了几篇论文，但它们或多或少地解释了算法，而不是解决如何处理枢轴选择的随机性或者不是很明确：
简单快速排序实现的最坏情况发生在输入已经根据你的主元策略排序时，比如如果选择主元作为子数组的第一个元素，你将得到最坏的情况运行 时间，如果你的元素已经有序。因为我们经常对 "mostly sorted" 的数组进行排序，首先通过随机化主元选择，您可以在实践中更接近预期的 运行 时间。
理想情况下，您希望选择一个能够平均划分子问题的支点，这有多种变体，其中选择随机元素只是其中之一。另一个，我见过的另一种策略是对数组进行采样，选择 5 个元素，然后使用中位数。 （编辑：从另一个回答来看，DualPivotQuicksort实际上是这种风格，有7个样本点，然后分成三个分区。这种方法没有随机性，而是抽样。）
最后，这就是为手头的特定任务找到最快或最有效的变体。如果您对所排序内容的底层结构有更多信息，则可以调整算法的变体，使其在您的数据集上更成功。在图书馆中，您通常希望速度很快，但在面对 "misuse" 时也可以预测。这就是为什么像这样在已经排序的数组上具有良好性能的方法是一个很好的选择。
你没有说 哪个 Java 实现所以我假设你指的是 java.util.DualPivotQuicksort.
class 不会选择随机枢轴。事实上，它从子数组中选取 7 个等距的候选主元，对它们进行排序，并使用第 3 个和第 5 个作为（双）主元。
例外情况：
- 小数组/子数组使用插入排序进行排序。
byte的数组使用插入排序或计数排序进行排序。
（注意：这是基于Java 7 / 8 中的实现）