java – Quicksort-枢轴选择策略如何影响quicksort的整体Big-o

您应该知道的一个重要事实是,在一系列不同的元素中,随机选择分区的快速排序将以O(n lg n)运行.有很多很好的证明,the one on Wikipedia实际上有很好的讨论.如果你愿意采用一种稍微不那么正式的证据,这种证据主要是数学上合理的,那么直觉如下.每当我们选择一个支点时,让我们说一个“好”的支点是一个支点,它给我们至少75％/ 25％的分割;也就是说,它大于至少25％的元素和至多75％的元素.我们希望限制在算法终止之前我们可以获得此类数据的次数.假设我们得到这种k分裂,并考虑以这种方式生成的最大子问题的大小.它的大小最多为(3/4)kn,因为在每次迭代时我们都会消除至少四分之一的元素.如果我们考虑k = log3 / 4(1 / n)= log4 / 3n的特定情况,那么选择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)时间.

我之所以提到这个证明的原因是它为你提供了一个很好的框架来思考如何在快速排序中选择一个支点.如果您可以在每个迭代中选择一个非常靠近中间的轴,则可以保证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”,描述了你如何通过使用恶意比较函数来获取任何确定性快速排序并为其构建病态最坏情况输入.您几乎肯定希望在任何真正的快速实施中避免这种情况,因为否则恶意用户可以通过输入这些杀手序列来强制您的程序在二次时间内排序并因此挂起来对您的代码发起DoS攻击.另一方面,因为(d)随机选取其样本点,所以它不容易受到这种攻击,因为在任何序列上,枢轴的选择是随机的.

有趣的是,对于(d),虽然选择三个随机元素并取中位数并没有什么坏处,但你不需要这样做.早期的证据足以证明你可以通过一个随机的枢轴选择得到O(n lg n).我实际上不知道选择三个随机值的中位数是否会提高快速排序算法的性能,但是因为快速排序总是Ω(n lg n),所以它肯定不会比仅选择随机元素更渐进.支点.

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!