Поразрядная (цифровая) сортировка / Radix sort Поразрядная сортировка - это алгоритм, который использует внутреннюю структуру сортируемых объектов.
Перед началом сортировки необходимо знать:
length - максимальное количество разрядов в сортируемых величинах (например, при сортировке слов необходимо знать максимальное количество букв в слове);
rang количество возможных значений одного разряда (при сортировке слов – количество букв в алфавите).
Распределяем исходные значения по этим массивам. Распределение осуществляется по значению младшего (крайнего) разряда.
Соединяем значения в той последовательности, в которой они находятся после распределения по спискам.
Повторяем шаги 1-2 для оставшихся разрядов.
Пример реализации на Kotlin: fun radixSort(original: IntArray): IntArray {
var old = original
for (shift in 31 downTo 0) {
val tmp = IntArray(old.size)
var j = 0
for (i in 0 until old.size) {
val move = (old[i] shl shift) >= 0
val toBeMoved = if (shift == 0) !move else move
if (toBeMoved)
tmp[j++] = old[i]
else {
old[i - j] = old[i]
}
}
for (i in j until tmp.size) tmp[i] = old[i - j]
old = tmp
}
return old
}
