Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

2.2.4. С
ОРТИРОВКА 
Ш
ЕЛЛА
 
Этот метод является усовершенствованием метода вставок. Суть его 
заключается в разбиении сортируемого массива на ряд цепочек из равноот-
стоящих друг от друга элементов. Расстояние между элементами одной це-
почки (шаг цепочки) первоначально выбирается достаточно большим. Эле-
менты каждой из цепочек сортируются обычным методом вставок. Однако 
перестановка значений элементов, находящихся на больших расстояниях 
друг от друга, позволяет существенно повысить эффективность алгоритма. 
При последующих просмотрах шаг цепочек уменьшается до тех пор, пока он 
не станет равным 1.
Повышение эффективности алгоритма достигается за счет того, что на 
начальных этапах в сортировке участвуют немного элементов. С каждым 
этапом степень упорядоченности массива повышается и на последнем этапе, 
когда происходит сортировка простыми вставками, число перемещений эле-
ментов невелико. 
В этой сортировке важен правильный выбор величины шагов. Анализ 
показывает, что величины шагов не должны быть кратны друг другу, чтобы 
достигнуть лучших результатов. Д. Кнут [24] рекомендует такие последова-
тельности (записанные в обратном порядке): 
4 / 23

---

28 
1, 4, 13, 40, 121, … , 
где stepk-1=3*stepk+1, 
1, 3, 7. 15, 31, …
где stepk-1=2*stepk+1. 
В листинге 2.9, приведенном ниже, шаги выбирались по формуле
stepk = stepk-1*3/5,
(2.9) 
начиная с step1 = N/2 и заканчивая шагом, равным единице. 
Листинг 2.9. Сортировка Шелла 
public void SortShell(int[] a)
{ 
int N = a.Length; 
int step = N / 2; // 
первый шаг 
while (step >= 1) 
{ 
int k = step; 
for (int i = k + 1; i < N; i++) 
{ 
int tmp = a[i]; int j = i - k; 
while ((j > 0) && (tmp < a[j])) 
{ 
a[j + k] = a[j]; 
j = j - k; 
} 
a[j + k] = tmp; 
} 
// 
определение следующего шага 
step = 3 * step / 5;
} 
} 
5 / 23

---

29 
Анализ алгоритма сортировки Шелла показывает, что скорость его рос-
та O(N). Это значительное улучшение по сравнению с «родительской» сорти-
ровкой простыми вставками, имеющей скорость роста O(N
2
).