Распределяющий подсчет

В этом алгоритме ключами могут быть целые числа или приводимые к целым в диапазоне от a до c.

Ki Э [a…c]

a ≤ Ki ≤ C

a = min{Ki} – O(n)

c = max{Ki} – O(n)

Для подсчета количества используется вспомогательный массив

a = min{k}= 2

c = max{k} = 5

count [a…c]

4 2 4 5 4 2

0 0 0 0 count

2 3 4 5

2 0 3 1 count[k[i]++]

2 3 4 5

I этап инициализация массива count 0 0 0 0

II этап подсчет одинаковых ключей Count[i]++

2 0 3 1

III этап – заметим, что значением самой правой ячейки count показывает, сколько ячеек необходимо зарезервивать в результирующем массиве под хранение значения K[i]. В данном случае одна ячейка отводится под хранение 5, три ячейки под значения 4, 0 ячеек – под тройку и две ячейки под значение двойки. При помощи цикла расположим элементы по зарезерванным позициям. Заметим, что тройки могли бы начать располагаться после всех двоек, т.е. после количества, указанной в count.. Четверки располагаются по двойки и тройки, т.е. с позиции count[2]+count[3], а прибавляя count [4] мы получаем самую правую позицию, которую может занять k[i] ключ.

IV этап – расположение элементов.

|c - a| - должно быть небольшое

2*O(N) + O(c-a) + O(N) + O(c-a-1) + O(N)= const O(N) + const O(c-a)