关于中位数算法的中位数，我不了解

Question

关于中位数的算法，有一点我不明白。这个算法的一个关键步骤是找到一个近似的中位数，根据维基百科，我们保证这个近似的中位数大于初始集元素的30%。

为了找到这个近似中位数，我们计算每组5个元素的中位数，将这些中位数聚集在一个新的集合中，然后重新计算中位数，直到获得的集合至少包含5个元素。在这种情况下，我们得到集合的中值。（如果我的解释不清楚，请参阅维基百科页面。）

但是，请考虑以下125个元素:

1 2 3 1001 1002
4 5 6 1003 1004
7 8 9 1005 1006
1020 1021 1022 1023 1034 
1025 1026 1027 1028 1035 

10 11 12 1007 1008
13 14 15 1009 1010
16 17 18 1011 1013
1029 1030 1031 1032 1033 
1036 1037 1038 1039 1040 

19 20 21 1014 1015
22 23 24 1016 1017
25 26 27 1018 1019
1041 1042 1043 1044 1045
1046 1047 1048 1049 1050

1051 1052 1053 1054 1055
1056 1057 1058 1059 1060
1061 1062 1063 1064 1065
1066 1067 1068 1069 1070
1071 1072 1073 1074 1075

1076 1077 1078 1079 1080
1081 1082 1083 1084 1085
1086 1087 1088 1089 1090
1091 1092 1093 1094 1095
1096 1097 1098 1099 1100 

因此，我们将集合划分为5个元素的组，计算并收集中位数，因此，我们获得以下集合:

3 6 9 1022 1207
12 15 18 1031 1038
21 24 27 1043 1048
1053 1058 1063 1068 1073
1078 1083 1088 1093 1098

我们重做相同的算法，得到以下集合：

9 18 27 1063 1068

所以我们得到了近似的中位数是27。但是这个数字大于或等于只有27个元素。27/125=21.6%

所以我的问题是：我错在哪里？？为什么在我的情况下，近似中值不大于元素的30%？？？？

谢谢你的回复！！

Answer 1

我完全按照你的分析，当你得到五个元素块中每个块的中位数时，当你剩下这个元素集合时：

3 6 9 1022 1207 12 15 18 1031 1038  21 24 27 1043 1048 1053 1058 1063 1068 1073 1078 1083 1088 1093 1098

你是对的，在这一点上，我们需要得到这个元素集合的中位数。然而，中位数算法实现这一目标的方式与你提出的不同。

在进行分析时，您尝试通过再次将输入拆分为大小为 5 的块并取每个块的中位数来获取这组值的中位数。但是，这种方法实际上不会为您提供中位数的中位数。（您可以通过注意您返回27来查看这一点，这不是该值集合的真正中位数）。

中位数算法实际上取回中位数的方法是递归调用整体算法来获取这些元素的中位数。这与反复将事物分解成块并计算每个块的中位数有微妙的不同。特别是，每个递归调用都会

• 通过使用五组启发式方法获得枢轴的估计值，
• 递归地调用自身上的函数以查找这些中位数的中位数，然后
• 对该中位数应用分区步骤，并使用它来确定如何从那里继续。

在我看来，这个算法太复杂了，无法用手进行实际跟踪。您确实需要相信这一点，因为您正在进行的每个递归调用都在一个比您开始时更小的数组上工作，所以每个递归调用确实会执行它所说的操作。所以当你像以前一样，只剩下每组的中值时，你应该相信当你需要通过递归调用得到中值时，最终得到的是真正的中值。

如果您查看在第一步中生成的中位数的真实中位数，您会发现它确实介于原始数据集的第30个和第70个百分位数之间。

如果这看起来令人困惑，别担心-你有一个很好的同伴。众所周知，这种算法很难理解。对我来说，理解它最简单的方法就是相信递归是有效的，并且只在一层的深度上进行跟踪，在所有递归调用都有效的假设下工作，而不是试图一直走到递归树的底部。

Answer 2

您对中位数算法感到困惑的原因是，虽然中位数返回实际中位数20%以内的近似结果，但在算法的某些阶段，我们还需要计算精确的中位数。如果你混淆了两者，你将得不到预期的结果，正如你的例子所展示的。

中间值使用三个函数作为其构建块:

medianOfFive(array, first, last) {
    // ...
    return median;
}

此函数返回数组（部分）中五个（或更少）元素的确切中位数。有几种方法可以对此进行编码，例如基于排序网络或插入排序。细节对于这个问题并不重要，但需要注意的是，此函数返回的是确切的中位数，而不是近似值。

medianOfMedians(array, first, last) {
    // ...
    return median;
}

此函数返回(部分)数组中值的近似值，保证大于30%最小元素，小于30%最大元素。我们将在下面详细讨论。

select(array, first, last, n) {
    // ...
    return element;
}

此函数返回数组（部分）的第 n 个最小元素。此函数也返回精确结果，而不是近似值。

最基本的是，整体算法的工作方式如下：

medianOfMedians(array, first, last) {
    call medianOfFive() for every group of five elements
    fill an array with these medians
    call select() for this array to find the middle element
    return this middle element (i.e. the median of medians)
}

所以这就是你计算错误的地方。在创建了一个具有五个中值的数组后，您再次对该数组使用了median-of-medians函数，它给出了一个中值的近似值(27)，但这里您需要的是实际的中值(1038)。

这一切听起来相当简单，但它变得复杂的地方是函数select（）调用mediasOfMedians（）来获得中位数的第一个估计值，然后用它来计算确切的中位数，所以你得到一个双向递归，其中两个函数相互调用。当 medianOfMedians（） 被调用 25 个或更少的元素时，这种递归停止，因为那时只有 5 个中位数，并且它可以使用 medianOfFive（） 而不是使用 select（） 来查找它们的中位数。

select（） 调用 medianOfMedians（） 的原因是它使用分区将数组拆分（部分）成大小接近相等的两个部分，并且它需要一个好的枢轴值来做到这一点。在将数组划分为两个部分后，其中的元素小于和大于透视，然后它会检查第n个最小元素所在的部分，并与此部分一起递归。如果具有较小值的零件的大小为 n-1，则枢轴是第 n 个值，不需要进一步的递归。

select(array, first, last, n) {
    call medianOfMedians() to get approximate median as pivot
    partition (the range of) the array into smaller and larger than pivot
    if part with smaller elements is size n-1, return pivot
    call select() on the part which contains the n-th element
}

如您所见，select（） 函数递归（除非枢轴恰好是第 n 个元素），但在数组的较小范围内，因此在某些点（例如两个元素）找到第 n 个元素将变得微不足道，不再需要进一步递归。

所以最后我们得到了更多的细节：

medianOfFive(array, first, last) {
    // some algorithmic magic ...
    return median;
}

medianOfMedians(array, first, last) {
    if 5 elements or fewer, call medianOfFive() and return result
    call medianOfFive() for every group of five elements
    store the results in an array medians[]
    if 5 elements or fewer, call medianOfFive() and return result
    call select(medians[]) to find the middle element
    return the result (i.e. the median of medians)
}

select(array, first, last, n) {
    if 2 elements, compare and return n-th element
    if 5 elements or fewer, call medianOfFive() to get median as pivot
    else call medianOfMedians() to get approximate median as pivot
    partition (the range of) the array into smaller and larger than pivot
    if part with smaller elements is size n-1, return pivot
    if n-th value is in part with larger values, recalculate value of n
    call select() on the part which contains the n-th element
}

示例

输入数组(125个值，25组，每组5个):

 #1    #2    #3    #4    #5    #6    #7    #8    #9    #10   #11   #12   #13   #14   #15   #16   #17   #18   #19   #20   #21   #22   #23   #24   #25

   1     4     7  1020  1025    10    13    16  1029  1036    19    22    25  1041  1046  1051  1056  1061  1066  1071  1076  1081  1086  1091  1096
   2     5     8  1021  1026    11    14    17  1030  1037    20    23    26  1042  1047  1052  1057  1062  1067  1072  1077  1082  1087  1092  1097
   3     6     9  1022  1027    12    15    18  1031  1038    21    24    27  1043  1048  1053  1058  1063  1068  1073  1078  1083  1088  1093  1098
1001  1003  1005  1023  1028  1007  1009  1011  1032  1039  1014  1016  1018  1044  1049  1054  1059  1064  1069  1074  1079  1084  1089  1094  1099
1002  1004  1006  1034  1035  1008  1010  1013  1033  1040  1015  1017  1019  1045  1050  1055  1060  1065  1070  1075  1080  1085  1090  1095  1100

五组的中间值（25个值）：

3, 6, 9, 1022, 1027, 12, 15, 18, 1031, 1038, 21, 24, 27, 1043,  
1048, 1053, 1058, 1063, 1068, 1073, 1078, 1083, 1088, 1093, 1098

五人组表示近似中位数：

 #1    #2    #3    #4    #5

   3    12    21  1053  1078
   6    15    24  1058  1083
   9    18    27  1063  1088
1022  1031  1043  1068  1096
1027  1038  1048  1073  1098

近似中位数为5的中位数:

9, 18, 27, 1063, 1088

近似中值作为轴心：

27

用枢轴27分区的五个中间（取决于方法）：

small: 3, 6, 9, 24, 21, 12, 15, 18
pivot: 27
large: 1031, 1038, 1027, 1022, 1043, 1048, 1053, 1058,  
       1063, 1068, 1073, 1078, 1083, 1088, 1093, 1098

较小的组有 8 个元素，较大的组有 16 个元素。我们一直在寻找25个元素中的第13个中间元素，所以现在我们寻找13 - 8 - 1 = 16个元素中的第4个元素：

五人组：

 #1    #2    #3    #4

1031  1048  1073  1098
1038  1053  1078
1027  1058  1083
1022  1063  1088
1043  1068  1093

五人组的中位数：

1031, 1058, 1083, 1098

近似中值作为轴心：

1058

用pivot 1058划分的五个中间值的范围(取决于方法):

small: 1031, 1038, 1027, 1022, 1043, 1048, 1053
pivot: 1058
large: 1063, 1068, 1073, 1078, 1083, 1088, 1093, 1098

较小的组有7个元素。我们在寻找16个元素中的第4个元素，所以现在我们在7个元素中寻找第4个元素：

五人组：

 #1    #2

1031  1048
1038  1053
1027
1022
1043

五人组的中位数：

1031, 1048

近似中值作为轴心：

1031

使用枢轴1031划分的五个中位数的范围（取决于方法）：

small: 1022, 1027
pivot: 1031
large: 1038, 1043, 1048, 1053

较小的部分有2个元素，较大的部分有4个元素，所以现在我们寻找4-2-1=4中的第一个元素：

五的中间值作为支点:

1043

用pivot 1043划分的五个中间值的范围(取决于方法):

small: 1038
pivot: 1043
large: 1048, 1053

较小的部分只有一个元素，我们正在寻找第一个元素，因此我们可以返回小元素1038。

正如您将看到的，1038是原始25个5的中位数的确切中位数，而原始125数组中有62个较小的值：

1 ~ 27, 1001 ~ 1011, 1013 ~ 1023, 1025 ~ 1037

这不仅将它放在30~70%的范围内，而且意味着它实际上是精确的中间值(注意，这是这个特定示例的巧合)。