Medians算法中值的解释
Median of medians方法在quicksort类型的分区算法Median of medians非常受欢迎，以产生一个相当不错的支点，从而使其统一划分数组。 其逻辑在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比另外两个数字更大。 这使得在n / 10个小5个元素组中每个小于3个数字（2个数字+中位数本身）小于m 。 因此， m至少大于3n/10数字。
元素数目m类似逻辑大于。
可以在这里找到用于查找第n个最大的整数n的中值 - 中值算法的说明：http://cs.indstate.edu/~spitla/presentation.pdf
链接地址: http://www.djcxy.com/p/83825.html