Сортировка подсчетом

Суть метода заключается в том, что на каждом шаге подсчитывается, в какую позицию результирующего массива B надо записать очередной элемент исходного массива A. Если некоторый элемент A[i] помещается в результирующий массив в позицию k+1, то слева от B[k+1] должны стоять элементы меньшие или равные B[k+1]. Значит, число k складывается из количества элементов меньших A[i] и, возможно, некоторого числа элементов, равных A[i]. Условимся, что из равных будут учитываться только те элементы, которые в исходном массиве стоят левее A[i].

procedure NumerSort(n: integer;

var A: array [1..n] of integer);

{Процедура сортировки подсчетом}

var

i, j, k: integer;

B: array[1..n] of integer;

begin

for i := 1 to n do begin

{Вычисляем положение элемента в результирующем массиве}

k := 1;

for j := 1 to n do

if (A[j] < A[i]) or

((A[j] = A[i]) and (j < i)) then k := k+1;

{Включаем очередной элемент в результирующий массив}

B[k] := A[i];

end;

for i := 1 to n do A[i] := B[i];

end;

Рисунок 40. Сортировка подсчетом

Легко видеть, что этот алгоритм всегда имеет временную сложность, пропорциональную O(n²) (два вложенных цикла, зависящих от n линейно и не зависящих от порядка элементов) и пространственную сложность, пропорциональную O(n) (результирующий массив). Также следует отметить, что данный алгоритм сохраняет порядок элементов с одинаковыми значениями.