该Median of medians方法在类型划分算法中非常流行，quicksort可以产生相当好的枢轴，从而均匀地划分数组。其逻辑在 Wikipedia 中给出为：
选择的枢轴小于和大于中位数列表中元素的一半，每半数约为 n/10 个元素 (1/2 * (n/5))。这些元素中的每一个都是 5 的中位数，使其小于块外的 2 个其他元素和大于 2 个其他元素。因此，主元小于块外的 3(n/10) 个元素，大于块外的另外 3(n/10) 个元素。因此，所选中值将元素拆分为 30%/70% 和 70%/30% 之间的某个位置，这确保了算法的最坏情况线性行为。
有人可以为我解释清楚一点。我发现很难理解其中的逻辑。
考虑以下一组数字：
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也大于其他两个数字。这使得在每个小的 5 个元素组中至少有 3 个数字（2 个数字 + 中位数本身），n / 10小于m. 因此，m至少大于3n/10数字。
元素数量的类似逻辑m大于。