java - 快速排序-枢轴选择策略如何影响快速排序的整体Big-oh行为？

Question

我已经提出了几种策略，但是我不完全确定它们如何影响整体行为。我知道平均情况是O(NlogN)，所以我认为答案在某处。我只想将NlogN + 1用于如果我只是选择数组中的第一项作为快速排序的枢纽，但是我不知道这是否正确还是可以接受？如果有人能启发我这个话题，那将是很棒的。谢谢!

可能的策略:

a)数组是随机的:选择第一项，因为这是最具成本效益的选择。

b)数组大部分是排序的:选择中间项，这​​样我们很可能会赞扬每次拆分一半的二进制递归。

c)数组相对较大:选择数组中的第一个，中间和最后一个索引并进行比较，选择最小的索引以确保避免出现最坏的情况。

d)对随机生成的索引执行“c”，以减少选择的确定性。

Answer 1

您应该知道的重要事实是，在一系列不同的元素中，具有随机选择的分区的快速排序将在O(n lg n)中运行。有很多很好的证明，并且the one on Wikipedia实际上对此进行了很好的讨论。如果您愿意使用稍微不那么正式的证明(在数学上基本上是合理的)，那么直觉如下。每当我们选择一个枢轴时，就说一个“好的”枢轴是至少给我们带来了75％/25％分割的枢轴。也就是说，它大于至少25％的元素，最多大于75％的元素。我们希望限制在算法终止之前可以得到这种支点的次数。假设我们得到了k个此类拆分，并考虑了以此方式生成的最大子问题的大小。它的大小最大为(3/4)kn，因为在每次迭代中，我们都至少去除了四分之一的元素。如果我们考虑k = log3/4(1/n)= log4/3 n的特定情况，那么在选择了k个良好的枢轴之后，最大子问题的大小将为1，并且递归将停止。这意味着，如果我们选择获得O(lg n)好的枢轴，则递归将终止。但是在每次迭代中，获得这种枢轴的机会是什么？好吧，如果我们随机选择枢轴，那么它有50％的机会位于元素的中间50％，依此类推，在获得良好的枢轴之前，我们将选择两个随机枢轴。选择枢纽的每个步骤都需要O(n)时间，因此在获得每个良好枢纽之前，我们应该花费大约O(n)时间。由于我们最多获得O(lg n)个良好的支点，因此总体运行时间为预期的O(n lg n)。

上面讨论中的一个重要细节是，如果将75％/25％的拆分替换为任何恒定的拆分(例如，(100-k％)/k％的拆分)，则渐近分析是相同的。您将获得quicksort平均花费O(n lg n)的时间。

我之所以提到此证明，是因为它为您提供了一个很好的框架，供您考虑如何选择快速排序中的枢轴。如果您可以选择在每次迭代中都非常接近中间位置的枢轴，则可以保证O(n lg n)运行时。如果您不能保证在任何迭代中都能获得良好的支点，但是可以说，在获得良好支点之前仅需要进行恒定数量的迭代，那么您也可以保证O(n lg n)预期的运行时间。

鉴于此，让我们看一下您提议的数据透视方案。对于(a)，如果数组是随机的，则选择第一个元素作为枢轴与在每一步中选择一个随机枢轴基本相同，因此通过以上分析，您将获得期望的O(n lg n)运行时。对于(b)，如果您知道该数组大部分已排序，则选择中位数是一个很好的策略。原因是，如果我们可以说每个元素都与排序序列中的元素“非常接近”，那么您可以提出一个论点，即您选择的每个枢轴都是一个很好的枢轴，为您提供O(n lg n )您想要的运行时。 (“非常接近”一词在数学上不是很精确，但是我想如果需要的话，可以将其形式化而不会太费力)。

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

有趣的是，对于(d)，虽然选择三个随机元素并取中位数没有什么坏处，但您不需要这样做。较早的证明足以表明，通过一个随机的枢轴选择，您将获得O(n lg n)的期望值。我实际上不知道选择三个随机值的中位数是否会提高快速排序算法的性能，尽管由于快速排序始终为Ω(n lg n)，所以与选择随机元素作为渐近点相比，它肯定不会渐近地好。枢轴。

我希望这会有所帮助-我真的很喜欢quicksort算法以及构建良好的quicksort实现所涉及的所有设计决策。 :-)