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


Добавил:DMT
Дата создания:23 апреля 2008, 21:55
Дата обновления:23 апреля 2008, 22:04
Просмотров:10510 последний вчера, 5:35
Комментариев: 0

Полагаем, что элемент массива состоит из структуры, включающей ключ записи. Для каждого ключа вычисляется количество ключей, которые больше него. Это количество будет номером записи, содержащей данный ключ.

Пусть массив ключей состоит из целых чисел Определим таблицу

count [1], count [2], …, count [ n ],

для подсчета количества ключей, меньших данного.

После завершения подсчета величина count [ j +1] будет равна номеру записи в отсортированном массиве, имеющей ключ k j . Алгоритм будет состоять из операций:

for ( i =1; i <= n ; i ++) count [ i ]=0;

for (i=n; i>=2;i--)

for(j=i-1; j>=1; j--)

if (k[i]<k[j]) count[j]++;

else count [ i ]++;

Сначала вычисляется номер последнего элемента, и попутно увеличиваются счетчики для элементов, которые меньше него. Алгоритм будет работать и в том случае, когда существуют одинаковые элементы.

Пример. Пусть ключи равны

.

Тогда массив счетчиков претерпевает следующие изменения:

0 0 0 0 0 0 0

i =7: 1 0 0 0 0 1 4

i =6: 0 0 0 0 0 6

i =5: 2 1 1 1 0

i =4: 3 1 1 3

i =3: 4 1 2

i =2: 5 1

Следовательно, ключи получат порядковые номера 6, 2, 3, 4, 1, 7, 5.

Распределяющий подсчет. Сортировка методом подсчета применяется в том случае, когда имеется много равных ключей, и все они попадают в некоторый диапазон u <= k [ j ]<= v , где значение v - u невелико. Каждый ключ k [ j ] содержится в записи R [ j ] . Алгоритм состоит из двух просмотров. При первом просмотре для каждого из значений u , u +1,…, v вычисляется количество ключей, равных этому значению. При втором просмотре вычисляются позиции записей, содержащих эти ключи.

Рассмотрим шаги алгоритма. Пусть u <= k [ j ]<= v для всех j таких, что 1<= j <= n . Определим вспомогательную таблицу count [ u ], count [ u +1], …, count [ v ].

•  Положим count[u] = count[u+1] = … = count[v] = 0 ;

•  Выполним цикл, соответствующий первому просмотру

for (j=1; j<=n; j++)

count[k[j]]++;

•  Для каждого i из интервала u   <= i  <= v найдем количество ключей, не больших i

for (i=u+1; i<=v; i++)

count[i]+=count[i-1];

•  К этому моменту count [ i ] равно числу ключей, не больших, чем i . В частности, count [ v ]= n . Для каждого j  =  n ,  n - 1,   …,   1 выводим запись R [ j ] , имеющую ключ k [ j ] , в запись S [ i ] и уменьшаем count [ k [ j ]] на 1:

 

for (j=n; j>=1; j--)

{ i=count[k[j]]; S[i]=R[j]; count[k[j]]=i-1;

}

up