Quicksort-枢轴选择策略如何影响quicksort的整体Big-oh行为？
我提出了几个策略，但我不完全确定它们如何影响整体行为。 我知道平均情况是O（NlogN），所以我认为这将是某个地方的答案。 如果我只选择数组中的第一项作为快速排序的枢轴，我想把NlogN + 1放入，但我不知道这是正确还是可接受？ 如果有人能够在这个主题上启发我会很棒。 谢谢！
可能的策略：
a）数组是随机的：选择第一项，因为这是最具成本效益的选择。
b）数组主要是排序的：选择中间项，这样我们很可能会赞美每次拆分的二进制递归。
c）数组相对较大：选择数组中的第一个，中间和最后一个索引并比较它们，选择最小的索引以确保避免最坏的情况。
d）使用随机生成的索引执行’c’，以使选择更不确定。
您应该知道的一个重要事实是，在一系列不同的元素中，随机选择分区的快速排序将以O（n lg n）运行。 有很多很好的certificate， 维基百科上的一个实际上对此有很好的讨论。 如果你愿意采用一种稍微不那么正式的证据，这种证据主要是数学上合理的，那么直觉如下。 每当我们选择一个支点时，让我们说一个“好”的支点是一个支点，它给我们至少75％/ 25％的分割; 也就是说，它大于至少25％的元素和至多75％的元素。 我们希望限制在算法终止之前我们可以获得此类数据的次数。 假设我们得到这种k分裂，并考虑以这种方式生成的最大子问题的大小。 它的大小最多为（3/4） k n，因为在每次迭代中我们都会消除至少四分之一的元素。 如果我们考虑k = log 3/4 （1 / n）= log 4/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％分裂 – 过度渐近分析是相同的。 平均而言，你会得到快速排序O（n lg n）时间。
我之所以提到这个certificate的原因是它为你提供了一个很好的框架来思考如何在快速排序中选择一个支点。 如果您可以在每个迭代中选择一个非常接近中间的数据透视表，则可以保证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（n 2 ）行为。 实际上有一篇非常有趣的论文被McIlroy称为“Quickort的杀手对手” ，它描述了如何通过使用恶意比较函数来获取任何确定性快速排序并为其构建病态最坏情况输入。 您几乎肯定希望在任何真正的快速排序实现中避免这种情况，因为否则恶意用户可以通过输入这些杀手序列来强制您的程序在二次时间内排序并因此挂起来对您的代码发起DoS攻击。 另一方面，因为（d）随机选取其样本点，所以它不容易受到这种攻击，因为在任何序列上，枢轴的选择是随机的。
有趣的是，对于（d），虽然选择三个随机元素并取中位数并没有什么坏处，但你不需要这样做。 早期的证据足以certificate你可以通过一个随机的枢轴选择得到O（n lg n）。 我实际上不知道选择三个随机值的中位数是否会提高快速排序算法的性能，但是因为快速排序总是Ω（n lg n），所以它肯定不会比仅选择随机元素更为渐近。支点。
我希望这有点帮助 – 我真的很喜欢快速排序算法和构建良好的快速排序实现所涉及的所有设计决策。 🙂
您必须了解已有许多算法可以让您维持O（nlog（n））复杂性。 使用随机快速排序预期时间复杂度为O（nlog（n）），并且通常被认为比其他方法更好。
如果您将上述所有内容混合使用，您将能够维持O（nlog（n）），即根据输入数据集的“配置文件”有条件地应用其中一个。 话虽如此，对输入数据集本身进行分类是一项挑战。 无论如何，要做得更好，您必须研究输入数据集并选择可能的替代方案。
最好的枢轴是能够将arrays精确分成两半的枢轴。 arrays的中位数当然是最佳选择。 我会建议这种方法： –
select some random indexes
calculate median of these elements
Use this as pivot element
从O（n）中值查找算法，我认为5个随机索引应该足够了。