algorithm - 使用随机三中位数的快速排序是否比随机快速排序明显更好？

Question

我刚刚回答了一个关于在快速排序实现中选择分区的不同方法的问题，然后提出了一个老实说我不知道​​如何回答的问题。这有点数学重，而且这可能是问这个问题的错误站点，所以如果需要移动，请告诉我，我很乐意将它迁移到其他地方。

众所周知，随机统一选择其枢轴的快速排序实现将在预期的 O(n lg n) 时间内运行(有一个很好的证明 on Wikipedia )。然而，由于生成随机数的成本，许多快速排序实现不会随机选择主元，而是依赖于“三个中位数”方法，在该方法中确定性地选择三个元素，并选择其中的中位数作为枢。众所周知，在最坏的情况下，这会退化为 O(n²)(例如，有关如何生成那些最坏情况的输入，请参阅 this great paper)。

现在，假设我们通过从序列中选取三个随机元素并使用它们的中值作为基准选择来组合这两种方法。我知道这也保证了 O(n lg n) 平均情况运行时间，使用的证明与常规随机快速排序的证明略有不同。但是，我不知道在这个特定的快速排序实现中 n lg n 项前面的常数因子是什么。对于常规的随机快速排序，维基百科列出了随机快速排序的实际运行时间，最多需要 1.39 n lg n 次比较(使用 lg 作为二进制对数)。

我的问题是:有没有人知道使用“三中位数”随机快速排序得出比较次数常数因子的方法？如果我们走得更一般，是否有使用随机中值 k 方法的快速排序常数因子的表达式？我很好奇，因为我认为看看这种方法是否有一些比其他随机快速排序实现更少的比较的“最佳点”会很有趣。我的意思是，如果能够说随机快速排序和随机的 6 个中位数选择进行最少的比较，这不是很酷吗？或者能够得出结论，您应该随机选择一个枢轴元素？

Answer 1

这是常量的启发式推导。我认为它可以变得更严格，需要付出更多的努力。

设 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，常数为

In[1]:= -1/NIntegrate[x Log[2, x] + (1 - x) Log[2, 1 - x], {x, 0, 1}]

Out[1]= 1.38629

当pivot为中位数3时，P的pdf为6 x (1 - x)。常数是

In[2]:= -1/NIntegrate[6 x (1 - x) (x Log[2, x] + (1 - x) Log[2, 1 - x]), {x, 0, 1}]

Out[2]= 1.18825