Временная сложность
Лучший: O(n + k)
Средний: O(n + k)
Худший: O(n + k)
Counting Sort — это алгоритм сортировки, не основанный на сравнении элементов. Он подсчитывает количество вхождений каждого значения и использует арифметические вычисления для определения их позиций.
Как это работает:
1. Найти диапазон входных значений (от минимума до максимума)
2. Создать массив подсчёта для хранения частоты встречаемости каждого значения
3. Изменить массив подсчёта, чтобы хранить накопленные суммы
4. Построить выходной массив, размещая элементы на соответствующих позициях
Временная сложность:
Лучший случай: O(n + k)
Средний случай: O(n + k)
Худший случай: O(n + k)
где k — диапазон входных значений
Пространственная сложность: O(n + k)
Свойства:
- Стабильная сортировка
- Не является сортировкой на месте
- Не основана на сравнении элементов
- Очень эффективна, когда k мало относительно n
Counting Sort идеально подходит для сортировки целых чисел в известном небольшом диапазоне. Также используется как вспомогательный алгоритм в Radix Sort.
Похожие алгоритмы
Частые вопросы
- Что такое Сортировка подсчётом (Counting Sort)?
- Counting Sort — это алгоритм сортировки, не основанный на сравнении элементов. Он подсчитывает количество вхождений каждого значения и использует арифметические вычисления для определения их позиций.
- Какова сложность Сортировка подсчётом (Counting Sort)?
- Время (среднее): O(n + k) · Память: O(n + k)
- Для кого предназначена визуализация Сортировка подсчётом (Counting Sort)?
- Визуализация Сортировка подсчётом (Counting Sort) рассчитана на средний уровень в категории «Сортировка». Полезна для студентов, подготовки к собеседованиям и практического изучения.
- Какие алгоритмы связаны с Сортировка подсчётом (Counting Sort)?
- В той же категории (Сортировка) вы можете изучить: Bubble Sort, Selection Sort, Insertion Sort. Каждый из них имеет интерактивную визуализацию.