Алгоритмы и структуры данных

Поразрядная сортировка

Это алгоритм несравнительной сортировки, который используется для целых чисел или строк с представлениями фиксированной длины. Он сортирует элементы, обрабатывая отдельные цифры или символы от младшей значащей цифры до самой старшей.

Алгоритм:
1. Определить необходимое количество проходов (зависит от количества цифр или символов в максимальном элементе)
2. Создание 10 сегментов (0–9) для каждой позиции цифры (для чисел с основанием 10) или 26 сегментов (A–Z) для каждой позиции символа (для букв верхнего регистра).
3. Распределение элементов по сегментам, начиная с младшей значащей цифры.
4. Сортировка элементов в каждом сегменте, используя стабильный алгоритм сортировки
5. Формирование частично отсортированного массива.
6. Повторение процесса до тех пор пока не получится отсортированный массив.

Сложность:
В лучшем случаи: O(n)
В худшем: O(n*k)

www.tgoop.com/the_algorithms/4559

9.0K viewsSep 27, 2023 at 08:59

Поразрядная сортировка

Это алгоритм несравнительной сортировки, который используется для целых чисел или строк с представлениями фиксированной длины. Он сортирует элементы, обрабатывая отдельные цифры или символы от младшей значащей цифры до самой старшей.

Алгоритм:
1. Определить необходимое количество проходов (зависит от количества цифр или символов в максимальном элементе)
2. Создание 10 сегментов (0–9) для каждой позиции цифры (для чисел с основанием 10) или 26 сегментов (A–Z) для каждой позиции символа (для букв верхнего регистра).
3. Распределение элементов по сегментам, начиная с младшей значащей цифры.
4. Сортировка элементов в каждом сегменте, используя стабильный алгоритм сортировки
5. Формирование частично отсортированного массива.
6. Повторение процесса до тех пор пока не получится отсортированный массив.

Сложность:
В лучшем случаи: O(n)
В худшем: O(n*k)

BY Алгоритмы и структуры данных