Сортировка подсчётом
Ни одного сравнения: считаем вхождения значений и раскладываем по счётчикам за O(n + k).
1function countingSort(arr: number[], max: number): number[] {2 const counts = new Array(max + 1).fill(0)3 for (const v of arr) counts[v]++4 5 for (let v = 1; v <= max; v++) {6 counts[v] += counts[v - 1]7 }8 9 const out = new Array(arr.length)10 for (let i = arr.length - 1; i >= 0; i--) {11 const v = arr[i]12 out[--counts[v]] = v13 }14 return out15}Проблема
Значения — целые в узком диапазоне 0..k. Сравнивать бессмысленно: про каждое значение и так известно, где оно должно стоять — надо только посчитать, сколько таких.
Что вы видите
Три ряда: вход, счётчики counts, выход. Фаза 1 — счётчики растут по мере чтения. Фаза 2 — счётчики превращаются в границы блоков. Фаза 3 — элементы справа налево раскладываются по своим местам.
Как это работает
После префикс-суммирования counts[v] показывает, сколько значений ≤ v — то есть позицию блока значения v. Раскладка справа налево сохраняет устойчивость. Сложность O(n + k): быстрее любой сравнительной сортировки, если k = O(n).
Пошаговый разбор
- 01
Подсчёт
counts[v]++ для каждого элемента.
- 02
Границы
Префикс по счётчикам: где блок каждого значения.
- 03
Раскладка
Справа налево: out[−−counts[v]] = v.
- 04
Готово
Без единого сравнения элементов.
Complexity и ограничения
Только целые (или отображаемые в индексы) из диапазона 0..k. Память O(n + k). Устойчива.
Edge cases
- Большой k
Память взрывается — переходить к поразрядной.
- Все одинаковые
Один блок, ноль сравнений.
- Отрицательные
Сдвигом диапазона приводятся к 0..k.
Где встречается в реальности
Поразрядная сортировка
Radix sort — counting sort по разрядам.
Гистограммы
Построение распределения — это и есть фаза подсчёта.
Возрастные группы
Узкие дискретные диапазоны идеальны для подсчёта.
Связанные алгоритмы
«Сортировка без сравнений: просто посчитай»
Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.
Shorts 9:16
Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.