Сортировка подсчётом :: Counting sort

Сортировка подсчётом

Базовый алгоритм. В "чистом" виде не встречается, однако лежит в основе многих сортировок распределением. В частности, сортировка царя Соломона, мелькающая сортировка и бисерная сортировка являются разновидностями данного метода.

Алгоритм

Подсчитываем сколько раз в массиве встречается каждое значение и заполняем массив подсчитанными элементами в соответствующих количествах. Счётчики для всего диапазона чисел создаются зараннее (изначально равны нулю).

Голубиная сортировка почти идентичная этому алгоритму, за исключением того, что счётчики создаются только тогда, когда число встречается при просмотре массива.

Характеристики алгоритма

НазваниеСортировка подсчётом (Counting sort)
АвторГарольд Сьюард (Harold H. Seward)
Год1954
КлассСортировки распределением
УстойчивостьДа
СравненияНет
Сложность по времениХудшаяO(n + k)
СредняяO(n + k)
ЛучшаяO(n)
Сложность по памятиОбщаяO(n + k)
ДополнительнаяO(k)

Ссылки

Сортировки распределением

Сортировка подсчётом

Counting sort

Реализация на различных ЯП