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