Как найти медиану одномерного массива?

Question

[root09]

Приветствую. Как найти медиану массива без предварительной сортировки?

Answer 1

[Eddy_Em]

Когда-то давно я стащил из книжки с коллекцией сишных сниппетов быстрый поиск медианы. Вот код. Там не выполняется полная сортировка, а лишь ищется медиана. Если работать с указателями, то при вычислении скользящей медианы вычисления ускоряются.

Answer 2

[Sergey Aganezov]

топик на хабре
в Вашем случае k = [n / 2]

Answer 3

[15432]

Если заранее известен набор значений элементов массива (0..255), а количество элементов сильно больше набора значений (несколько тысяч), можно использовать гистограмму — считать количество элементов каждого значения (5 нулей, 340 единиц, 210 двоек… ) В гистограмме середину найти значительно проще (будет известно общее количество, достаточно суммировать количества в ячейках до превышения половины от общего числа. Элемент, на котором будет достигнута середина и будет медианой)
Данный подход очень сильно ускоряет медианную фильтрацию изображений с большим радиусом (обновление гистограммы можно нехило оптимизировать, обновляя лишь «края» при переходе к соседнему пикселю)