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

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

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

Алгоритм

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

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

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

Ссылки

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

Counting sort

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