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