Цифровая сортировка — различия между версиями
Linn (обсуждение | вклад) |
Linn (обсуждение | вклад) |
||
| Строка 5: | Строка 5: | ||
Для чисел наиболее часто в качестве устойчивой сортировки применяют [[сортировка подсчетом|сортировку подсчетом]]. | Для чисел наиболее часто в качестве устойчивой сортировки применяют [[сортировка подсчетом|сортировку подсчетом]]. | ||
==Сложность== | ==Сложность== | ||
| − | Пусть <tex> | + | Пусть <tex>k</tex> - количество разрядов, n - количество входных данных, <tex>T(n)</tex> - сложность устойчивой сортировки, тогда сложность цифровой сортировки - <tex>О(k*T(n))</tex>. |
При использовании сортировки подсчетом получаем линейную зависимость. | При использовании сортировки подсчетом получаем линейную зависимость. | ||
==Псевдокод== | ==Псевдокод== | ||
Версия 19:01, 19 июня 2011
Цифровая сортировка — алгоритм сортировки за линейное время.
Содержание
Алгоритм
При цифровой сортировке данные разбиваются на "разряды", после этого данные сортируются какой-либо устойчивой сортировкой по каждому разряду, в порядке от младшего разряда к старшему. Для чисел наиболее часто в качестве устойчивой сортировки применяют сортировку подсчетом.
Сложность
Пусть - количество разрядов, n - количество входных данных, - сложность устойчивой сортировки, тогда сложность цифровой сортировки - . При использовании сортировки подсчетом получаем линейную зависимость.
Псевдокод
Radix_sort
for i = 1 to m
do устойчивая сортировка массива по i-ому разряду
Литература
- Дональд Кнут Искусство программирования, том 3. Сортировка и поиск
- Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ
Ссылки
- Визуализатор1 — Java-аплет.
- Визуализатор2 — Java-аплет.
