---
title: "Сортировка без сравнений (подсчётом / поразрядная)"
url: https://algopath.pro/ru/patterns/non-comparison-sort
language: ru
summary: "Сортировки подсчётом и поразрядная не сравнивают значения между собой. Они читают сам ключ и обгоняют n log n на узком диапазоне."
updated: 2026-08-24
---

# Сортировка без сравнений (подсчётом / поразрядная)

Сортировки подсчётом и поразрядная не сравнивают значения между собой. Они читают сам ключ и обгоняют n log n на узком диапазоне.

## Сортировка без сравнений (подсчётом / поразрядная): как это работает?

Сортировке подсчётом нужны ключи из известного узкого диапазона. Заведите по счётчику на каждый возможный ключ.

Пройдите вход один раз и посчитайте каждый ключ. Теперь известно, сколько каких значений.

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

Пройдите вход второй раз и положите каждый элемент на его позицию. Ничего ни разу не сравнивалось.

Поразрядная сортировка применяет ту же идею по одному разряду. Она начинает с младшего разряда.

Каждый проход по разряду обязан быть устойчивым. Неустойчивый проход отменяет все предыдущие.

- `счётчики = [1, 1, 2]` Сортируем [2, 0, 2, 1]. Один ноль, одна единица, две двойки.
- `старты = [0, 1, 2]` Накопленные суммы дают каждому ключу его первую ячейку.
- `[0, _, _, _]` Ноль ложится в ячейку 0. Его старт сдвигается на единицу.
- `[0, 1, 2, _]` Единица занимает ячейку 1, первая двойка ячейку 2.
- `[0, 1, 2, 2]` Вторая двойка занимает ячейку 3. Ни одного сравнения не было.

## Сортировка без сравнений (подсчётом / поразрядная): когда применять?

- ключи — целые числа в небольшом известном диапазоне
- сортировка возрастов, оценок или ограниченных счётчиков
- нужна O(n), а сравнения — узкое место
- сортировка по разрядам или ключу фиксированной ширины
- n большое, но диапазон значений намного меньше n

## Сортировка без сравнений (подсчётом / поразрядная): с чем путают?

- **Быстрая сортировка (merge / quick)** - Никакая сортировка сравнением не быстрее n log n. Чтение ключа обходит этот предел целиком.
- **Хеш-множество / словарь** - Словарь тоже считает значения, но порядка не хранит. Сортировка подсчётом делает значение индексом.
- **Сортировка с пользовательским компаратором** - Компаратор описывает порядок между двумя элементами. Подсчёт вообще не смотрит на пары.
- **Элементарные сортировки (выбором, пузырьком, вставками)** - Те сравнивают соседей и стоят n в квадрате. Подсчёт линеен, если диапазон позволяет.

## Сортировка без сравнений (подсчётом / поразрядная): сложность по времени и памяти

n значений с ключами меньше k дают O(n + k). Поразрядная стоит O(d умножить на n) при d разрядах.

## Сортировка без сравнений (подсчётом / поразрядная): разбор примера

### K самых частых значений

Верните k значений, которые встречаются чаще всего.

Сортировка счётчиков стоит n log n, а полный порядок задаче не нужен.

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

Используйте сам счётчик как индекс в списке корзин. Читайте корзины с конца.

```javascript
function topKFrequent(nums, k) {
    const count = new Map();
    for (const x of nums) count.set(x, (count.get(x) ?? 0) + 1);

    // bucket i holds every value that appeared exactly i times
    const buckets = Array.from({ length: nums.length + 1 }, () => []);
    for (const [value, c] of count) buckets[c].push(value);

    const answer = [];
    for (let c = buckets.length - 1; c >= 1 && answer.length < k; c--) {
        for (const value of buckets[c]) {
            answer.push(value);
            if (answer.length === k) break;
        }
    }

    return answer;
}
```

## Сортировка без сравнений (подсчётом / поразрядная): частые ошибки

- **Берут её на огромном диапазоне ключей** Счётчик на каждый ключ означает память размером с диапазон. Значения до 1e9 делают это невозможным.
- **Неустойчивый проход внутри поразрядной** Каждый проход по разряду обязан сохранить прошлый порядок. Иначе ранняя работа пропадает.
- **Забывают про отрицательные значения** Индекс массива не бывает отрицательным. Сдвиньте все ключи на минимум.
- **Считают дробные числа или строки** Ключ обязан быть ограниченным целым. Всё остальное требует сортировки сравнением.

## Сортировка без сравнений (подсчётом / поразрядная): задачи с собеседований

- **Сортировка небольших целых** По счётчику на значение, потом чтение по порядку.
- **Сортировка цветов** Возможных ключей три, значит и счётчика три.
- **K самых частых элементов** Сам счётчик становится индексом корзины.
- **Индекс Хирша** Счётчики цитирований, ограниченные числом работ.
- **Максимальный разрыв** Поразрядная сортировка и делает линейное решение возможным.
- **Относительная сортировка массива** Подсчёт с порядком, заданным другим списком.
- **Сортировка символов по частоте** Корзины по числу вхождений буквы.

## JavaScript

```javascript
function countingSort(arr, maxVal) {
    const counts = new Array(maxVal + 1).fill(0);
    for (const x of arr) counts[x]++;
    const out = [];
    for (let v = 0; v <= maxVal; v++) {
        while (counts[v]-- > 0) out.push(v);
    }
    return out;
}
```

## Python

```python
def counting_sort(arr, max_val):
    counts = [0] * (max_val + 1)
    for x in arr:
        counts[x] += 1
    out = []
    for v, c in enumerate(counts):
        out.extend([v] * c)
    return out
```

## PHP

```php
function countingSort(array $arr, int $maxVal): array {
    $counts = array_fill(0, $maxVal + 1, 0);
    foreach ($arr as $x) $counts[$x]++;
    $out = [];
    for ($v = 0; $v <= $maxVal; $v++) {
        for ($c = $counts[$v]; $c > 0; $c--) $out[] = $v;
    }
    return $out;
}
```