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