Этот алгоритм - модификация сортировки простыми вставками. Идея, например, в случае 16 чисел n1 ... n16 такова: Вначале сортируем простыми вставками каждые 8 групп из 2-х элементов (n1, n9), (n2, n10), ... , (n8, n16). Потом сортируем каждую из четырех групп по 4 элемента (n1, n5, n9, n13), ..., (n4, n8, n12, n16). Далее сортируем 2 группы по 8 элементов, начиная с (n1, n3, n5, n7, n9, n11, n13, n15). А в конце сортируем вставками все 16 элементов. Очевидно, лишь последняя сортировка необходима, чтобы расположить все элементы по своим местам. Так зачем нужны остальные ? Hа самом деле они продвигают элементы максимально близко к соответствующим позициям, так что в последней стадии число перемещений будет весьма невелико. Они и так почти рассортированы. Были проведены многочисленные исследования по вопросу, какова должна быть последовательность расстояний между сортируемыми элементами в зависимости от прохода (инкремент). В конце мы все равно сортируем весь массив вставками, так что, очевидно, любая последовательность подойдет. Hабор ..., 8, 4, 2, 1 - неплохой выбор, особенно, когда N - степень двойки. Hо гораздо лучше будет взять ( 3k - 1 )/2, ..., 40, 13, 4, 1. Ее можно вычислить рекуррентно: i_1 = 1, i_k+1 = 3i_k + 1, k = 1, 2, ... При этой последовательности количество операций даже в наихудшем случае - порядка N^3/2. Для случайной последовательности при N < 60000 количество операций, приблизительно, N^1.25, однако уже при N > 50 QuickSort быстрее. Исходник на Си. void shell(unsigned long n, float a[]) { unsigned long i, j, inc; float v; inc=1; // начальный инкремент do { inc *=3; inc++; } while (inc <= n); do { // Цикл частичных сортировок inc /=3; // Внутренний цикл простых вставок for (i=inc+1; i<=n; i++) { v=a[i]; j=i; while ( a[j-inc] > v) { a[j] = a[j-inc]; j -= inc; if ( j <= inc ) break; } a[j]=v; } } while ( inc > 1 ); }  8  Комментарии к статье  8 8  Обсудить в чате