algorithm - Medians of Medians算法的解释

Question

中位数的中位数 方法在quicksort 类型的分区算法中非常流行，可以产生相当好的主元，从而均匀地分区数组。其逻辑在维基百科中给出为:

The chosen pivot is both less than and greater than half of the elements in the list of medians, which is around n/10 elements (1/2 * (n/5)) for each half. Each of these elements is a median of 5, making it less than 2 other elements and greater than 2 other elements outside the block. Hence, the pivot is less than 3(n/10) elements outside the block, and greater than another 3(n/10) elements outside the block. Thus the chosen median splits the elements somewhere between 30%/70% and 70%/30%, which assures worst-case linear behavior of the algorithm.

有人可以为我解释一下吗？我发现很难理解其中的逻辑。

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 )。这意味着对于那些较小的 5 个元素组中的每一个，其中 m大于中位数，m也大于其他两个数字。这使得每个 n / 10 中至少有 3 个数字(2 个数字 + 中位数本身)小 5 元素组，小于 m .因此，m至少大于 3n/10数。

元素个数的类似逻辑m大于。