Изменения
Нет описания правки
Сам алгоритм работает следующим образом. Создаются <tex>range</tex> вспомогательных списков - корзин, т.е. на каждое возможное значение разряда элемента по корзине.
'''Первый этаппроход:''' распределение по корзинам и на первом проходе элементы исходной последовательности помещаются в эти корзины по их младшему разряду, т.е. по самому правому символу. Какой этот самый младший разряд у элемента, в такую корзину этот элемент и помещается.
Например, пусть имеем исходную последовательность из <tex>list0: {11, 24, 9, 59, 21, 98, 76, 8}</tex>, для которой определяем <tex>width</tex>= 2, <tex>range</tex> = 10, поэтому будет 10 корзин: <tex>list0, list1..., list9</tex>. Тогда на первом проходе корзины №0, 2, 3, 5, 7 окажутся пусты, а остальные распределят элементы след. образом:
<tex>list1: 11, 21</tex>
<tex>list6: 76</tex>
<tex>list8: 98, 8</tex>
<tex>list9: 9, 59</tex>
'''Второй этап''' - сборка: просто последовательно соединяем один за другим все корзины и располагаем элементы уже в этой последовательности:
<tex>9, 8 (list0), 11, 21 (list1), 24(list4), 76(list6), 98, 8(list8), 9, 59(list9)</tex>
Это был один проход алгоритма, соответствующий крайнему правому разряду ключа.
На следующем проходе, элементы из уже обновленной последовательности распределяются по корзинам в соответствии с их вторым(т.е. предпоследним) разрядом и т.д по самого старшего, максимального, <tex>width</tex>-го разряда ключа.
'''Второй проход:'''
На втором проходе корзины №3, 4, 6, 8 окажутся пусты, а остальные распределят элементы след. образом:
<tex>list0: 8, 9</tex>
<tex>list1: 11</tex>
<tex>list2: 21, 24</tex>
<tex>list5: 59</tex>
<tex>list7: 76</tex>
<tex>list9: 98</tex>
Собираем и получаем отсортированную по возрастанию последовательность: <tex>8, 9(list0), 11(list1), 21(list2), 59(list5), 76(list7), 98(list 9)</tex>
== Время работы ==
