Radix Sort Средний

Radix Sort

Урок 14 из 14 в курсе Алгоритмы. Старт.

Содержание курса (14/14)
1 Bubble Sort 2 Insertion Sort 3 Selection Sort 4 Merge Sort 5 Quick Sort 6 Heap Sort 7 Shell Sort 8 Counting Sort 9 Cocktail Sort 10 Comb Sort 11 Gnome Sort 12 Odd-Even Sort 13 Pancake Sort
14 Radix Sort

Interactive

Radix Sort Visualizer

Введите числа и управляйте пошаговым выполнением алгоритма.

sorting

История шагов

Radix Sort

Radix Sort — поразрядная сортировка целых чисел: сортирует по разрядам от младшего к старшему.

Основная идея

На каждом шаге используем стабильную сортировку (counting sort) по очередному разряду. После прохода по всем разрядам массив отсортирован.

Пошаговый пример

Исходный массив:

[170, 45, 75, 90, 802, 24, 2, 66]
  1. Сортируем по единицам → [170, 90, 802, 2, 24, 45, 75, 66]
  2. Сортируем по десяткам → [802, 2, 24, 45, 66, 170, 75, 90]
  3. Сортируем по сотням → [2, 24, 45, 66, 75, 90, 170, 802]

Псевдокод

exp = 1
max_value = max(arr)
while max_value / exp > 0:
    counting_sort_by_digit(arr, exp)
    exp *= 10

Оптимизация: Работает за линейное время, если число разрядов фиксировано.

Сложность

Время O(d · (n + k)), где d — число разрядов, k — основание.
Память O(n + k).

Когда используется

  • Большие массивы целых чисел
  • Сортировка строк фиксированной длины
  • Высокопроизводительные системы

Ключевые свойства

  • Стабильный
  • Не сравнительный
  • Линейный по числу элементов
Все уроки курса

Комментарии к уроку

Войдите, чтобы оставить комментарий.

Пока нет комментариев — будьте первым.