java快速排序选择策略如何影响快速排序的总体Bigoh行为？

# 2 楼答案

您应该知道的一个重要事实是，在不同元素的数组中，随机选择分区的快速排序将在O（n lg n）中运行。关于这一点有很多很好的证明，而且the one on Wikipedia实际上对此进行了很好的讨论。如果你愿意去做一个稍微不太正式的证明，它大部分在数学上是合理的，那么直觉如下。每当我们选择一个支点时，假设一个“好”支点是一个支点，它至少给我们75%/25%的分割；也就是说，它至少大于25%的元素，最多大于75%的元素。我们希望在算法终止之前，限制我们可以获得此类枢轴的次数。假设我们得到这样的K分裂，并考虑这样生成的最大子问题的大小。它的大小最多为（3/4）^kn，因为在每次迭代中，我们至少要去掉四分之一的元素。如果考虑K＝log＞3/4＞/Sub＞（1／n）＝log＞4/3＜/Sub＞n的具体情况，则选择K优枢轴后的最大子问题的大小为1，递归将停止。这意味着，如果我们选择GetO（lgn）good pivots，递归将终止。但在每次迭代中，获得这样一个支点的机会有多大？如果我们随机地选择枢轴，那么有50%的可能性是在元素的中间50%，所以在我们得到一个好的枢轴之前，我们会选择两个随机的枢轴。选择一个支点的每一步都需要O（n）个时间，因此在获得每个好支点之前，我们应该花费大约O（n）个时间。因为我们最多得到O（lgn）个好的支点，所以整个运行时是O（nlgn）

上述讨论中的一个重要细节是，如果你用任何常数分割代替75%/25%分割，比如（100-k%）/k%分割，则过渐近分析是相同的。你会发现快速排序平均需要O（n lgn）个时间

我提到这个证明的原因是，它为您提供了一个很好的框架来思考如何在快速排序中选择轴心点。如果你能在每一个iTartion上选择一个非常接近中间的轴心，你就可以保证O（n lgn）运行时。如果您不能保证在任何迭代中都能获得一个好的轴心，但可以说，在获得一个好的轴心之前，您只需要一个恒定的迭代次数，那么您还可以保证O（n lg n）个预期的运行时

请看一下你提出的枢轴方案。对于（a），如果数组是随机的，那么在每个步骤中选择第一个元素作为轴与选择一个随机轴基本相同，因此通过上面的分析，您将得到预期的O（n lg n）运行时。对于（b），如果您知道数组大部分已排序，则选择中值是一个好策略。原因是，如果我们可以说每个元素都“非常接近”它在排序序列中应该位于的位置，那么您可以提出一个论点，即您选择的每个枢轴都是一个好的枢轴，为您提供了所需的O（n lg n）运行时。（术语“非常接近”在数学上不是很精确，但我认为如果你愿意的话，你可以不费吹灰之力将其形式化）

至于（c）和（d），在这两个函数中，（d）是唯一保证在期望值上得到O（n lgn）的函数。如果您决定性地选择某些元素用作枢轴，则您的算法将容易受到确定性序列的攻击，这些确定性序列可能会将其退化为O（n²）行为。实际上，McIlroy有一篇非常有趣的文章，名为"A Killer Adversary for Quicksort"，它描述了如何通过使用恶意比较函数来接受任何确定性快速排序并为其构造病理学上最坏情况的输入。在任何真正的快速排序实现中，您几乎肯定希望避免这种情况，因为否则恶意用户可能会通过输入这些杀手序列来对您的代码发起DoS攻击，从而迫使您的程序按二次时间排序，从而挂起。另一方面，因为（d）正在拾取其采样点s随机，它不易受到此攻击，因为在任何序列上，轴的选择都是随机的

有趣的是，对于（d），虽然选择三个随机元素并取中间值没有什么坏处，但您不需要这样做。前面的证明足以表明，通过一个随机轴心选择，您将得到预期的O（n lgn）。事实上，我不知道选取三个随机值的中值是否会提高快速排序算法的性能，尽管由于快速排序总是Ω（n lg n），它肯定不会比仅仅选取随机元素作为枢轴更好

我希望这能有所帮助-我真的很喜欢快速排序算法和构建良好的快速排序实现所涉及的所有设计决策。：-）

共 (3) 个答案

# 1 楼答案

您必须了解，已经有许多算法允许您维持O（nlog（n））复杂性。使用randomized quick sort预期时间复杂度为O（nlog（n）），通常被认为比其他方法更好

如果您将以上所有内容混合使用，即根据输入数据集的“配置文件”有条件地应用其中一项，则您将能够维持O（nlog（n））。也就是说，对输入数据集本身进行分类是一项挑战。在任何情况下，为了做得更好，您必须研究您的输入数据集，并选择可能的替代方案
# 2 楼答案

您应该知道的一个重要事实是，在不同元素的数组中，随机选择分区的快速排序将在O（n lg n）中运行。关于这一点有很多很好的证明，而且the one on Wikipedia实际上对此进行了很好的讨论。如果你愿意去做一个稍微不太正式的证明，它大部分在数学上是合理的，那么直觉如下。每当我们选择一个支点时，假设一个“好”支点是一个支点，它至少给我们75%/25%的分割；也就是说，它至少大于25%的元素，最多大于75%的元素。我们希望在算法终止之前，限制我们可以获得此类枢轴的次数。假设我们得到这样的K分裂，并考虑这样生成的最大子问题的大小。它的大小最多为（3/4）^kn，因为在每次迭代中，我们至少要去掉四分之一的元素。如果考虑K＝log＞3/4＞/Sub＞（1／n）＝log＞4/3＜/Sub＞n的具体情况，则选择K优枢轴后的最大子问题的大小为1，递归将停止。这意味着，如果我们选择GetO（lgn）good pivots，递归将终止。但在每次迭代中，获得这样一个支点的机会有多大？如果我们随机地选择枢轴，那么有50%的可能性是在元素的中间50%，所以在我们得到一个好的枢轴之前，我们会选择两个随机的枢轴。选择一个支点的每一步都需要O（n）个时间，因此在获得每个好支点之前，我们应该花费大约O（n）个时间。因为我们最多得到O（lgn）个好的支点，所以整个运行时是O（nlgn）

上述讨论中的一个重要细节是，如果你用任何常数分割代替75%/25%分割，比如（100-k%）/k%分割，则过渐近分析是相同的。你会发现快速排序平均需要O（n lgn）个时间

我提到这个证明的原因是，它为您提供了一个很好的框架来思考如何在快速排序中选择轴心点。如果你能在每一个iTartion上选择一个非常接近中间的轴心，你就可以保证O（n lgn）运行时。如果您不能保证在任何迭代中都能获得一个好的轴心，但可以说，在获得一个好的轴心之前，您只需要一个恒定的迭代次数，那么您还可以保证O（n lg n）个预期的运行时
请看一下你提出的枢轴方案。对于（a），如果数组是随机的，那么在每个步骤中选择第一个元素作为轴与选择一个随机轴基本相同，因此通过上面的分析，您将得到预期的O（n lg n）运行时。对于（b），如果您知道数组大部分已排序，则选择中值是一个好策略。原因是，如果我们可以说每个元素都“非常接近”它在排序序列中应该位于的位置，那么您可以提出一个论点，即您选择的每个枢轴都是一个好的枢轴，为您提供了所需的O（n lg n）运行时。（术语“非常接近”在数学上不是很精确，但我认为如果你愿意的话，你可以不费吹灰之力将其形式化）

至于（c）和（d），在这两个函数中，（d）是唯一保证在期望值上得到O（n lgn）的函数。如果您决定性地选择某些元素用作枢轴，则您的算法将容易受到确定性序列的攻击，这些确定性序列可能会将其退化为O（n²）行为。实际上，McIlroy有一篇非常有趣的文章，名为"A Killer Adversary for Quicksort"，它描述了如何通过使用恶意比较函数来接受任何确定性快速排序并为其构造病理学上最坏情况的输入。在任何真正的快速排序实现中，您几乎肯定希望避免这种情况，因为否则恶意用户可能会通过输入这些杀手序列来对您的代码发起DoS攻击，从而迫使您的程序按二次时间排序，从而挂起。另一方面，因为（d）正在拾取其采样点s随机，它不易受到此攻击，因为在任何序列上，轴的选择都是随机的

有趣的是，对于（d），虽然选择三个随机元素并取中间值没有什么坏处，但您不需要这样做。前面的证明足以表明，通过一个随机轴心选择，您将得到预期的O（n lgn）。事实上，我不知道选取三个随机值的中值是否会提高快速排序算法的性能，尽管由于快速排序总是Ω（n lg n），它肯定不会比仅仅选取随机元素作为枢轴更好

我希望这能有所帮助-我真的很喜欢快速排序算法和构建良好的快速排序实现所涉及的所有设计决策。：-）
# 3 楼答案

最好的支点是能够将数组精确地分成两半的支点。阵列的中值是最佳选择。我将建议这种方法：-
select some random indexes calculate median of these elements Use this as pivot element

从O（n）中值查找算法来看，我认为5个随机索引应该足够了

Python中文网

有 Java 编程相关的问题?

java快速排序选择策略如何影响快速排序的总体Bigoh行为？

共 (3) 个答案

# 1 楼答案

# 2 楼答案

# 3 楼答案