007 Сортировка подсчётом Counting sort

Описание: Сортировка подсчётом (Counting Sort)
Сортировка подсчётом (Counting Sort) — это алгоритм сортировки, который использует количество элементов в диапазоне значений для упрощения процесса сортировки. Этот алгоритм эффективен, когда элементы массива имеют ограниченный диапазон значений.

Основная идея:
Определяем диапазон значений элементов.
Создаем массив счётчиков, чтобы подсчитать количество вхождений каждого значения.
Используем массив счётчиков для построения отсортированного массива.
Шаги алгоритма:
Поиск максимального значения: Найдите максимальное значение в массиве, чтобы определить диапазон значений.
Создание массива счётчиков: Создайте массив счётчиков (или частотный массив) длиной, равной диапазону значений, и инициализируйте его нулями.
Подсчёт вхождений: Пройдите по исходному массиву и увеличьте соответствующие элементы в массиве счётчиков.
Кумулятивное суммирование: Пройдите по массиву счётчиков, чтобы получить кумулятивные суммы, которые укажут позиции элементов в отсортированном массиве.
Создание отсортированного массива: Пройдите по исходному массиву и используйте массив счётчиков для вставки элементов в правильные позиции в новом массиве.