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

Коротко

Ещё одна сортировка без единого сравнения элементов между собой. Работает быстрее O(n log n), но только для чисел или строк фиксированной длины.

Идея: сортируем по одной цифре за раз

Вместо того чтобы сравнивать числа целиком, разберём их по разрядам и отсортируем последовательно — сначала по единицам, потом по десяткам, потом по сотням.

Ключевая неочевидность: начинать надо с младшего разряда, а не со старшего. Это называется LSD-версией (least significant digit).

Разберём на массиве [170, 45, 75, 90, 802, 24, 2, 66].

Проход 1 — по единицам:

170, 90, 802, 2, 24, 45, 75, 66
 ↑    ↑   ↑   ↑   ↑   ↑   ↑   ↑
 0    0   2   2   4   5   5   6

Проход 2 — по десяткам:

802, 2, 24, 45, 66, 170, 75, 90
 0   0   2   4   6   7    7   9

Проход 3 — по сотням:

2, 24, 45, 66, 75, 90, 170, 802
0   0   0   0   0   0   1    8

Массив отсортирован. Три прохода вместо log₂(8) = 3 уровней рекурсии — но каждый проход линейный.

Почему это работает

Секрет в устойчивости каждого прохода. Когда мы сортируем по десяткам, числа с одинаковой цифрой десятков сохраняют порядок, полученный на предыдущем шаге, — то есть порядок по единицам.

Посмотрите на шаг 2: числа 170 и 75 обе имеют 7 в десятках. Между собой они остались в том порядке, в котором пришли после сортировки по единицам (170 с нулём, потом 75 с пятёркой). Так информация о младших разрядах не теряется, а накапливается.

Если убрать устойчивость, алгоритм сломается полностью. Именно поэтому внутри используют сортировку подсчётом в её устойчивом варианте, а не, скажем, быструю сортировку.

Код на Python

def counting_sort_by_digit(arr: list[int], exp: int) -> list[int]:
    """Устойчивая сортировка подсчётом по разряду exp (1, 10, 100, ...)."""
    n = len(arr)
    output = [0] * n
    counts = [0] * 10  # десятичные цифры

    for num in arr:
        digit = (num // exp) % 10
        counts[digit] += 1

    # префиксные суммы: позиция, куда класть каждую цифру
    for i in range(1, 10):
        counts[i] += counts[i - 1]

    # справа налево — это обеспечивает устойчивость
    for num in reversed(arr):
        digit = (num // exp) % 10
        counts[digit] -= 1
        output[counts[digit]] = num

    return output


def radix_sort(arr: list[int]) -> list[int]:
    if not arr:
        return arr

    # алгоритм работает с неотрицательными числами
    if min(arr) < 0:
        raise ValueError('нужна отдельная обработка отрицательных чисел')

    exp = 1
    max_value = max(arr)

    # проходим по разрядам, пока они есть в максимальном числе
    while max_value // exp > 0:
        arr = counting_sort_by_digit(arr, exp)
        exp *= 10

    return arr


print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]

Извлечение разряда — (num // exp) % 10. Целочисленное деление отбрасывает младшие разряды, остаток от деления на 10 берёт нужную цифру.

Что делать с отрицательными числами

Стандартный алгоритм с ними не работает. Есть два подхода.

Разделить и склеить. Отсортировать отрицательные и положительные по отдельности, у отрицательных взять модуль, отсортировать, развернуть и приписать в начало.

def radix_sort_signed(arr: list[int]) -> list[int]:
    negatives = [-x for x in arr if x < 0]
    positives = [x for x in arr if x >= 0]

    sorted_neg = radix_sort(negatives)[::-1]
    return [-x for x in sorted_neg] + radix_sort(positives)

Сдвинуть диапазон. Прибавить ко всем элементам модуль минимума, отсортировать, вычесть обратно. Проще в коде, но при большом разбросе может добавить лишний разряд.

Сложность: где выигрыш, а где нет

Формула O(d · (n + k)). Здесь d — количество разрядов в максимальном числе, k — основание системы счисления (10 в нашем коде).

Для 32-битных целых d не превышает 10 при основании 10. То есть сортировка миллиона чисел — это 10 линейных проходов. Быстрой сортировке понадобилось бы log₂(10⁶) ≈ 20 уровней рекурсии, но с гораздо более дешёвыми операциями внутри.

На практике поразрядная сортировка обгоняет быструю на больших массивах целых чисел, но проигрывает на маленьких — константа у неё заметно выше.

Оптимизация, которую применяют в реальных реализациях: работать не с десятичными цифрами, а с байтами (основание 256). Тогда для 32-битного числа нужно всего 4 прохода вместо 10, а извлечение разряда делается битовым сдвигом вместо деления:

digit = (num >> shift) & 0xFF   # shift = 0, 8, 16, 24

LSD и MSD

Разобранная версия — LSD, от младшего разряда к старшему. Есть и обратная, MSD (most significant digit): сортируем по старшему разряду, потом рекурсивно внутри каждой группы.

MSD удобна для строк разной длины — она похожа на сортировку слов в словаре. LSD проще и обычно быстрее для чисел фиксированной разрядности.

Когда применять

Хорошо подходит:

• большие массивы целых чисел;
• строки фиксированной длины — телефоны, артикулы, идентификаторы;
• даты в числовом формате;
• ситуации, где важна устойчивость.

Не подходит:

• вещественные числа в общем случае;
• произвольные объекты со сложным сравнением;
• маленькие массивы — накладные расходы съедят выигрыш;
• числа с огромным разбросом разрядности.

Частые ошибки

Использование неустойчивой сортировки внутри. Самая грубая. Алгоритм перестанет работать вовсе, и результат будет просто неверным.

Проход слева направо во внутренней сортировке. Ломает устойчивость с тем же результатом.

Цикл по фиксированному числу разрядов. Если жёстко прописать 10 проходов, алгоритм отработает, но потратит время впустую на массиве из однозначных чисел. Условие max_value // exp > 0 останавливает цикл ровно тогда, когда нужно.

Забытые отрицательные числа. Код молча выдаст неверный порядок, если не обработать их отдельно.

Что запомнить

• Сортируем по одному разряду за раз, начиная с младшего.
• Внутри обязательно устойчивая сортировка — иначе алгоритм не работает.
• O(d · (n + k)) — линейно по количеству элементов при фиксированной разрядности.
• Отрицательные числа требуют отдельной обработки.
• В реальных реализациях основание берут 256 и извлекают разряд битовыми операциями.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→