Алгоритмы и структуры данных

Сортировка Шелла

Это алгоритм сортировки, который является расширением алгоритма сортировки вставками. Сортировка Шелла сортирует элементы, удаленные друг от друга на расстояние D, а затем постепенно сокращает разрыв между ними.

Есть огромное количество методов выбора числа D:
1. Самый просто пример это D = n / 2, D2 = D/2 … Dn =1
2. Предложение Хиббарда: проверить на всем N ^i — 1<= N. 
3. Числа Седжвика и много много другого.

Основные шаги в сортировке:
1. Выбрать расстояние D
2. Сформировать подмассивы на основе данного массива и расстояния D.
3. Применяем сортировку вставками к каждому подмассиву
4. Собрать массив
Повторять эти шаги пока массив не будет отсортирован.

Сложность алгоритма:
В лучшем случаи: O(n)
В cреднем: O(n (logn)^2)
В худшем: O(n log^2n)

www.tgoop.com/the_algorithms/4561

8.3K viewsSep 29, 2023 at 09:01

Сортировка Шелла

Это алгоритм сортировки, который является расширением алгоритма сортировки вставками. Сортировка Шелла сортирует элементы, удаленные друг от друга на расстояние D, а затем постепенно сокращает разрыв между ними.

Есть огромное количество методов выбора числа D:
1. Самый просто пример это D = n / 2, D2 = D/2 … Dn =1
2. Предложение Хиббарда: проверить на всем N ^i — 1<= N. 
3. Числа Седжвика и много много другого.

Основные шаги в сортировке:
1. Выбрать расстояние D
2. Сформировать подмассивы на основе данного массива и расстояния D.
3. Применяем сортировку вставками к каждому подмассиву
4. Собрать массив
Повторять эти шаги пока массив не будет отсортирован.

Сложность алгоритма:
В лучшем случаи: O(n)
В cреднем: O(n (logn)^2)
В худшем: O(n log^2n)

BY Алгоритмы и структуры данных