Найти медиану N 8-битных чисел

Используйте нечто похожее на сортировку подсчетом.

• Создайте массив «counts» размером 256, инициализированный всеми нулями. counts[x] будет количеством раз, когда x появляется во входном массиве.
• Перебирайте свой входной массив, увеличивая значение в позиции в массиве counts, соответствующем каждому значению во входном массиве (так что counts[input[i]]++).
• Перебирайте массив counts, суммируя все значения, пока не получите половину общего количества значений. Индекс будет числом, которое мы ищем (некоторая дополнительная логика, необходимая для работы с четным числом значений).

Это выполняется за O(n) времени с использованием O(1) пространства (что асимптотически оптимально).

Что-то вроде: (псевдокод)

// Count the number of occurrences of each value.
counts[256] = {0}
for i = 0 to input.length
   counts[input[i]]++

// Get the median.
count = input.length
sum = 0
if count divisible by 2
   first = NaN
   for i = 0 to counts.length
      sum += counts[i]
      if first == NaN && sum >= count / 2
         first = i
      if sum >= count / 2 + 1
         median = (first + i) / 2
         break
else
   for i = 0 to counts.length
      sum += counts[i]
      if sum >= (count + 1) / 2
         median = i
         break
return median

Существуют и другие способы достижения той же временной и пространственной сложности (хотя и немного более сложные, чем приведенные выше, и требующие изменения входного массива):

• Вариант быстрой сортировки, который оптимизирован для повторяющихся значений путем разделения массива на 3 вместо 2 на каждом шаге (меньшие, равные и большие значения).

• Вариант сортировки по основанию, который используется на месте.

• Алгоритм медианы медиан также фактически разделяет эту сложность.