Поразрядная сортировка

Идея

Сортируем числа по цифрам, начиная с младшей (LSD — least significant digit). Каждый проход — устойчивая сортировка по одной цифре: сортировка подсчётом всего с 10 возможными значениями. Поскольку каждый проход устойчив, порядок, установленный младшими цифрами, сохраняется среди чисел с одинаковой старшей цифрой. После прохода по старшей цифре массив отсортирован.

Отрицательные числа сортируются отдельно по модулю и ставятся в начало в обратном порядке.

Пример

Сортируем [170, 45, 75, 90, 802, 24, 2, 66]. Цифра текущего прохода выделена жирным; в последнем проходе для наглядности показаны ведущие нули.

Проход	Массив после прохода
вход	170, 45, 75, 90, 802, 24, 2, 66
единицы	170, 90, 802, 2, 24, 45, 75, 66
десятки	802, 02, 24, 45, 66, 170, 75, 90
сотни	002, 024, 045, 066, 075, 090, 170, 802

Посмотрите на 170 и 75 после прохода по десяткам: у обоих 7 десятков, и 170 остаётся перед 75, потому что стояло перед ним после прохода по единицам (0 < 5). Вот почему каждый проход обязан быть устойчивым.

Попробуйте сами

Тот же пример по шагам. Измените данные или нажмите «Старт».

Псевдокод

RADIX-SORT(A)                          // неотрицательные целые
  max = maximum of A
  place = 1
  while ⌊max / place⌋ > 0
    stable COUNTING-SORT of A by digit ⌊A[i] / place⌋ mod 10
    place = place × 10

Сложность

Лучший	Средний	Худший	Память	Устойчивая	На месте
O(d(n + b))	O(d(n + b))	O(d(n + b))	O(n + b)	да	нет

• d — число цифр наибольшего по модулю значения, b = 10 — основание. Для чисел с ограниченным числом цифр это линейное время по n.
• В отличие от сортировки подсчётом, память не зависит от диапазона значений: для [0, 1 000 000 000] нужно 10 проходов, а не миллиард счётчиков.
• Только целые числа (до Number.MAX_SAFE_INTEGER); всё остальное вызывает TypeError.

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

Много целых чисел с ограниченным числом цифр: идентификаторы, отметки времени, почтовые индексы. Также для строк одинаковой длины (сортировка по символам вместо цифр) и как идея сортировки по составным ключам из нескольких полей.

Использование

import { radixSort } from 'ts-ds';

const ids = [170, 45, 75, -90, 802, 24, 2, 66];
radixSort(ids); // [-90, 2, 24, 45, 66, 75, 170, 802]

Справочник API

Литература

• Табуляторы Г. Холлерита (1890-е) сортировали перфокарты именно так.
• Кормен, §8.3 «Поразрядная сортировка».
• Седжвик, Алгоритмы, §5.1 «Сортировка строк» (LSD и MSD).