的中位数算法中位数的说明中位数、算法
中位数的中位数的做法是非常流行的快速排序键入分割算法来产生一个相当不错的支点，这样的它划分阵列均匀。其逻辑是在维基百科给出的：
The Median of medians approach is very popular in quicksort type partitioning algorithms to yield a fairly good pivot, such that it partitions the array uniformly. Its logic is given in Wikipedia as:
所选择的枢轴比超过一半的元素的位数的每半个列表，是绕N / 10元件（1/2 *（N / 5））均不大。这些元素是5的中位数，使得它小于2其他元素和外块大于2的其他元素。因此，该枢轴是外块小于3（N / 10）的元素，和大于另一个3（N / 10）外块元素。因此所选择的中位数分割元件之间的30％/ 70％和70％/ 30％，这保证了该算法的最坏情况下的线性行为某处
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.
有人可以解释有点清晰地对我。我发现很难理解其中的逻辑。
Can somebody explain it a bit lucidly for me. I am finding it difficult to understand the logic.
推荐答案
想到的数字下面的一组：
Think of the following set of numbers:
5 2 6 3 1
这些数字的中位数是 3 。现在，如果你有多个 N ，如果 N'GT; 3 ，那么它是大于至少一半以上的数值。如果 N'LT; 3 ，则它比至少一半以上的数字。
The median of these numbers is 3. Now if you have a number n, if n > 3, then it is bigger than at least half of the numbers above. If n < 3, then it is smaller than at least half of the numbers above.
所以这就是这个想法。也就是说，对于每个集的5个数字，则得到他们的中位数。现在你有 N / 5 的数字。这是显而易见的。
So that is the idea. That is, for each set of 5 numbers, you get their median. Now you have n / 5 numbers. This is obvious.
现在，如果你得到这些数字（称之为 M ），它是大于一半的人并小于另一半的中位数（中值的定义！ ）。换句话说， M 大于 N / 10 号（这本身是小的5元组的中位数）和大于另一个 N / 10 号（这又回到了小的5元组的中位数）。
Now if you get the median of those numbers (call it m), it is bigger than half of them and smaller than the other half (by definition of median!). In other words, m is bigger than n / 10 numbers (which themselves were medians of small 5 element groups) and bigger than another n / 10 numbers (which again were medians of small 5 element groups).
在上面的例子中，我们看到，如果中位数 K 和你有 M＆GT;氏/ code>，然后 M 也大于其他2个号码（即是自己比 K ）。这意味着，对于每个那些规模较小的5元组，其中 M 是大于它的介质， M 也越大比其他两个数字。这使得至少有3个数字（2号+的中位数本身）在每个那些 N / 10 小的5元组，即比小米。因此， M 至少大于 3N / 10 的数字。
In the example above, we saw that if the median is k and you have m > k, then m is also bigger than 2 other numbers (that were themselves smaller than k). This means that for each of those smaller 5 element groups where m was bigger than its medium, m is bigger also than two other numbers. This makes it at least 3 numbers (2 numbers + the median itself) in each of those n / 10 small 5 element groups, that are smaller than m. Hence, m is at least bigger than 3n/10 numbers.
类似的逻辑元件的数量 M 比我的大。
Similar logic for the number of elements m is bigger than.
