c# - 在 C# 中计算中位数

Question

我需要编写接受小数数组并找到中位数的函数。

.net Math 库中有函数吗？

Answer 1

看起来其他答案正在使用排序。从性能的角度来看，这不是最优的，因为它需要 O(n logn)时间。可以在 O(n) 中计算中位数时间代替。这个问题的广义版本被称为“n 阶统计”，这意味着在集合中找到一个元素 K，使得我们有 n 个元素小于或等于 K，其余元素大于或等于 K。因此 0 阶统计将是最小的集合中的元素(注意:一些文献使用从 1 到 N 的索引，而不是 0 到 N-1)。中位数就是 (Count-1)/2 -订单统计。

以下是从 Cormen 等人的《算法导论》第 3 版中采用的代码。

/// <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);
}

一些注意事项:

1. 此代码将书中原始版本的尾递归代码替换为迭代循环。
2. 它还消除了原始版本在 start==end 时不必要的额外检查。
3. 我提供了两个版本的 Median，一个接受 IEnumerable 然后创建一个列表。如果您使用接受 IList 的版本，请记住它会修改列表中的顺序。
4. 以上方法计算 O(n) 中的中位数或任何 i-order 统计数据预计时间。如果你想要O(n) 最坏的情况下然后有使用中位数的技术。虽然这会提高最坏情况下的性能，但它会降低平均情况，因为 O(n) 中的常量现在更大了。但是，如果您主要计算非常大的数据的中位数，那么它值得一看。
5. NthOrderStatistics 方法允许传递随机数生成器，该生成器随后将用于在分区期间选择随机基准。这通常是不必要的，除非您知道您的数据具有某些模式，因此最后一个元素不会足够随机，或者如果您的代码以某种方式暴露在外部以进行有针对性的利用。
6. 如果你有奇数个元素，中位数的定义就很清楚了。它只是索引为 (Count-1)/2 的元素在排序数组中。但是当你有偶数个元素时 (Count-1)/2不再是整数，您有两个中位数:中位数下限 Math.Floor((Count-1)/2)和 Math.Ceiling((Count-1)/2) .一些教科书使用较低的中位数作为“标准”，而其他教科书则建议使用两个的平均值。这个问题对于 set of 2 elements 变得尤为重要。上面的代码返回较低的中位数。如果你想要 lower 和 upper 的平均值，那么你需要调用上面的代码两次。在这种情况下，请务必测量数据的性能，以决定是否应使用上述代码还是直接排序。
7. 对于 .net 4.5+，您可以添加 MethodImplOptions.AggressiveInlining Swap<T> 上的属性略微提高性能的方法。