Очевидно, как следует из названия, мы собираемся подсчитать материал и получить результат. Временная сложность сортировки подсчетом лучше, чем у других методов сортировки, таких как сортировка слиянием и быстрая сортировка. Сортировка подсчетом не является алгоритмом сортировки на месте. Требует дополнительного вспомогательного пространства.

Сортировка подсчетом — это метод сортировки, основанный на ключах в определенном диапазоне. Он работает, подсчитывая количество объектов, имеющих различные значения ключа. Это похоже на хеширование, но не то же самое. Затем выполните некоторые математические операции, чтобы вычислить положение каждого объекта в выходной последовательности.

Давайте рассмотрим пример.
Входные данные: 1, 3, 2, 4, 1, 6, 4, 3, 2, 4

Диапазон элементов — от 1 до 6. Поэтому мы берем массив count размером 7, чтобы включить в него индекс 6. Назначение массива count — хранить количество каждого отдельного элемента. Массив count выглядит примерно так:

1) Диапазон элементов — от 1 до 6. Итак, мы берем массив count размером 7, чтобы включить индекс 6. Назначение массива count — хранить количество каждого отдельного элемента. Массив count выглядит примерно так:

1) The range of elements is 1 to 6. So we take a count array of size         7 to include index 6. The purpose of the count array is to store the      count of each distinct element. The count array looks something like   this:
  Index:     0  1  2  3  4  5  6 
  Count:     0  2  2  2  3  0  1
2) Modify the count array such that each element at each index 
  stores the sum of previous counts. 
  Index:     0  1  2  3  4  5  
  Count:     0  2  4  6  9  10
The modified count array indicates the position of each object in 
the output sequence.
3) Output each object from the input sequence followed by 
  decreasing its count by 1.
  Process the input data: 1, 3, 2, 4, 1, 6, 4, 3, 2, 4. 
  Position of 4 is 3. Put data 4 at index 8 in output. Decrease    count by 1 to place next data 4 at an index 1 smaller than this index.

Если вы со мной, возможно, вы уже поняли, что этот алгоритм не будет работать для отрицательных элементов, поскольку у нас нет отрицательных индексов в массиве. Но есть решение. Таким образом, решение состоит в том, чтобы найти минимальный элемент и сохранить его количество с нулевым индексом.

Полная реализация сортировки подсчета (на Java):

Временная сложность: O(n+k), где n — размер входных данных, а k — диапазон входных данных.

Вспомогательная сложность: O(n+k)

Замечания:
1. Сортировка подсчетом эффективна, если диапазон входных данных незначительно превышает количество сортируемых объектов. Рассмотрим ситуацию, когда входная последовательность находится в диапазоне от 1 до 10 КБ, а данные — 10, 5, 10 КБ, 5 КБ.
2. Это не сортировка на основе сравнения. Сложность времени выполнения составляет O (n) с пространством, пропорциональным диапазону данных.
3. Он часто используется как подпрограмма для другого алгоритма сортировки, такого как сортировка по основанию.
4. Сортировка подсчетом использует частичное хеширование для подсчета появления объекта данных в O(1).
5. Сортировку подсчетом можно расширить, чтобы она работала и с отрицательными входными данными.