Этот простой метод основан на том, что j-й ключ в сортированной последовательности превышает ровно j-1 ключ. В первой фазе алгоритм подсчитывает для каждого ключа число ключей, которые меньше его. Значение счетчика для ключа и есть тот номер позиции в сортированной таблице, который он должен занять.
void CountSort(int n, int t[]){
// t – сортируемый массив целых чисел длиной n
int i,j;
int *c=new int[n]; // массив счетчиков
// обнулим счетчики
for(i=0; i<n; i++) c[i]=0;
// фаза подсчета
for(i=0; i<n; i+){
for(j=0; j<i; j++){
if(t[i]>t[j]){
c[i]++;
} else {
c[j]++;
}
}
}
// фаза расстановки
for(i=0; i<n; i++){
while(i!=c[i]){ // до тех пор, пока t[i] не займет
// окончательного положения
swap(t[i],t[c[i]]); // обмен местами эл-тов таблицы
swap(c[i],c[c[i]]); // обмен местами счетчиков
}
}
}
Ключ ti в исходной последовательности сравнивается с iпредшествующими ключами и, следовательно, общее число сравнений равно
то есть пропорционально N2.
