30 lines
1.2 KiB
C++
30 lines
1.2 KiB
C++
#include <iostream>
|
||
|
||
void shellSort(int arr[], int n)
|
||
{
|
||
// Сортировка Шелла
|
||
|
||
for (int gap = n/2; gap > 0; gap /= 2)
|
||
{
|
||
// Выполнение промежуточной сортировки вставками.
|
||
for (int i = gap; i < n; i += 1)
|
||
{
|
||
// Сохраняем элемент arr[i] во временной переменной temp,
|
||
// чтобы на этой позиции можно было оставить "отверстие".
|
||
int temp = arr[i];
|
||
|
||
// Передвигаем ранее отсортированные элементы выше,
|
||
// пока не будет найдена правильная позиция для a[i]
|
||
int j; // Объявляем j здесь, т.к. позже еще будет нужна
|
||
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
|
||
{
|
||
// Сдвигаем ранее отсортированные элементы.
|
||
// "Отверстие" позволяет это сделать.
|
||
arr[j] = arr[j - gap];
|
||
}
|
||
// Помещаем сохраненный элемент в его правильную позицию
|
||
arr[j] = temp;
|
||
}
|
||
}
|
||
}
|