关于中位数的算法，我有些不明白。 关于这个算法的一个关键步骤是找到一个近似的中位数，根据维基百科，我们可以保证这个近似中位数大于初始集合元素的 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%！！
所以我的问题是：我错在哪里？为什么在我的情况下，近似中位数不大于元素的 30%????
感谢您的回复！！
您对中位数算法感到困惑的原因是，虽然中位数在实际中位数的 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)
}
所以这就是你的计算出错的地方。创建中位数为 5 的数组后，您再次在此数组上使用中位数函数，这为您提供了中位数的近似值 (27)，但这里您需要实际中位数 (1038)。
这一切听起来都相当简单，但变得复杂的是函数 select() 调用 medianOfMedians() 来获得中位数的第一个估计值，然后使用它来计算确切的中位数，所以你会得到一个双向递归，其中两个函数相互调用。当 medianOfMedians() 被调用 25 个或更少的元素时，这种递归停止，因为那时只有 5 个中位数，而不是使用 select() 来查找它们的中位数，它可以使用 medianOfFive()。
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 划分的 5 个中位数(取决于方法)：
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
使用枢轴 1058 划分的 5 个中位数范围(取决于方法)：
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 划分的 5 的中位数范围(取决于方法)：
small: 1022, 1027
pivot: 1031
large: 1038, 1043, 1048, 1053
较小的部分有 2 个元素，较大的部分有 4 个元素，所以现在我们寻找 4 - 2 - 1 = 4 个元素中的第 1 个：
中位数为 5 作为枢轴：
1043
使用枢轴 1043 划分的 5 个中位数范围(取决于方法)：
small: 1038
pivot: 1043
large: 1048, 1053
较小的部分只有一个元素，我们正在寻找第一个元素，因此我们可以返回小元素 1038。
如您所见，1038 是原始 25 个中位数的确切中位数，而原始数组中的 125 个值有 62 个较小的值：
1 ~ 27, 1001 ~ 1011, 1013 ~ 1023, 1025 ~ 1037
这不仅把它放在30~70%的范围内，而且意味着它实际上是确切的中位数(注意，这是这个特定例子的巧合)。
我完全支持你的分析，直到你得到五个元素块中每个元素的中位数，当你剩下这个元素集合时：
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 个百分位数之间。
如果这看起来令人困惑，请不要担心 - 你真的是很好的公司。这个算法是出了名的难以理解。对我来说，理解它的最简单方法是相信递归有效，并且只深入一层，假设所有递归调用都有效，而不是试图一直走到递归树的底部。