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

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

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

Алгоритм

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

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

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

Ссылки

Сортировка подсчётом в Википедии
Counting sort on Wikipedia
Реализация на различных ЯП

Добавить комментарий