403
правки
Изменения
→Алгоритм
При цифровой сортировке данные разбиваются на "разряды", после чего они сортируются какой-либо устойчивой сортировкой по каждому разряду, в порядке от младшего разряда к старшему. Заметим, что лексикографический порядок сортировки разрядов должен совпадать с требуемым от самой цифровой сортировки. Например, если объекты сортируются по невозрастанию, то при сортировки по <tex> i </tex>-ому разряду объект с меньшим <tex> i </tex>-ым разрядом должен идти раньше, чем объект, у которого данный разряд больше. В этом нетрудно убедиться, если на вход алгоритму подать объекты, состоящие из одного разряда.
Примерами объектов, которые удобно разбивать на разряды и сортировать по ним, являются числа и строки.
*Так как строки представляют из себя массивы символов, то в качестве разряда можно брать отдельные символы, сравнение которых обычно происходит по соответствующим им кодам из таблицы кодировок. Для такого разбиения
*
Для чисел наиболее часто в качестве устойчивой сортировки применяют [[сортировка подсчетом|сортировку подсчетом]].
=== Корректность алгоритма ===
