Как правильно реализовать Knuth Sequence для оболочки в Java?

Question

Может ли кто-нибудь предоставить простой рабочий образец оболочки в Java, который использует последовательность Кнута? Я смотрел в нескольких местах через Интернет, но не могу найти объяснение, которое хорошо работает для меня. Я понимаю shellsort на концептуальном уровне - поскольку это сортировка вставки, которая выполняется за промежуток, который со временем сокращается, до достижения промежутка 1, который тогда по существу является сортировкой вставки. Однако последовательность Кнута (k * 3 - 1)/2, а список первых нескольких промежутков обычно представлен как [1, 4, 13, 40, 121 .. и т. Д.].

Вопрос в том, как это реализовать? Действительно ли начальный пробел равен 1, или это значение, генерируемое этой последовательностью, прежде чем оно будет больше, чем размер сортируемого списка? Если пробел начинался с 1, цель была бы побеждена, если я правильно понимаю оболочку. Может ли кто-то пролить свет на это? Я чувствую, что пропустил что-то важное для понимания этой вещи.

Заранее спасибо.

Answer 1

Я нашел один на http://algs4.cs.princeton.edu/ (см. Главу «Элементарные сортировки»). Исходный код можно найти here

Класс Shell предоставляет статические методы для сортировки в массив, используя ShellSort с последовательностью Кнута приращения (1, 4, 13, 40, ...). Дополнительную документацию см. В разделе «http://algs4.cs.princeton.edu/21elementary» (раздел 2.1) «Алгоритмы, 4-е издание» Роберта Седжуика и Кевина Уэйна.