我刚刚回答了一个关于在快速实施中选择分区的不同方法的问题，并提出了一个我真的不知道如何回答的问题 . 这有点数学，这可能是错误的网站，所以如果这需要移动请告诉我，我很乐意将其迁移到其他地方 .
它's well-known that a quicksort implementation that picks its pivots uniformly at random will end up running in expected O(n lg n) time (there'是一个很好的证据on Wikipedia） . 然而，由于生成随机数的成本，许多快速排序实现不会随机选择枢轴，而是依赖于确定性地选择三个元素并且选择中值作为枢轴的方法 . 众所周知，在最坏的情况下退化为O（n2）（例如，参见如何生成那些最坏情况输入的this great paper） .
现在，假设我们通过从序列中挑选三个随机元素并使用它们的中位数作为枢轴的选择来实现这两种方法 . 我知道这也保证了O（n lg n）平均情况运行时使用的证据与常规随机快速排序的证明略有不同 . 但是，我不知道在这个特定的快速排序实现中，n ng n项前面的常数因子是什么 . 对于常规随机快速排序维基百科列出随机快速排序的实际运行时间最多需要1.39 n lg n比较（使用lg作为二进制对数） .
我的问题是： does anyone know of a way to derive the constant factor for the number of comparisons made using a "median-of-three" randomized quicksort ？如果我们更普遍地说，使用随机的k中值方法是否存在关于快速排序的常数因子的表达式？能够说随机化的快速排序与随机中位数为六的枢轴选择使得比较最少，这真是太酷了吗？或者能够最终说你应该随机选择一个枢轴元素？
5 回答
通常的随机快速排序的常量很容易计算，因为比较两个元素k个位置的概率正好是2 /（k 1）：这两个元素中的一个被选为k之前的任意k的概率它们之间的-1个元素 . 不幸的是，你的算法没有那么聪明 .
我犹豫是否尝试你的粗体问题，因为我可以回答你的问题：渐渐地说，没有"sweet spot" . 计算k个元素的中位数（甚至是O（n1-ε）元素）的总增加成本是线性的，并且n log n项的常数随着阵列被更均匀地分割而减小 . 捕获当然是线性项上的常量，这是非常不切实际的，突出了渐近分析的一个缺点 .
根据我在下面的评论，我猜0 <α<1的k = O（nα）是"sweet spot" .
这是常量的启发式推导 . 我认为它可以做得很严谨，付出更多的努力 .
令P为连续随机变量，其值为[0,1] . 直观地，P是小于枢轴的值的分数 . 我们正在寻找这样的常数c
c n lg n = E [n c P n lg（P n）c（1-P）n lg（（1-P）n）] .
稍后我们有一点代数
c = 1 / E [-P lg P - （1-P）lg（1-P））] .
换句话说，c是具有平均值P的伯努利分布的预期熵的倒数 . 直观地，对于每个元素，我们需要以产生大约lg n位信息的方式将其与枢轴进行比较 .
当P是均匀的时，P的pdf是1.常数是
当枢轴的中位数为3时，P的pdf为6 x（1 - x） . 常数是
如果集合的初始状态是随机排序的，那么您将获得完全相同的常数因子，用于随机选择三个项目来计算中位数，如同确定性地选择三个项目时一样 .
随机挑选项目的动机是确定性方法会给出比平均值更差的结果 . 如果确定性方法给出了良好的中位数，则无法通过随机选择项目来改进它 .
因此，哪种方法给出最佳结果取决于输入数据，不能为每个可能的组确定 .
降低常数因子的唯一可靠方法是增加用于计算中位数的项目数，但在某些时候计算中位数将比获得更好的中位数值所获得的更高 .
是的，它确实 . C standard library's qsort function的作者Bentley和McIlroy写道在他们的论文中，Engineering a Sort Function以下数字：
1.386 n lg使用第一个，中间或随机枢轴进行平均比较
1.188 n lg n平均比较使用3个数据点的中位数
1.094 n lg n平均比较使用3个中位数的中位数
根据上述论文：
只是一个想法：如果你使用三分之一的方法，并且你发现它更好，为什么不使用五分之一或十一分之一的方法呢？当你在它上面的时候，也许你可以想到一个中位数的优化......嗯......好吧，这显然是一个坏主意（因为你必须对你的序列进行排序......） .
基本上，要选择您的pivot元素作为m的中间元素，您可以对这些m元素进行排序，对吧？因此，我只是猜测，你正在寻找的常数之一是"2"：通过首先排序3个元素来选择你的数据透视表，你执行了多少额外的比较？让我们说它2.你在快速反应中一遍又一遍地做到这一点 . 一个基本的结论是，3的中位数比简单的随机快速排序慢2倍 .
但是这里有什么用呢？你得到了更好的设备和征服分配，你可以更好地防止退化的情况（一点点） .
所以，回到我开头的臭名昭着的问题：为什么不从m的中位数选择枢轴元素，m是5,7，n / 3，左右 . 必须有一个甜蜜的地方，m元素的分类比从更好的分而治之行为和快速排序的收益更糟糕 . 我想，这个甜蜜点很早就出现了 - 如果选择3的中位数，你必须首先对抗2比较的常数因子 . 我承认，值得一个实验，但我不会过分期待结果:-)但如果我错了，收益很大：不要停在3！