1)Сортировка выбором на C/C++

template<class T>

}

2)Сортировка пузырьком на C/C++

template<class T>
void bubbleSort(T a[], long size) {
long i, j;
T x;

for( i=0; i < size; i++) { // i - номер прохода
for( j = size-1; j > i; j-- ) { // внутренний цикл прохода
if ( a[j-1] > a[j] ) {
x=a[j-1]; a[j-1]=a[j]; a[j]=x;
}
}
}
}

3)Сортировка вставками на C/C++

template
void insertSort(T a[], long size) {
T x;
long i, j;

for ( i=0; i < size; i++) { // цикл проходов, i - номер прохода
x = a[i];
// поиск места элемента в готовой последовательности
for ( j=i-1; j>=0 && a[j] > x; j--)
a[j+1] = a[j]; // сдвигаем элемент направо, пока не дошли
// место найдено, вставить элемент
a[j+1] = x;
}
}

4)Сортировка Шелла на C/C++

int increment(long inc[], long size) {
int p1, p2, p3, s;

p1 = p2 = p3 = 1;
s = -1;
do {
if (++s % 2) {
inc[s] = 8*p1 - 6*p2 + 1;
} else {
inc[s] = 9*p1 - 9*p3 + 1;
p2 *= 2;
p3 *= 2;
}
p1 *= 2;
} while(3*inc[s] < size);

return s > 0 ? --s : 0;
}

template
void shellSort(T a[], long size) {
long inc, i, j, seq[40];
int s;

// вычисление последовательности приращений
s = increment(seq, size);
while (s >= 0) {
// сортировка вставками с инкрементами inc[]
inc = seq[s--];
for (i = inc; i < size; i++) {
T temp = a[i];
for (j = i-inc; (j >= 0) && (a[j] > temp); j -= inc)
a[j+inc] = a[j];
a[j] = temp;
}
}
}

5) Пирамидальная сортировка на C/C++

template
void downHeap(T a[], long k, long n) {
// процедура просеивания следующего элемента
// До процедуры: a[k+1]...a[n] - пирамида
// После: a[k]...a[n] - пирамида
T new_elem;
long child;
new_elem = a[k];

while(k <= n/2) { // пока у a[k] есть дети
child = 2*k;
// выбираем большего сына
if( child < n && a[child] < a[child+1] )
child++;
if( new_elem >= a[child] ) break;
// иначе
a[k] = a[child]; // переносим сына наверх
k = child;
}
a[k] = new_elem;
}

template
void heapSort(T a[], long size) {
long i;
T temp;

// строим пирамиду
for(i=size/2-1; i >= 0; i--) downHeap(a, i, size-1);

// теперь a[0]...a[size-1] пирамида

for(i=size-1; i > 0; i--) {
// меняем первый с последним
temp=a[i]; a[i]=a[0]; a[0]=temp;
// восстанавливаем пирамидальность a[0]...a[i-1]
downHeap(a, 0, i-1);
}
}

6)Быстрая сортировка (сортировка Хоара) на C/C++

template<class T>
void quickSortR(T* a, long N) {
// На входе - массив a[], a[N] - его последний элемент.

long i = 0, j = N; // поставить указатели на исходные места
T temp, p;

p = a[ N>>1 ]; // центральный элемент

// процедура разделения
do {
while ( a[i] < p ) i++;
while ( a[j] > p ) j--;

if (i <= j) {
temp = a[i]; a[i] = a[j]; a[j] = temp;
i++; j--;
}
} while ( i<=j );

// рекурсивные вызовы, если есть, что сортировать
if ( j > 0 ) quickSortR(a, j);
if ( N > i ) quickSortR(a+i, N-i);
}

7)Поразрядная сортировка на C/C++

typedef struct slist_ {
long val;
struct slist_ *next;
} slist;

// функция сортировки возвращает указатель на начало отсортированного списка
slist *radix_list(slist *l, int t) {
// t - разрядность (максимальная длина числа)
int i, j, d, m=1;
slist *temp, *out, *head[10], *tail[10];
out=l;

for (j=1; j<=t; j++) {
for (i=0; i<=9; i++)
head[i] = (tail[i]=NULL);

while ( l != NULL ) {
d = ((int)(l->val/m))%(int)10;
temp = tail[d];
if ( head[d]==NULL ) head[d] = l;
else temp->next = l;
temp = tail[d] = l;
l = l->next;
temp->next = NULL;
}
for (i=0; i<=9; i++)
if ( head[i] != NULL ) break;
l = head[i];
temp = tail[i];
for (d=i+1; d<=9; d++) {
if ( head[d] != NULL) {
temp->next = head[d];
temp = tail[d];
}
}
m*=10;
}
return (out);
}