我正在研究基于Select 算法的快速排序变体实现的快速排序变体实现，以选择一个好的枢轴元素。传统的智慧似乎是将数组划分为 5 个元素块，取每个块的中值，然后递归地对生成的中值应用相同的块方法以获得“中值的中值”。
让我困惑的是选择 5 元素块而不是 3 元素块。对于 5 元素块，在我看来，您执行n/4 = n/5 + n/25 + n/125 + n/625 + ...的是 5 的中位数操作，而对于 3 元素块，您执行n/2 = n/3 + n/9 + n/27 + n/81 + ...的是 3 的中位数操作。由于每个 5 的中位数是 6 次比较，每个 3 的中位数是 2 次比较，这导致3*n/2使用 5 的中位数和n进行比较和使用中位数 3 进行比较。
谁能解释这种差异，以及使用 5 元素块的动机是什么？我不熟悉应用这些算法的通常做法，所以也许有一些方法可以减少一些步骤，并且仍然“足够接近”中位数以确保良好的枢轴，并且这种方法更适用于 5 元素块?
原因是通过选择 3 个块，我们可能会失去 O(n) 时间算法的保证。
对于 5 个块，时间复杂度为
T(n) = T(n/5) + T(7n/10) + O(n)
对于 3 块，结果是
T(n) = T(n/3) + T(2n/3) + O(n)
看看这个：http ://www.cs.berkeley.edu/~luca/w4231/fall99/slides/l3.pdf
我相信这与确保“好的”分裂有关。划分为 5 个元素块可确保最坏情况下的拆分为 70-30。标准参数是这样的：在n/5块中，至少一半的中位数 >= 中位数的中位数，因此至少一半的n/5块有至少 3 个元素（5 个中的 1/2）>= 中位数-中位数，这给出了一个3n/10分裂，这意味着另一个分区是7n/10最坏的情况。
这给了T(n) = T(n/5) + T(7n/10) + O(n).
因为n/5 + 7n/10 < 1，最坏情况下的运行时间是O(n)。
选择 3 元素块使得它：至少一半的n/3块具有至少 2 个元素 >= 中位数的中位数，因此这给出了n/3拆分，或者2n/3在最坏的情况下。
这给了T(n) = T(n/3) + T(2n/3) + O(n).
在这种情况下，n/3 + 2n/3 = 1，所以它在最坏的情况下减少到O(n log n)。
您可以使用大小为 3 的块！是的，我和你一样惊讶。2014 年（你在 2010 年问过）有一篇论文展示了如何做到这一点。
这个想法如下：而不是做median3, partition, median3, partition, ...，你做median3, median3, partition, median3, median3, partition, ... 。在论文中，这被称为“重复步骤算法”。
所以而不是：
T(n) <= T(n/3) + T(2n/3) + O(n)
T(n) = O(nlogn)
一个得到：
T(n) <= T(n/9) + T(7n/9) + O(n)
T(n) = Theta(n)
上述文章是K. Chen 和 A. Dumitrescu 的Select with Groups of 3 or 4 Takes Linear Time (2014, arxiv)，或Select with groups of 3 or 4 (2015, author's homepage)。
PS：A. Alexandrescu（以 D 语言闻名！）的《快速确定性选择》展示了如何更有效地实现上述内容。