我需要编写一个函数来接受十进制数数组，并找到其中位数。
.net Math库中是否有此功能？
12个回答
91
看起来其他答案正在使用排序。从性能角度来看，这不是最优的，因为它需要 O(n logn) 的时间。实际上可以在 O(n) 的时间内计算中位数。此问题的广义版本称为 "n阶统计"，意思是在一个集合中找到元素K，使得我们有 n 个小于或等于 K 的元素，其余的大于或等于 K。因此，0阶统计将是集合中的最小元素（注意：有些文献使用索引从1到 N 而不是0到N-1）。中位数仅仅是 (Count-1)/2 阶统计。
下面是摘自 Cormen 等人的 "算法导论" 第三版的代码。
下面是摘自 Cormen 等人的 "算法导论" 第三版的代码。
/// <summary>
/// Partitions the given list around a pivot element such that all elements on left of pivot are <= pivot
/// and the ones at thr right are > pivot. This method can be used for sorting, N-order statistics such as
/// as median finding algorithms.
/// Pivot is selected ranodmly if random number generator is supplied else its selected as last element in the list.
/// Reference: Introduction to Algorithms 3rd Edition, Corman et al, pp 171
/// </summary>
private static int Partition<T>(this IList<T> list, int start, int end, Random rnd = null) where T : IComparable<T>
{
if (rnd != null)
list.Swap(end, rnd.Next(start, end+1));
var pivot = list[end];
var lastLow = start - 1;
for (var i = start; i < end; i++)
{
if (list[i].CompareTo(pivot) <= 0)
list.Swap(i, ++lastLow);
}
list.Swap(end, ++lastLow);
return lastLow;
}
/// <summary>
/// Returns Nth smallest element from the list. Here n starts from 0 so that n=0 returns minimum, n=1 returns 2nd smallest element etc.
/// Note: specified list would be mutated in the process.
/// Reference: Introduction to Algorithms 3rd Edition, Corman et al, pp 216
/// </summary>
public static T NthOrderStatistic<T>(this IList<T> list, int n, Random rnd = null) where T : IComparable<T>
{
return NthOrderStatistic(list, n, 0, list.Count - 1, rnd);
}
private static T NthOrderStatistic<T>(this IList<T> list, int n, int start, int end, Random rnd) where T : IComparable<T>
{
while (true)
{
var pivotIndex = list.Partition(start, end, rnd);
if (pivotIndex == n)
return list[pivotIndex];
if (n < pivotIndex)
end = pivotIndex - 1;
else
start = pivotIndex + 1;
}
}
public static void Swap<T>(this IList<T> list, int i, int j)
{
if (i==j) //This check is not required but Partition function may make many calls so its for perf reason
return;
var temp = list[i];
list[i] = list[j];
list[j] = temp;
}
/// <summary>
/// Note: specified list would be mutated in the process.
/// </summary>
public static T Median<T>(this IList<T> list) where T : IComparable<T>
{
return list.NthOrderStatistic((list.Count - 1)/2);
}
public static double Median<T>(this IEnumerable<T> sequence, Func<T, double> getValue)
{
var list = sequence.Select(getValue).ToList();
var mid = (list.Count - 1) / 2;
return list.NthOrderStatistic(mid);
}
几点说明：
- 此代码将尾递归代码从原始版本中替换为迭代循环。
- 它还消除了原始版本在start==end时进行的不必要的额外检查。
- 我提供了两个版本的Median，一个接受IEnumerable然后创建列表。如果您使用接受IList的版本，则请记住它会修改列表中的顺序。
- 上面的方法在
O(n)期望时间内计算中位数或任何i-order统计信息。如果你想要O(n)最坏情况下的时间，那么有一种技术可以使用中位数。虽然这会改善最坏情况的性能，但平均情况下会降低常量在O(n)中。但是，如果您主要在非常大的数据上计算中位数，则值得一看。 - NthOrderStatistics方法允许传递随机数生成器，然后在分区期间使用随机枢轴。除非您知道您的数据具有某些模式，以使最后一个元素不够随机，否则通常不需要这样做，或者如果某种方式您的代码暴露在外，供有目的的利用。
- 如果您有奇数个元素，则中位数的定义很清楚。它只是排序数组中索引为
(Count-1)/2的元素。但是，当您有偶数个元素(Count-1)/2不再是一个整数，您有两个中位数：下中位数Math.Floor((Count-1)/2)和Math.Ceiling((Count-1)/2)。一些教科书使用下中位数作为“标准”，而其他人建议使用两者的平均值。对于2个元素的集合，这个问题变得尤为关键。上面的代码返回下中位数。如果您想要下限和上限的平均值，则需要两次调用上面的代码。在这种情况下，请确保测量您的数据的性能，以决定是否应该使用上述代码VS直接排序。 - 对于.NET 4.5+，可以在Swap<T>方法上添加
MethodImplOptions.AggressiveInlining属性以稍微提高性能。
- Shital Shah
10
52
感谢Rafe，这考虑到了你的回答者提出的问题。
public static double GetMedian(double[] sourceNumbers) {
//Framework 2.0 version of this method. there is an easier way in F4
if (sourceNumbers == null || sourceNumbers.Length == 0)
throw new System.Exception("Median of empty array not defined.");
//make sure the list is sorted, but use a new array
double[] sortedPNumbers = (double[])sourceNumbers.Clone();
Array.Sort(sortedPNumbers);
//get the median
int size = sortedPNumbers.Length;
int mid = size / 2;
double median = (size % 2 != 0) ? (double)sortedPNumbers[mid] : ((double)sortedPNumbers[mid] + (double)sortedPNumbers[mid - 1]) / 2;
return median;
}
- Jason Jakob
5
为什么这个函数在这里是静态的？ - richieqianle
2@richieqianle：因为所有可以是静态的东西都应该是静态的。从虚拟函数表的角度来看，这更有效。 - abatishchev
1@abatishchev 在C＃中，默认情况下，方法不是虚拟的（与Java相反）。但即使它是，性能也不是使某些东西静态或非静态的真正糟糕的原因。在这个答案中更好的原因可能是如果该方法是一些实用程序方法的类型，其中不需要类的任何实例。 - MakePeaceGreatAgain
@HimBromBeere：“不需要类的任何实例”基本上等同于“所有可以是静态的东西都应该是静态的”。 - abatishchev
2@abatishchev 我同意，对于这个问题使用静态是完全可以的。 - DavidGuaita
49
Math.NET 是一个开源库，提供一种计算中位数的方法。 Nuget 包名为 MathNet.Numerics。
使用方法非常简单：
using MathNet.Numerics.Statistics;
IEnumerable<double> data;
double median = data.Median();
- NePh
1
你好，感谢提供的信息。我想知道是否有类似的用法来计算众数而不是中位数？我在文档 https://numerics.mathdotnet.com/api/MathNet.Numerics.Statistics/Statistics.htm#Median 中找不到相关内容。 - Lod
32
decimal Median(decimal[] xs) {
Array.Sort(xs);
return xs[xs.Length / 2];
}
这应该就可以解决问题。
-- 编辑 --
对于那些想要完整的解决方案，这里是完整、简洁、纯净的解决方案（假定输入数组非空）：
decimal Median(decimal[] xs) {
var ys = xs.OrderBy(x => x).ToList();
double mid = (ys.Count - 1) / 2.0;
return (ys[(int)(mid)] + ys[(int)(mid + 0.5)]) / 2;
}
- Rafe
4
10这是
O(n log n)。可以在O(n)的时间内找到中位数。另外，如果数组长度为偶数，则此方法无法返回中位数（应该是排序后中间两个元素的平均值）。 - jason6可以，但问题没有提到O(n)是要求，并且关于偶数或空的情况，留给学生作为练习。 - Rafe
8这也修改了你传递给该方法的数组，这很愚蠢。 - Gleno
7@Gleno，我认为规范并没有具体说明这一点（好吧，我是按照C#中'function'的意思解释的，因为它可以产生副作用）。目标只是简单地展示一个简短的答案。 - Rafe
27
.net Math库中有这样的函数吗？
没有。
不过自己写也不难。朴素算法是对数组排序，然后选择中间（或两个中间数的平均值）元素。但是，该算法的时间复杂度为O(n log n)，而可以在O(n)时间内解决此问题。您需要查看选择算法以获得此类算法。
- jason
5
这是Jason回答的通用版本：
/// <summary>
/// Gets the median value from an array
/// </summary>
/// <typeparam name="T">The array type</typeparam>
/// <param name="sourceArray">The source array</param>
/// <param name="cloneArray">If it doesn't matter if the source array is sorted, you can pass false to improve performance</param>
/// <returns></returns>
public static T GetMedian<T>(T[] sourceArray, bool cloneArray = true) where T : IComparable<T>
{
//Framework 2.0 version of this method. there is an easier way in F4
if (sourceArray == null || sourceArray.Length == 0)
throw new ArgumentException("Median of empty array not defined.");
//make sure the list is sorted, but use a new array
T[] sortedArray = cloneArray ? (T[])sourceArray.Clone() : sourceArray;
Array.Sort(sortedArray);
//get the median
int size = sortedArray.Length;
int mid = size / 2;
if (size % 2 != 0)
return sortedArray[mid];
dynamic value1 = sortedArray[mid];
dynamic value2 = sortedArray[mid - 1];
return (value1 + value2) / 2;
}
- Will Calderwood
4
我的观点是（因为它似乎更直接/简单，并且对于简短的列表已经足够）：
public static T Median<T>(this IEnumerable<T> items)
{
var i = (int)Math.Ceiling((double)(items.Count() - 1) / 2);
if (i >= 0)
{
var values = items.ToList();
values.Sort();
return values[i];
}
return default(T);
}
附注：按照ShitalShah的描述，使用“更高的中位数”。
- mike
2
在未来的某个时候。我认为这是最简单的形式。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Median
{
class Program
{
static void Main(string[] args)
{
var mediaValue = 0.0;
var items = new[] { 1, 2, 3, 4,5 };
var getLengthItems = items.Length;
Array.Sort(items);
if (getLengthItems % 2 == 0)
{
var firstValue = items[(items.Length / 2) - 1];
var secondValue = items[(items.Length / 2)];
mediaValue = (firstValue + secondValue) / 2.0;
}
if (getLengthItems % 2 == 1)
{
mediaValue = items[(items.Length / 2)];
}
Console.WriteLine(mediaValue);
Console.WriteLine("Enter to Exit!");
Console.ReadKey();
}
}
}
- Krishneil
1
你实际上可以不使用if语句。只需设置
medianValue = (items[items.Length / 2] + items[(items.Length - 1) / 2])/2。感谢整数除法，对于数组中的奇数项，您将获得相同的项两次，当您将其加起来然后除以二时，您将得到相同的数字。对于偶数项，您将获得两个不同的索引。您也可以考虑保留原样以保持清晰度，但这种方式更为简洁。 - Tom H2
这里是一个 QuickSelect 实现。它是从这篇 文章 中采用的一份
unsafe 的 C 代码实现，比较了几种算法并发现 QuickSelect 平均速度最快。 [MethodImpl(MethodImplOptions.AggressiveInlining)]
private static unsafe void SwapElements(int* p, int* q)
{
int temp = *p;
*p = *q;
*q = temp;
}
public static unsafe int Median(int[] arr, int n)
{
int middle, ll, hh;
int low = 0; int high = n - 1; int median = (low + high) / 2;
fixed (int* arrptr = arr)
{
for (;;)
{
if (high <= low)
return arr[median];
if (high == low + 1)
{
if (arr[low] > arr[high])
SwapElements(arrptr + low, arrptr + high);
return arr[median];
}
middle = (low + high) / 2;
if (arr[middle] > arr[high])
SwapElements(arrptr + middle, arrptr + high);
if (arr[low] > arr[high])
SwapElements(arrptr + low, arrptr + high);
if (arr[middle] > arr[low])
SwapElements(arrptr + middle, arrptr + low);
SwapElements(arrptr + middle, arrptr + low + 1);
ll = low + 1;
hh = high;
for (;;)
{
do ll++; while (arr[low] > arr[ll]);
do hh--; while (arr[hh] > arr[low]);
if (hh < ll)
break;
SwapElements(arrptr + ll, arrptr + hh);
}
SwapElements(arrptr + low, arrptr + hh);
if (hh <= median)
low = ll;
if (hh >= median)
high = hh - 1;
}
}
}
- eladm
1
CenterSpace的NMath库提供了一个函数：
double[] values = new double[arraySize];
double median = NMathFunctions.Median(values);
如果您的数组可能包含null值，您可以选择使用NaNMedian，但是您需要将数组转换为向量：
double median = NMathFunctions.NaNMedian(new DoubleVector(values));
CenterSpace的NMath库并非免费，但许多大学都有许可证
- soxfan04
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
rnd.Next(start, end)替换为rnd.Next(start, end + 1)以避免排除end作为一个枢轴。其次，如果数组包含许多相同的值，则该算法会变成O(n^2)。为了避免这种情况，在Partition<T>()中添加一个检查，如果pivot与list[prevPivotIndex]相同，则返回end。 - G. Cohenrnd.Next(start, end+1)很好的发现。但是如果枢轴与最后一个相同，我不确定是否返回最后一个。我需要考虑一下这个问题... - Shital Shah