Radix Sort (Поразрядная сортировка)

Краткое описание

Сортирует числа поразрядно — цифра за цифрой, от младшего разряда к старшему (LSD — Least Significant Digit). На каждом разряде применяется стабильная сортировка (обычно Counting Sort). Не сравнивает числа между собой напрямую. Работает за O(d·(n+b)), где d — количество разрядов, b — основание системы счисления.

Когда использовать

• Целые числа (или строки фиксированной длины, IPv4-адреса) с ограниченным числом разрядов d
• Когда d мало относительно n — тогда быстрее O(n log n)
• Нужна стабильная сортировка больших наборов целочисленных ключей

Когда не стоит использовать:

• Числа с большим количеством разрядов (d велико) — теряется преимущество перед O(n log n)
• Дробные числа произвольной точности, сложные объекты без разрядного ключа
• Когда критична память — требует O(n + b) дополнительного пространства

---

С объяснением логики работы

/**
 * Поразрядная сортировка (LSD Radix Sort) для неотрицательных целых.
 * Принцип: стабильно сортируем по каждому разряду, начиная с единиц.
 */
function radixSort(arr) {
    if (arr.length === 0) return arr;
 
    const max = Math.max(...arr);
 
    // Проходим по разрядам: exp = 1 (единицы), 10 (десятки), 100 (сотни)...
    for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
        arr = countingSortByDigit(arr, exp);
    }
 
    return arr;
}
 
/**
 * Стабильная сортировка по одному разряду (по цифре на позиции exp).
 */
function countingSortByDigit(arr, exp) {
    const output = new Array(arr.length);
    const count = new Array(10).fill(0); // цифры 0..9
 
    // 1. Считаем количество каждой цифры на текущем разряде
    for (const num of arr) {
        const digit = Math.floor(num / exp) % 10;
        count[digit]++;
    }
 
    // 2. Префиксные суммы -> позиции
    for (let i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
 
    // 3. Строим результат с конца (стабильность)
    for (let i = arr.length - 1; i >= 0; i--) {
        const digit = Math.floor(arr[i] / exp) % 10;
        count[digit]--;
        output[count[digit]] = arr[i];
    }
 
    return output;
}
 
// Пример использования
console.log(radixSort([170, 45, 75, 90, 2, 802, 24, 66]));
// [2, 24, 45, 66, 75, 90, 170, 802]

---

С анализом сложностей

/**
 * Radix Sort с анализом сложности
 *
 * ВРЕМЕННАЯ СЛОЖНОСТЬ: O(d · (n + b))
 * - d — количество разрядов в максимальном числе
 * - n — количество элементов
 * - b — основание (здесь 10, т.е. цифры 0..9)
 * - На каждый из d разрядов делаем Counting Sort за O(n + b)
 * - При фиксированном небольшом d это фактически O(n) — быстрее сравнений O(n log n)
 *
 * ПРОСТРАНСТВЕННАЯ СЛОЖНОСТЬ: O(n + b)
 * - O(n) на output + O(b) на счётчики
 *
 * ОСОБЕННОСТИ:
 * - Стабильная (опирается на стабильность Counting Sort по разряду)
 * - НЕ in-place
 * - Не основана на сравнениях
 * - Базовая версия работает с неотрицательными целыми; для отрицательных нужна доработка
 *   (например, сместить диапазон или сортировать знак отдельно)
 */

См. также

• counting-sort — используется как стабильная сортировка по разряду
• O(n) — линейная сложность