Приведите пример пирамидальной сортировки (сортировки кучи) на C++.
Ответ
Сортировка "кучи" на C++.
#include
template
inline void swap( T & arg1, T & arg2)
{
T temp = arg1;
arg1 = arg2;
arg2 = temp;
};
template
void shiftup(T * a, int size, int indexToShift) {
int i = indexToShift;
while(i > 1) {
if(a[i] < a[i/2]) {
swap(a[i], a[i/2]);
i /= 2;
} else
break;
}
}
template
void shiftdown(T * a, int size, int indexToShift) {
int i = indexToShift;
int min;
while ( i < size) {
if ( i*2 <= size) {
if (i*2+1 <= size) {
min = a[i*2] < a[i*2+1] ? i*2 : i*2+1;
} else
min = i*2;
if (a[i] > a[min]) {
swap(a[i], a[min]);
i = min;
} else
break;
} else
break;
}
}
template
void heap_sort( T * a, int size) {
for (int i = 1; i < size; ++i)
shiftup(a, size, i);
for (int i = size-1; i > 1; i--) {
swap(a[1], a[i]);
shiftdown(a, i-1, 1);
}
}
Комментариев нет:
Отправить комментарий