Цифровая сортировка — различия между версиями
(→Псевдокод) |
|||
| Строка 7: | Строка 7: | ||
При использовании сортировки подсчетом получаем линейную зависимость. | При использовании сортировки подсчетом получаем линейную зависимость. | ||
==Псевдокод== | ==Псевдокод== | ||
| − | Radix_sort | + | |
| − | for i = 1 to m | + | Radix_sort |
| − | + | for i = 1 to m | |
| + | do устойчивая сортировка массива по i-ому разряду | ||
Версия 18:44, 15 июня 2011
Цифровая сортировка — алгоритм сортировки за линейное время.
Алгоритм
При цифровой сортировке данные разбиваются на "разряды", после этого данные сортируются какой-либо устойчивой сортировкой по каждому разряду, в порядке от младшего разряда к старшему. Для чисел наиболее часто в качестве устойчивой сортировки применяют сортировку подсчетом.
Сложность
Пусть - количество разрядов, n - количество входных данных, T(n) - сложность устойчивой сортировки, тогда сложность цифровой сортировки - . При использовании сортировки подсчетом получаем линейную зависимость.
Псевдокод
Radix_sort
for i = 1 to m
do устойчивая сортировка массива по i-ому разряду
