Сортировка Шелла: как работает и какая сложность

Коротко

Сортировка Шелла — это улучшенная сортировка вставками. Одна идея превращает квадратичный алгоритм в почти линейно-логарифмический, и при этом код остаётся коротким.

Проблема, которую она решает

У сортировки вставками есть слабое место: элементы двигаются только на одну позицию за шаг. Если самое маленькое число оказалось в конце массива, ему придётся проделать n−1 сдвиг, чтобы добраться до начала.

[9, 8, 7, 6, 1]
                 единице нужно 4 сдвига, чтобы дойти до начала

Дональд Шелл в 1959 году предложил простое решение: сначала сортировать элементы, стоящие далеко друг от друга. Тогда далёкие от места элементы переезжают большими прыжками, а не ползут по одному.

Как это работает

Берём промежуток (gap) — например, половину длины массива. Сортируем вставками элементы, отстоящие друг от друга на этот промежуток. Потом уменьшаем промежуток и повторяем. Последний проход всегда делается с промежутком 1 — это обычная сортировка вставками, но к этому моменту массив уже почти упорядочен, и она отрабатывает почти за O(n).

Разберём [62, 83, 18, 53, 07, 17, 95, 86], начальный промежуток 4:

Проход 1, gap = 4. Сортируем пары, отстоящие на 4: (62, 07), (83, 17), (18, 95), (53, 86).

до:    62  83  18  53 | 07  17  95  86
после: 07  17  18  53 | 62  83  95  86

Проход 2, gap = 2. Сортируем цепочки через одну позицию.

до:    07  17  18  53  62  83  95  86
после: 07  17  18  53  62  83  95  86   (уже упорядочены)

Проход 3, gap = 1. Обычные вставки, но массив почти отсортирован — сдвигов почти нет.

07  17  18  53  62  83  86  95

Код на Python

def shell_sort(arr: list[int]) -> list[int]:
    n = len(arr)
    gap = n // 2

    while gap > 0:
        # сортировка вставками, но с шагом gap вместо 1
        for i in range(gap, n):
            key = arr[i]
            j = i

            while j >= gap and arr[j - gap] > key:
                arr[j] = arr[j - gap]
                j -= gap

            arr[j] = key

        gap //= 2

    return arr


print(shell_sort([62, 83, 18, 53, 7, 17, 95, 86]))
# [7, 17, 18, 53, 62, 83, 86, 95]

Сравните с сортировкой вставками: отличие ровно в том, что единица заменена на gap, а снаружи добавлен цикл уменьшения промежутка. Если подставить gap = 1, получится в точности сортировка вставками.

То же на JavaScript

function shellSort(arr) {
  for (let gap = Math.floor(arr.length / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (let i = gap; i < arr.length; i++) {
      const key = arr[i];
      let j = i;

      while (j >= gap && arr[j - gap] > key) {
        arr[j] = arr[j - gap];
        j -= gap;
      }

      arr[j] = key;
    }
  }

  return arr;
}

Выбор промежутков решает всё

Это самое интересное в алгоритме: его сложность зависит не от кода, а от последовательности промежутков. Здесь до сих пор нет окончательного ответа, какая последовательность оптимальна.

Исходная последовательность деления пополам — худшая из них, зато самая простая. Проблема в том, что все промежутки оказываются степенями двойки, и элементы на чётных и нечётных позициях долго не сравниваются между собой.

Вариант с последовательностью Кнута, которая на практике даёт хороший результат при простом коде:

def shell_sort_knuth(arr: list[int]) -> list[int]:
    n = len(arr)

    # наибольший промежуток вида (3^k - 1) / 2, меньший n
    gap = 1
    while gap < n // 3:
        gap = gap * 3 + 1

    while gap > 0:
        for i in range(gap, n):
            key = arr[i]
            j = i
            while j >= gap and arr[j - gap] > key:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = key

        gap //= 3

    return arr

Почему это быстрее вставок

Два эффекта работают вместе.

Первые проходы дешёвые. При большом промежутке подмассивов много, но каждый очень короткий. Сортировка коротких кусков стоит мало.

Последний проход почти бесплатный. К моменту gap = 1 массив почти отсортирован, а сортировка вставками на таких данных работает за O(n).

Ключевое свойство: после сортировки с промежутком g массив становится «g-упорядоченным», и это свойство не теряется при последующих проходах с меньшими промежутками. Работа накапливается, а не переделывается.

Место среди других сортировок

Ниша сортировки Шелла — когда нужна скорость лучше квадратичной, но нельзя тратить память. Слиянию нужен дополнительный массив, быстрой сортировке — стек рекурсии. Шеллу не нужно ничего.

Отсюда её реальные применения: встраиваемые системы, ядра операционных систем (она используется в uClibc), сортировка в условиях жёстких ограничений по памяти. В прикладном коде на Python или JavaScript вы её вряд ли напишете — там есть встроенный sorted().

Почему она неустойчива

Элементы прыгают через большие расстояния, и равные значения легко меняются местами:

[3a, 2, 3b]  gap = 2 → сравниваем 3a и 3b, порядок может нарушиться

Сделать её устойчивой без потери смысла нельзя — именно дальние перестановки дают выигрыш.

Частые ошибки

Условие j >= gap заменено на j > 0. Приведёт к выходу за границу массива при вычислении arr[j - gap].

Промежуток уменьшается не до единицы. Если цикл заканчивается на gap = 2, массив останется частично неотсортированным. Финальный проход с gap = 1 обязателен всегда.

Уменьшение промежутка внутри внутреннего цикла. Промежуток должен меняться только после полного прохода по массиву.

Что запомнить

• Сортировка Шелла — это сортировка вставками с переменным шагом.
• Дальние перестановки в начале избавляют от медленного «ползания» элементов.
• Сложность зависит от последовательности промежутков: от O(n²) до O(n log² n).
• Деление пополам — самый простой и самый плохой вариант; последовательность Кнута лучше при почти той же простоте.
• Главное преимущество — O(1) памяти при скорости заметно лучше квадратичной.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→