Сортировка подсчетом относится к семейству сортировок, которые выполняются за линейное время. Сортировка оперирует массивом, состоящим из элементов с целочисленными положительными значениями:
public CountingSort(int array[]){
arr = array;
}
public int[] sort(int k){
int C[] = new int[k + 1];
// инициализируем вспомогательный массив C нулями
for (int i = 0; i < C.length; i++){
C[i] = 0;
}
// подсчитываем частоту появления значения в входном массиве
for (int i = 0; i < arr.length; i++){
C[arr[i]] += 1;
}
for (int i = 1; i < C.length; i++){
C[i] = C[i - 1] + C[i];
}
// используем вспомогательный массив B, в котором будет хранится отсортированная последовательность
int B[] = new int[arr.length + 1];
for (int i = arr.length - 1; i >= 0; i--){
B[C[arr[i]]] = arr[i];
C[arr[i]] -= 1;
}
return B;
}
В алгоритме сортировки подсчетом, используются два вспомогательных массива: массив C, в ячейках которого хранится число элементов, не превышающие i, где i - значение одного из элементов в исходном массиве и массив B, в котором хранится отсортированная последовательность. Переменная k определяет размер вспомогательного массива C, зависит от максимального значения в сортируемом массиве.
В первом цикле инициализируем вспомогательный массив C нулями. Во втором цикле подсчитываем частоту появления значений элементов входного массива.:
Например, сортируемая последовательность: {1,8, 5, 2, 1, 2, 5}
После второго цикла массив C, будет выглядеть следующим образом: {0, 2, 0, 0, 2, 0, 0, 1}, где индекс является значением одного из элементов в сортируемой массиве. Т.е. значение 0 встречается 0 раз, значение 1 встречается 2 раза и т.д.
Третий цикл определяет позиции элементов в отсортированном массиве.:
В моем примере массив C после прохода цикла будет выглядеть след. образом: {0, 2, 0, 0, 4, 0, 0, 7}. Например, количество элементов, не превышающих значения 1 равно 2, или количество элементов, не превышающих значения 7 равно 7.
В четвертом цикле элемент из сортируемого массива arr, устанавливается в позицию отсортированного массива B. Позиции хранятся в вспомогательном массиве C. Если количество элементов, не превышающих значения 1 равно 2, то элемент устанавливается в 2-ую позицию массива B.
Первый цикл выполняется за время Thetta(k), второй за время Thetta(n), третий за время Thetta(k), четвертый за время Thetta(n). Таким образом, полное время выполнения алгоритма равно Thetta(n + k). На практике сортировка подсчетом применяется, когда k = O(n), а в этом случае время работы алгоритма равно Thetta(n).
Важное свойство алгоритма сортировки подсчетом заключается в том, что он устойчив: элементы с одним и тем же входным значением находятся в выходном массиве, в том же порядке, что и во входном. Обычно свойство устойчивости важно только в ситуации, когда вместе сортируемые элементы имеют сопутствующие данные.
Сортировка подсчетом используется, когда входные данные положительны, целочисленны и их значения изменяются в небольшом интервале.