Цифровая сортировка — различия между версиями
(→Псевдокод) |
|||
| Строка 11: | Строка 11: | ||
for i = 1 to m | for i = 1 to m | ||
do устойчивая сортировка массива по i-ому разряду | do устойчивая сортировка массива по i-ому разряду | ||
| + | |||
| + | == Литература == | ||
| + | * Дональд Кнут Искусство программирования, том 3. Сортировка и поиск | ||
| + | * Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ | ||
| + | |||
| + | == Ссылки == | ||
| + | * [http://rain.ifmo.ru/cat/view.php/vis/sorts/linear-2005 Визуализатор1] — Java-аплет. | ||
| + | * [http://rain.ifmo.ru/cat/view.php/vis/sorts/linear-2001 Визуализатор2] — Java-аплет. | ||
Версия 18:14, 19 июня 2011
Цифровая сортировка — алгоритм сортировки за линейное время.
Содержание
Алгоритм
При цифровой сортировке данные разбиваются на "разряды", после этого данные сортируются какой-либо устойчивой сортировкой по каждому разряду, в порядке от младшего разряда к старшему. Для чисел наиболее часто в качестве устойчивой сортировки применяют сортировку подсчетом.
Сложность
Пусть - количество разрядов, n - количество входных данных, T(n) - сложность устойчивой сортировки, тогда сложность цифровой сортировки - . При использовании сортировки подсчетом получаем линейную зависимость.
Псевдокод
Radix_sort
for i = 1 to m
do устойчивая сортировка массива по i-ому разряду
Литература
- Дональд Кнут Искусство программирования, том 3. Сортировка и поиск
- Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ
Ссылки
- Визуализатор1 — Java-аплет.
- Визуализатор2 — Java-аплет.
