Изменения
Нет описания правки
В этом алгоритме сортировки числа сортируются по разрядам. Существует два варианта least significant digit (LSD) и most significant digit (MSD). При LSD сортировке, сначала сортируются младшие разряды, затем старшие. При MSD сортировке все наоборот. При LSD сортировке получается следующий порядок: короткие ключи идут раньше длинных, ключи одного размера сортируются по алфавиту, это совпадает с нормальным представлением чисел: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. При MSD сортировке получается алфавитный порядок, который подходит для сортировки строк. Например "b, c, d, e, f, g, h, i, j, ba" отсортируется как "b, ba, c, d, e, f, g, h, i, j". Если MSD применить к числам разной длины, то получим последовательность 1, 10, 2, 3, 4, 5, 6, 7, 8, 9.
== Алгоритм LSD==
Теперь рассмотрим подробно, что же представляет собой этот алгоритм.
2. <tex>range</tex> - количество возможных значений одного разряда ключа(сортируемого элемента)т.е. мощность используемого алфавита.
Сам алгоритм работает следующим образом. Создаются <tex>range</tex> вспомогательных списков - корзин, т.е. на каждое возможное значение разряда элемента по корзине. 1)Первый этап распределение по корзинам и на первом проходе элементы исходной последовательности помещаются в эти корзины по их младшему разряду, т.е. по самому правому символу. Какой этот самый младший разряд у элемента, в такую корзину этот элемент и помещается.
Например, пусть имеем исходную последовательность из <tex>{11, 24, 9, 59, 21, 98, 76, 8}</tex>, для которой определяем <tex>width</tex> = 2), <tex>range</tex> = 10, поэтому будет 10 корзин: <tex>list0, list1..., list9</tex>. Тогда на первом проходе корзины №2, 3, 5, 7 окажутся пусты, а остальные распределят элементы след. образом: <tex>list0: 9, 8</tex> <tex>list1: 11, 21</tex> <tex>list4: 24</tex> <tex>list6: 76</tex> <tex>list8: 98</tex> <tex>list9: 59</tex> '''Второй этап ''' - сборка: просто последовательно соединяем один за другим все корзины и располагаем элементы уже в этой последовательности: <tex>9, 8 (<< это был список0list0), 11, 21 (список1list1), 24(список4list4), 76(список 6list6), 98(список 8list8), 59(список9list9)</tex>
Это был один проход алгоритма, соответствующий крайнему правому разряду ключа.
