我对中位数算法的中位数不了解
Something I dont understand about median of medians algorithm
关于中位数的算法，我有些不明白。
这个算法的一个关键步骤是找到一个近似的中位数，根据Wikipedia，我们可以保证这个近似的中位数大于初始集合元素的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%？？？？
感谢您的回复！！
我完全同意你的分析，直到你得到五个元素的每个块的中值，当你剩下这个元素集合时：
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 个百分位数之间。
如果这看起来令人困惑，请不要担心 - 您的陪伴非常好。这个算法是出了名的难以理解。对我来说，理解它的最简单方法就是相信递归是有效的，并且只在一层深处追踪它，在所有递归调用都有效的假设下工作，而不是试图一直走到底部递归树。
您对中位数算法感到困惑的原因是，虽然中位数 return 是实际中位数 20% 以内的近似结果，但在算法的某些阶段我们还需要计算确切的中位数。如果将两者混为一谈，您将得不到预期的结果，如您的示例所示。
中位数中位数使用三个函数作为其构建块：
medianOfFive(array, first, last) {
// ...
return median;
}
此函数 return 是数组（的一部分）中五个（或更少）元素的精确中值。有几种方法可以对此进行编码，例如基于排序网络或插入排序。细节对于这个问题并不重要，但重要的是要注意这个函数 return 是精确的中位数，而不是近似值。
medianOfMedians(array, first, last) {
// ...
return median;
}
此函数 return 是数组（部分）中值的近似值，保证大于 30% 的最小元素，小于 30% 的最大元素。我们将在下面详细介绍。
select(array, first, last, n) {
// ...
return element;
}
此函数return是数组（的一部分）中的第 n 个最小元素。此函数也是 return 的精确结果，而不是近似值。
在最基本的情况下，整个算法的工作原理如下：
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)
}
所以这就是你计算错误的地方。在创建一个包含五位数中位数的数组后，您再次对该数组使用中位数函数，它给出了中位数 (27) 的近似值，但在这里您需要实际中位数 (1038)。
这一切听起来相当简单，但变得复杂的是函数 select() 调用 medianOfMedians() 以获得中位数的初步估计，然后使用它来计算准确的中位数，所以你得到一个双向递归，其中两个函数相互调用。当为 25 个或更少的元素调用 medianOfMedians() 时，此递归停止，因为那时只有 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 组，每组五个）：
#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
用主元 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 个元素中寻找第 4 - 2 - 1 = 1 个元素：
五个中位数作为枢轴：
1043
用主元 1043 划分的五个中位数的范围（取决于方法）：
small: 1038
pivot: 1043
large: 1048, 1053
小的部分只有一个元素，我们是找第一个元素，所以可以return小的元素1038.
你会看到，1038就是原来的25个五中位数的中位数，原来125的数组中还有62个更小的值：
1 ~ 27, 1001 ~ 1011, 1013 ~ 1023, 1025 ~ 1037
这不仅将它置于 30~70% 的范围内，而且意味着它实际上是准确的中位数（请注意，这是这个特定示例的巧合）。
关于中位数的算法，我有些不明白。 这个算法的一个关键步骤是找到一个近似的中位数，根据Wikipedia，我们可以保证这个近似的中位数大于初始集合元素的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%？？？？
感谢您的回复！！
我完全同意你的分析，直到你得到五个元素的每个块的中值，当你剩下这个元素集合时：
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 个百分位数之间。
如果这看起来令人困惑，请不要担心 - 您的陪伴非常好。这个算法是出了名的难以理解。对我来说，理解它的最简单方法就是相信递归是有效的，并且只在一层深处追踪它，在所有递归调用都有效的假设下工作，而不是试图一直走到底部递归树。
您对中位数算法感到困惑的原因是，虽然中位数 return 是实际中位数 20% 以内的近似结果，但在算法的某些阶段我们还需要计算确切的中位数。如果将两者混为一谈，您将得不到预期的结果，如您的示例所示。
中位数中位数使用三个函数作为其构建块：
medianOfFive(array, first, last) {
// ...
return median;
}
此函数 return 是数组（的一部分）中五个（或更少）元素的精确中值。有几种方法可以对此进行编码，例如基于排序网络或插入排序。细节对于这个问题并不重要，但重要的是要注意这个函数 return 是精确的中位数，而不是近似值。
medianOfMedians(array, first, last) {
// ...
return median;
}
此函数 return 是数组（部分）中值的近似值，保证大于 30% 的最小元素，小于 30% 的最大元素。我们将在下面详细介绍。
select(array, first, last, n) {
// ...
return element;
}
此函数return是数组（的一部分）中的第 n 个最小元素。此函数也是 return 的精确结果，而不是近似值。
在最基本的情况下，整个算法的工作原理如下：
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)
}
所以这就是你计算错误的地方。在创建一个包含五位数中位数的数组后，您再次对该数组使用中位数函数，它给出了中位数 (27) 的近似值，但在这里您需要实际中位数 (1038)。
这一切听起来相当简单，但变得复杂的是函数 select() 调用 medianOfMedians() 以获得中位数的初步估计，然后使用它来计算准确的中位数，所以你得到一个双向递归，其中两个函数相互调用。当为 25 个或更少的元素调用 medianOfMedians() 时，此递归停止，因为那时只有 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 组，每组五个）：
#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
用主元 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 个元素中寻找第 4 - 2 - 1 = 1 个元素：
五个中位数作为枢轴：
1043
用主元 1043 划分的五个中位数的范围（取决于方法）：
small: 1038
pivot: 1043
large: 1048, 1053
小的部分只有一个元素，我们是找第一个元素，所以可以return小的元素1038.
你会看到，1038就是原来的25个五中位数的中位数，原来125的数组中还有62个更小的值：
1 ~ 27, 1001 ~ 1011, 1013 ~ 1023, 1025 ~ 1037
这不仅将它置于 30~70% 的范围内，而且意味着它实际上是准确的中位数（请注意，这是这个特定示例的巧合）。