Оболочка сортировки и вставки сортировки

Question

У меня проблема. Я очень смущен алгоритмами сортировки и вставки сортировки. Как мы должны отличать друг от друга?

Answer 1

Вы можете реализовать сортировку вставки как серию сравнений и свопов смежных элементов. Это делает его «стабильным». Вместо этого Shell сортирует и свопит элементы, которые далеки друг от друга. Это делает его быстрее.

Я полагаю, что ваше замешательство проистекает из того факта, что сортировка оболочки может быть реализована в виде нескольких типов вставки, применяемых к различным подмножествам данных. Обратите внимание, что эти подмножества состоят из несмежных элементов последовательности данных.

См Википедии подробнее ;-)

Answer 2

insertion sort простая, в месте, O (N^2) сортировка. Shell sort немного сложнее и труднее понять, а где-то вокруг O (N^(5/4)). Проверьте ссылки на примерах - это должно быть легко увидеть разницу.

Answer 3

Shell sort - обобщенная версия Insertion sort. Основной принцип одинаковый для обоих алгоритмов. У вас есть отсортированная последовательность длиной n, и вы вставляете в нее несортированный элемент - и вы получаете n + 1 Элементы, отсортированные в длинном порядке.

Разница следует: в то время как сортировка вставки работает только с одной последовательностью (изначально первый элемент массива) и расширяет ее (используя следующий элемент). Однако сортировка оболочки имеет уменьшающийся приращение, что означает, что между сравниваемыми элементами существует зазор (изначально n/2). Следовательно, есть n/2 последовательности, которые нужно сортировать, используя сортировку вставки. На каждом шаге приращение сжимается (часто просто делятся на 2.2), а количество последовательностей уменьшается. На последнем шаге отсутствует пробел, и алгоритм дегенерирует до простой сортировки вставки.

Из-за уменьшающегося приращения большие и малые элементы быстро перемещаются, чтобы исправить часть массива, а на последнем шаге отсортированы с помощью сортировки вставки очень быстро. Это приводит к уменьшению временной сложности O (n^(4/3))