Counting Sort
Counting Sort — не сравнительная сортировка, которая считает количество каждого значения.
Основная идея
Создаём массив частот, затем восстанавливаем отсортированный массив по счётчикам.
Пошаговый пример
Исходный массив:
[4, 2, 2, 8, 3, 3, 1]- Считаем частоты каждого числа
- Идём по массиву частот слева направо
- Записываем элементы в отсортированный массив
Псевдокод
counts = array(max_value - min_value + 1, 0)
for value in arr:
counts[value - min_value] += 1
index = 0
for number, count in counts:
repeat count times:
arr[index] = number + min_value
index += 1
Оптимизация: Эффективен, когда диапазон значений небольшой по сравнению с n.
Сложность
Время
O(n + k), где k — диапазон значений.
Память
O(k).
Когда используется
- Целочисленные ключи малого диапазона
- Предобработка для radix sort
- Подсчёт частот
Ключевые свойства
- Стабильность зависит от реализации
- Не сравнительный
- Очень быстрый в своей нише