radix sort
поразрядная сортировка, цифровая сортировка # тип алгоритма (метода) сортировки массивов (списков), преимущественно числовых, без применения операций сравнения (non-comparative sorting algorithm). Элементы массива, имеющие более чем один значащий разряд (significant digit), распределяются по блокам (bucket) согласно их основаниям системы счисления (radix), и такое распределение-сортировка повторяется для каждого из разрядов, пока не обработаются все разряды. По этой причине поразрядная сортировка называется также блочной сортировкой (bucket sort) и цифровой сортировкой (digital sort). Алгоритм поразрядной сортировки можно использовать для упорядочения данных, которые позволяют это сделать лексикографически (lexicographically) – будь то целые числа, слова, игральные карты, сообщения электронной почты и др. Различают два варианта реализации поразрядной сортировки, на основе LSD (least significant digit) и MSD (most significant digit), младших и старших разрядов, соответственно. Оба варианта имеют асимптотику O(n)
Связные термины
asymptotics, big-O notation, sort
