algorithm
Radix Sort

Основная информация о Radix

Radix Sort - это алгоритм, основанный на сравнении нижних границ. Это не сравнительный целочисленный алгоритм сортировки, который сортирует данные с помощью целых ключей, группируя ключи по отдельным цифрам, которые имеют значительную позицию и значение. Radix sort - это линейный алгоритм сортировки по времени, который сортирует по времени O (n + k), когда элементы находятся в диапазоне от 1 до k. Идея Radix Sort состоит в том, чтобы выполнять сортировку по цифрам, начиная с наименьшей значащей цифры и заканчивая самой значительной цифрой. Сортировка Radix использует сортировку подсчета в качестве подпрограммы для сортировки. Сорт Radix - это обобщение сортировки ковша.

Псевдокод для Bucket Сортировка:

1. Создайте массив из элементов [0..n-1].
2. Call Bucket Сортировать по меньшей мере до самой значимой цифры каждого элемента в качестве ключа.
3. Верните отсортированный массив.

Пример сортировки Radix:

Вспомогательный объем: O(n)
Сложность времени: O(n)