Стр. 93 - Основы алгоритмов и структур данных

Содержание 91
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
207
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
207, 095, 646, 198, 809, 376, 917, 534, 310, 209, 181, 595, 799, 694, 334, 522, 139
Распределяем по правой цифре
095 646 198 809
376 917
534 310
209
181
595
799
694
334
522
139
207 095 646
198
809
376
917
534
310
209 181
595
799
694 334
522 139
310, 181, 522, 534, 694, 334, 095, 595, 646, 376, 207, 917, 198, 809, 209, 799, 139
Распределяем по средней цифре
207
095
646
198
809
376
917
534 310
209
181
595
799
694
334
522
139
207, 809, 209, 310, 917, 522, 534, 334, 139, 646, 376, 181, 694, 095, 595, 198, 799
Распределяем по левой цифре
095, 139, 181, 198, 207, 209, 310, 334, 376, 522, 534, 595, 646, 694, 799, 809, 917
Отсортированная таблица
Рис.72. Цифровая распределяющая сортировка
Заметим, что как к стопкам, так и к самой таблице обращаются по правилу:
“первым включается — первым исключается”, и поэтому лучшим способом их
представления являются очереди.
Алгоритм распределяющей сортировки:
Пусть необходимо упорядочить последовательность x1, x 2, …, xn , где
) ,..., , ( 1, 1 , , i pi pi i x x x x− = и m x
ji< ≤
, 0 .
Удобной структурой данных для такой последовательности является
массив размером np .