Изменения
Нет описания правки
'''Цифровая сортировка''' — алгоритм сортировки за линейное время.
==Алгоритм==
При цифровой сортировке данные разбиваются на "разряды", после этого данные сортируются какой-либо устойчивой сортировкой по каждому разряду, в порядке от младшего разряда к старшему.
Для чисел наиболее часто в качестве устойчивой сортировки применяют [[сортировка подсчетом|сортировку подсчетом]].
==Сложность==
Пусть <tex>m</tex> - количество разрядов, n - количество входных данных, T(n) - сложность устойчивой сортировки, тогда сложность цифровой сортировки - <tex>О(m*T(n))</tex>.
При использовании сортировки подсчетом получаем линейную зависимость.
==Псевдокод==
Radix_sort
for i = 1 to m
do устойчивая сортировка массива по i-ому разряду
