Sex*_*ast 12 algorithm quicksort median median-of-medians
该Median of medians方法在quicksort类型分区算法中非常流行,以产生相当好的枢轴,从而统一分区数组.其逻辑在维基百科中给出:
所选择的枢轴小于和大于中位数列表中元素的一半,每半个元素大约为n/10个元素(1/2*(n/5)).这些元素中的每一个都是5的中值,使得它少于2个其他元素并且在块之外大于2个其他元素.因此,枢轴在块外部小于3(n/10)个元素,并且大于块外的另外3个(n/10)个元素.因此,所选择的中值将元素分成介于30%/ 70%和70%/ 30%之间的某个位置,这确保了算法的最坏情况线性行为.
有人可以为我清楚地解释一下.我发现很难理解逻辑.
Sha*_*baz 14
想想以下几组数字:
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个数字+中位数本身),小于5 m.因此,m至少比3n/10数字更大.
元素数量的类似逻辑m大于.