Автор: mefestofel (22.05.2007 в 11:28)
Исходный массив разбивается на n частей , в каждую из которых попадают элементы с шагом n, начиная от от 0,1,..., n-1, то есть:
0, n, 2n, 3n
1, n+1, 2n+1, 3n+1
2, n+2, 2n+2, 3n+2
...
|
Каждая часть сортируется отдельно с использованием алгоритма вставок или алгоритма обмена, Затем выбирается меньший шаг и алгоритм повторяется... Несмотря на увеличение циклов, суммарное число перестановок будет меньшим...
P.S. Шаг удобнее выбрать равным степеням 2. Сортировкой Шелла удобно сортироваь небольшие массивы...