// Сортировка вставками
упорядочивает подсписки A[0]...A[i], 1 <= i <= n-1. Для
// каждого i A[i]
вставляется в подходящую позицию A[j]
template <class T>
void InsertionSort(T A[], int n)
{
int i, j;
T temp;
// i определяет подсписок A[0]...A[i]
for (i=1; i<n; i++)
{
// индекс j пробегает вниз по списку от
A[i] в процессе
//
поиска правильной позиции вставляемого значения
j = i;
temp = A[i];
// обнаружить подходящую позицию для
вставки, сканируя подсписок,
// пока temp < A[j-1] или пока не
встретится начало списка
while (j > 0 && temp < A[j-1])
{
// сдвинуть элементы вправо, чтобы
освободить место для вставки
A[j] = A[j-1];
j--;
}
// точка вставки найдена; вставить temp
A[j] = temp;
}
}
|