中位数算法的解释

Question

Median of medians方法在quicksort类型的分区算法中非常流行，可以产生一个相当不错的基准点，使得它可以将数组均匀地划分。其逻辑在维基百科中给出如下所示：

选择的基准点对于中位数列表中约n/10个元素（每半部分为1/2 * (n/5)）都小于和大于一半的元素。其中每个元素都是5个中位数之一，因此它比块外的两个元素小，比另外两个元素大。因此，基准点小于块外的3(n/10)个元素，并且大于块外的另外3(n/10)个元素。因此，所选的中位数将元素分割在30%/70%和70%/30%之间，这保证了算法的最坏情况下具有线性行为。

能否有人为我稍微解释一下？我发现很难理解这个逻辑。

- SexyBeast

Answer 1

想想下面这组数字：

5 2 6 3 1

这些数字的中位数是3。现在如果你有一个数字n，如果n > 3，那么它比上面至少一半的数字都大。如果n < 3，那么它比上面至少一半的数字都小。

这就是思路。也就是说，对于每组5个数字，您得到它们的中位数。现在你有n / 5个数字。这是显然的。

现在如果你得到这些数字的中位数（称为m），它比其中一半大，比另一半小（根据中位数的定义！）。换句话说，m比n/10个数字更大（它们本身是小的5元素组的中位数），而且比另外n/10个数字更大（它们再次是小的5元素组的中位数）。

在上面的例子中，我们看到如果中位数是k，并且您有m > k，则m还比其他2个数字大（它们本身小于k）。这意味着对于每个那些m比它的中位数大的较小的5元素组，m也比另外两个数字大。这使得每个n/10小的5元素组中至少有3个数字（2个数字+中位数本身）比m小。因此，m至少大于3n/10个数字。

对于m比其大的元素数量的逻辑类似。

- Shahbaz

---

另一个问题，这个方法如何保证这个数字将成为中位数？中位数是将数组分为上下两半的数字。那么这个30-30-70的数字代表什么意思？ - SexyBeast

嗯，中位数在中间，但是上面的文本中的 m 不是所有数字的中位数。它只是其中 1/5 数字的中位数（它们本身是较小的 5 元素组的中位数）。请仔细阅读最后一段。最后得出结论，即 m 大于至少 3n/10 的数字，这意味着 m 大于至少 30% 的数字。因此，最终结果是 m 大于至少 30%，小于至少另外 30%。还有 40% 的数字我们不确定。 - Shahbaz

那么为什么它平均会给出50-50的分区呢？50-50的分区是由正常的中位数给出的，对吧？ - SexyBeast

平均而言，快速排序并不会将数组以50-50的比例分割。它通常会在30-70和70-30之间进行分割（也许你可以将其称为平均50-50？），但这不是重点。为了使快速排序的时间复杂度达到O(nlogn)，它需要能够按照数组大小的比例划分数组。这才会产生logn的递归深度。30-70的分割已经给出了一个3n/10和7n/10的比例，与n成比例。因此，即使它不是完美的50-50，它仍然会产生对数级别的递归深度（只是它的对数底数不是2，而是10/7）。 - Shahbaz