Сортировка подсчётом :: Counting sort
Базовый алгоритм. В "чистом" виде не встречается, однако лежит в основе многих сортировок распределением. В частности, сортировка царя Соломона, мелькающая сортировка и бисерная сортировка являются разновидностями данного метода.
Алгоритм
Подсчитываем сколько раз в массиве встречается каждое значение и заполняем массив подсчитанными элементами в соответствующих количествах. Счётчики для всего диапазона чисел создаются зараннее (изначально равны нулю).
Голубиная сортировка почти идентичная этому алгоритму, за исключением того, что счётчики создаются только тогда, когда число встречается при просмотре массива.
Характеристики алгоритма
| Название | Сортировка подсчётом (Counting sort) | |
|---|---|---|
| Автор | Гарольд Сьюард (Harold H. Seward) | |
| Год | 1954 | |
| Класс | Сортировки распределением | |
| Устойчивость | Да | |
| Сравнения | Нет | |
| Сложность по времени | Худшая | O(n + k) |
| Средняя | O(n + k) | |
| Лучшая | O(n) | |
| Сложность по памяти | Общая | O(n + k) |
| Дополнительная | O(k) | |
Сортировка подсчётом
Реализация на различных ЯП