了解“中位数的中位数”算法

我想了解以下示例的“中位数”算法：

我们有 45 个不同的数字，分为 9 组，每组 5 个元素。

48 43 38 33 28 23 18 13 8

49 44 39 34 29 24 19 14 9 

50 45 40 35 30 25 20 15 10

51 46 41 36 31 26 21 16 53

52 47 42 37 32 27 22 17 54

1. 第一步是对每个组进行排序（在本例中它们已经排序）

2. 递归地第二步，找到中位数的“真实”中位数（50 45 40 35 30 25 20 15 10）即该集合将被分为 2 组：

   50 25
   
   45 20 
   
   40 15
   
   35 10
   
   30
   

   对这 2 组进行排序

   30 10
   
   35 15 
   
   40 20
   
   45 25
   
   50
   

中位数是 40 和 15（如果数字是偶数，我们取左边的中位数） 所以返回的值为 15，但是中位数的“真实”中位数（50 45 40 35 30 25 20 15 10) 为 30，此外还有 5 个小于 15 的元素，远小于 45 中提到的 30%维基百科 http://en.wikipedia.org/wiki/Selection_algorithm#Linear%5Fgeneral%5Fselection%5Falgorithm%5F-%5F.22Median%5Fof%5FMedians%5Falgorithm.22

and so T(n) <= T(n/5) + T(7n/10) + O(n) fails.

顺便说一句，在维基百科的例子中，我得到的递归结果是 36。然而，真正的中位数是 47。

所以，我认为在某些情况下，这种递归可能不会返回中位数的真实中位数。我想了解我的错误在哪里。

这里是伪代码 http://www.ics.uci.edu/~eppstein/161/960130.html对于中位数算法的中位数（稍微修改以适合您的示例）。维基百科中的伪代码未能描述其内部工作原理selectIdx函数调用。

我已在代码中添加了注释以进行解释。

// L is the array on which median of medians needs to be found.
// k is the expected median position. E.g. first select call might look like:
// select (array, N/2), where 'array' is an array of numbers of length N

select(L,k)
{

    if (L has 5 or fewer elements) {
        sort L
        return the element in the kth position
    }

    partition L into subsets S[i] of five elements each
        (there will be n/5 subsets total).

    for (i = 1 to n/5) do
        x[i] = select(S[i],3)

    M = select({x[i]}, n/10)

    // The code to follow ensures that even if M turns out to be the
    // smallest/largest value in the array, we'll get the kth smallest
    // element in the array

    // Partition array into three groups based on their value as
    // compared to median M

    partition L into L1<M, L2=M, L3>M

    // Compare the expected median position k with length of first array L1
    // Run recursive select over the array L1 if k is less than length
    // of array L1
    if (k <= length(L1))
        return select(L1,k)

    // Check if k falls in L3 array. Recurse accordingly
    else if (k > length(L1)+length(L2))
        return select(L3,k-length(L1)-length(L2))

    // Simply return M since k falls in L2
    else return M

}

以你的例子为例：

中位数函数的中位数将在 45 个元素的整个数组上调用，例如（k = 45/2 = 22):

median = select({48 49 50 51 52 43 44 45 46 47 38 39 40 41 42 33 34 35 36 37 28 29 30 31 32 23 24 25 26 27 18 19 20 21 22 13 14 15 16 17 8 9 10 53 54}, 45/2)

1. 第一次M = select({x[i]}, n/10)被称为，数组{x[i]}将包含以下数字：50 45 40 35 30 20 15 10。 在这次通话中，n = 45，因此 select 函数调用将是M = select({50 45 40 35 30 20 15 10}, 4)

2. 第二次M = select({x[i]}, n/10)被称为，数组{x[i]}将包含以下数字：40 20。 在这次通话中，n = 9因此电话将是M = select({40 20}, 0)。 此选择调用将返回并分配值M = 20.
   
   现在，到了您有疑问的地步，我们现在对数组进行分区L around M = 20 with k = 4.
   
   记住数组L这是：50 45 40 35 30 20 15 10.
   
   该数组将被划分为L1, L2 and L3按照规则L1 < M, L2 = M and L3 > M。因此：
   L1: 10 15
L2: 20
L3: 30 35 40 45 50
   
   Since k = 4，它大于length(L1) + length(L2) = 3。因此，现在将通过以下递归调用继续搜索：
   return select(L3,k-length(L1)-length(L2))
   
   翻译过来就是：
   return select({30 35 40 45 50}, 1)
   
   结果将返回 30。 （由于 L 有 5 个或更少的元素，因此它将返回第 k 个元素，即排序数组中的第一个位置，即 30）。

Now, M = 30将在第一时间收到select对 45 个元素的整个数组进行函数调用，以及分隔数组的相同分区逻辑L around M = 30将应用于最终获得中位数的中位数。

唷！我希望我能够足够详细和清晰地解释中位数算法的中位数。