Изменения

В этом алгоритме сортировки числа сортируются по разрядам. Существует два варианта least significant digit Least Significant Digit (LSD) и most significant digit Most Significant Digit (MSD). При LSD сортировке, сначала сортируются младшие разряды, затем старшие. При MSD сортировке все наоборот. При  == Алгоритм LSD сортировке получается следующий порядок==Перед сортировкой необходимо определить 2 величины: короткие ключи идут раньше длинных # <tex>width</tex> {{---}} максимальное количество разрядов в сортируемых величинах.# <tex>range</tex> {{---}} количество возможных значений одного разряда ключа (сортируемого элемента), то есть мощность используемого алфавита. Создаются <tex>range</tex> вспомогательных списков-корзин, ключи одного размера сортируются т.е. на каждое возможное значение разряда элемента по корзине. '''Первый проход:''' ''Первый этап'' {{---}} распределение по корзинам и на первом проходе элементы исходной последовательности помещаются в эти корзины по их младшему разряду, т.е. по алфавитусамому правому символу. Какой этот самый младший разряд у элемента, это совпадает с нормальным представлением чисел: 1в такую корзину этот элемент и помещается. Например, пусть имеем исходную последовательность из <tex>{11, 224, 39, 459, 521, 698, 776, 8}</tex>, 9для которой определяем <tex>width</tex> = 2, <tex>range</tex> = 10, поэтому будет 10корзин: <tex>list0, list1... При MSD сортировке получается алфавитный порядок, который подходит для сортировки строкlist9</tex>. Например "bТогда на первом проходе корзины №0, 2, c3, d5, e7 окажутся пусты, fа остальные распределят элементы след. образом: <tex>list1: 11, g21</tex> <tex>list4: 24</tex> <tex>list6: 76</tex> <tex>list8: 98, h8</tex> <tex>list9: 9, i59</tex> ''Второй этап'' {{---}} сборка: просто последовательно соединяем один за другим все корзины и располагаем элементы уже в этой последовательности: <tex>11, j21 (list1), ba" отсортируется как "b24(list4), ba76(list6), c98, d8(list8), e9, f59(list9)</tex> Это был один проход алгоритма, gсоответствующий крайнему правому разряду ключа.На следующем проходе, hэлементы из уже обновленной последовательности распределяются по корзинам в соответствии с их вторым(т.е. предпоследним) разрядом и т.д по самого старшего, iмаксимального, j"<tex>width</tex>-го разряда ключа. Если MSD применить к числам разной длины '''Второй проход:''' ''Первый этап'' {{---}} корзины №3, 4, 6, 8 окажутся пусты, то получим последовательность 1а остальные распределят элементы след. образом: <tex>list0: 8, 109</tex> <tex>list1: 11</tex> <tex>list2: 21, 224</tex> <tex>list5: 59</tex> <tex>list7: 76</tex> <tex>list9: 98</tex> ''Второй этап'' {{---}} собираем и получаем отсортированную по возрастанию последовательность: <tex>8, 39(list0), 411(list1), 521, 624(list2), 759(list5), 876(list7), 98(list 9.)</tex>

Алгоритм цифровой сортировки работает за линейное время- <tex>O(k(n + |A|))</tex>, где <tex>|A|</tex> {{---}} мощность алфавита(<tex>range</tex>), <tex>k</tex> {{---}} максимальная длина строки(<tex>width</tex>), <tex>n</tex> {{---}} количество сортируемых строк. == Применение ==Алгоритм цифровой сортировки позволяет строить суффиксный массив за <tex>O(n^2)</tex>, где <tex>n</tex> {{---}} длина строки. == Источник ==Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 5-8459-0082-4