Вопросы по сортировке Shell

Question

Я студент-второкурсник, изучающий структуру данных, и сегодня этот класс был посвящен алгоритмам сортировки.Мы изучили сортировку выделения, сортировку по пузырям, сортировку по вставке, сортировку по оболочке, быструю сортировку и сортировку слиянием (класс был в таком порядке).И из того, что я помню, сортировка Shell была сделана и разработана так, чтобы она выполнялась быстрее, чем обычная сортировка вставкой.

Итак, процедура такова:

1. разделить исходный список на несколько подсписков, используя пробел.
2. сортируйте подсписок, используя сортировку вставками.
3. непрерывно уменьшайте разрыв и повторяйте, пока разрыв не достигнет 1.

Надеюсь, я не ошибаюсь до этого уровня.Если я, пожалуйста, дайте мне знать.

Если я до сих пор прав, мой вопрос:

Если этот алгоритм, называемый «Shell sort», разработан и считается, что он быстрее обычногосортировка вставкой, тогда почему бы не использовать рекурсивную сортировку Shell на шаге 2?использование сортировки Shell вместо вставки сортировки, когда сортировка подсписков может сделать это быстрее согласно этой логике.

Answer 1

Вы сделали интересное наблюдение.Идея рекурсивного Шеллсорта была в некоторой степени использована в последовательности OEIS A036569 (ищите ее в статье Википедии [ 1 ]):

1 3 7 3*7 3*16 7*16 3*7*16 3*7*41 3*16*41 7*16*41 3*7*16*41...

Однако,как показано на графике внизу [ 1 ], эта последовательность IS85, имеющая большой GCD между ее промежутками, уступает другим последовательностям с небольшим GCD между их промежутками.

Очевидночем больше шагов Shellsort переплетают подсписки, тем меньше общих сравнений (это гипотеза, основанная на эмпирических результатах, а не на теореме).В качестве крайнего примера, прочитайте о поведении оригинальной последовательности гэпов Shell в [ 1 ].