Похоже, что другие ответы используют сортировку. Это не оптимально с точки зрения производительности, потому что это занимает O(n logn) время. Вместо этого можно рассчитать медиану в O(n) времени. Обобщенная версия этой проблемы известна как «статистика n-порядка», что означает нахождение элемента K в наборе, в котором у нас n элементов меньше или равно K, а остальные больше или равны K. Таким образом, статистика 0-го порядка будет минимальной элемент в наборе (примечание: в некоторых источниках используется индекс от 1 до N вместо 0 до N-1). Медиана - это просто (Count-1)/2 -статистическая статистика.
Ниже приведен код, принятый из Введение в алгоритмы Кормена и др., 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);
}
Несколько заметок:
- Этот код заменяет хвостовой рекурсивный код из исходной версии книги в итерационный цикл.
- Это также устраняет ненужную дополнительную проверку из исходной версии, когда start == end.
- Я предоставил две версии Median, одна из которых принимает IEnumerable, а затем создает список. Если вы используете версию, которая принимает IList, имейте в виду, что она изменяет порядок в списке.
- Вышеуказанные методы вычисляют медиану или любую статистику i-порядка в
O(n) ожидаемое время . Если вы хотите 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+ вы можете добавить атрибут
MethodImplOptions.AggressiveInlining в метод Swap<T> для немного улучшенной производительности.