| 06 | 12 I 18 | 42 | 44 | 55 | 67 | эЦ
Рис. 3.5. Пример сортировки Шелла
Приводимая программа не ориентирована на некую определенную последовательность расстояний. Все t расстояний обозначаются соответственно hi, hi, ..., ht, для них выполняются условия:
ht=;
hi+i < ht.
Каждая /ьсортировка программируется как сортировка с помощью прямого включения.
Анализ алгоритма.При анализе алгоритма возникают очень сложные математические задачи, многие из которых ещё не решены [3, 9]. В частности, не известно, какие расстояния дают наилучшие результаты. Однако выявлен удивительный факт, что они не должны быть множителями друг другу. Дональд Кнут рекомендует такую последовательность [9]:
1 3 7 15 31 где
hk_x=2hk+ l;
ht= 1 и r=[log2«]-l. В этом случае затраты на сортировку п элементов пропорциональны п ' .