Radix-сортировка (поразрядная сортировка) — алгоритм сортировки, который обрабатывает каждую цифру или букву по отдельности. 13

Процесс работы: 3

1. Начать с наименьшей части. 3 Для чисел это означает начать с правой цифры, для слов — с последней буквы. 3
2. Отсортировать по этой части. 3 Элементы группируются по значению цифры или буквы. 3 Все элементы с одинаковой последней цифрой или буквой объединяются. 3
3. Перейти к следующей части. 3 Затем список сортируется снова, но на этот раз рассматривается следующая цифра или буква слева. 3
4. Повторять до завершения. 3 Этот процесс продолжается до тех пор, пока не будет отсортирована по всем цифрам или буквам. 3

Существует два варианта Radix-сортировки в зависимости от направления, в котором выполняется сортировка: 3

1. LSD (Least Significant Digit). 13 Сортировка начинается с наименьшей значащей цифры (правой) и движется к наибольшей (левой). 13
2. MSD (Most Significant Digit). 13 Сортировка начинается с наибольшей значащей цифры (левой) и движется к наименьшей (правой). 13

Radix-сортировка исходно предназначена для сортировки целых чисел, записанных цифрами, но так как в памяти компьютеров любая информация записывается целыми числами, алгоритм пригоден для сортировки любых объектов, запись которых можно поделить на «разряды», содержащие сравнимые значения, например, строки. 1