Сортировка Шелла

Сортировка Шелла — это эффективная улучшенная версия сортировки вставками, предложенная Дональдом Шеллом в 1959 году.

Основная идея сортировки Шелла заключается в следующем:разделив исходный список на несколько подпоследовательностей, сначала выполнить сортировку вставками для каждой подпоследовательности, затем постепенно уменьшать интервал между подпоследовательностями и, наконец, выполнить стандартную сортировку вставками для всего списка.Этот метод позволяет элементам перемещаться на большие расстояния, тем самым устраняя большое количество инверсий на ранних этапах и значительно повышая эффективность сортировки.

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

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

Ключ к сортировке Шелла заключается в так называемойпоследовательности приращенийконцепции. Последовательность приращений определяет интервал для разделения подпоследовательностей каждый раз. Алгоритм выполняет несколько раундов сортировки списка в соответствии с постепенно уменьшающейся последовательностью приращений.

Шаги алгоритма

  1. Выберите последовательность приращений.Определите последовательность целых чисел от большего к меньшему, причём последнее приращение должно быть равно 1. Чаще всего в качестве начального приращения используется половина длины массива, а затем оно каждый раз уменьшается вдвое.
  2. Группировка по приращению: для текущего приращенияgap, разделите весь список наgapподпоследовательности. Каждая подпоследовательность состоит из всех элементов с интерваломgapСостав элементов.
  3. выполните сортировку вставками для подпоследовательностейВыполните сортировку вставками для каждой подпоследовательности отдельно.
  4. Уменьшите приращениеПолучите новое, меньшее приращение и повторите шаги 2 и 3.
  5. Окончательная сортировкаКогда приращение уменьшается до 1, выполняется стандартная сортировка вставками для всего списка; в этот момент список уже в основном упорядочен, поэтому сортировка завершается быстро.

Применимость

Временная сложность сортировки Шелла —O(n^(1.3-2)), а пространственная сложность имеет постоянный порядокO(1). Сортировка Шелла не так быстра, какO(n(logn)); алгоритм быстрой сортировки быстр, поэтому она хорошо работает при средних размерах, но не является оптимальным выбором для сортировки очень больших наборов данных. Короче говоря, по сравнению с обычнымиO(n^2 )алгоритмы с такой временной сложностью намного быстрее.

Схема процесса

Цель сортировки Шелла — улучшить сортировку вставками для повышения скорости. Она меняет местами несоседние элементы, чтобы сортировать части массива, и в конце использует сортировку вставками для сортировки локально упорядоченного массива.

Здесь мы выбираем приращениеgap=length/2, уменьшаем приращение доgap = gap/2методом, используя последовательность{n/2,(n/2)/2...1}для представления.

Как показано в примере:

(1) Первый проход с начальным приращениемgap = length/2 = 4

(2) Второй проход, приращение уменьшается до 2

(3) Третий проход, приращение уменьшается до 1, получая окончательный отсортированный результат

Пример кода на Java

Загрузка пакета исходного кода:Скачать

Самый внутренний цикл на самом деле является сортировкой вставками:

Код файла ShellSort.java:

public class ShellSort {
    // Основной код --- начало
    public static void sort(Comparable[] arr) {
        int j;
        for (int gap = arr.length / 2; gap >  0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                Comparable tmp = arr[i];
                for (j = i; j >= gap && tmp.compareTo(arr[j - gap]) < 0; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j] = tmp;
            }
        }
    }
    // Основной код --- конец
    public static void main(String[] args) {

        int N = 2000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 10);
        ShellSort.sort(arr);
        for( int i = 0 ; i < arr.length ; i ++ ){
            System.out.print(arr[i]);
            System.out.print(' ');
        }
    }
}

Реализация алгоритма на Python

Мы будем использовать Python для реализации сортировки Шелла и выберем наиболее распространённую настройку приращения (исходную последовательность Шелла):gap = n // 2, и продолжаемgapвыполнять целочисленное деление на 2, покаgapравно 1.

Пример

def shell_sort(arr):
    """
Используйте алгоритм сортировки Шелла, чтобы отсортировать список по возрастанию на месте.
   
Параметры:
arr (list): список, который нужно отсортировать.
   
Возвращает:
list: Отсортированный список (изменён на месте, также возвращён).
    """
    n = len(arr)
    # Установите начальный шаг gap равным половине длины массива
    gap = n // 2
   
    # Цикл, пока gap не уменьшится до 0
    while gap > 0:
        # Начиная с gap, выполните «сортировку вставками» для каждого элемента
        # Примечание: Здесь i идёт от gap до n-1, перебирая все элементы
        for i in range(gap, n):
            # Сохраните arr[i] во временную переменную temp
            temp = arr[i]
            j = i
            # Выполните сортировку вставками для подпоследовательности при текущем gap
            # Если предыдущий элемент в той же подпоследовательности больше temp, сдвиньте его назад
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            # Вставить temp в правильную позицию
            arr[j] = temp
        # Уменьшить шаг, например, уменьшить gap вдвое
        gap //= 2
   
    return arr

# Тестовый код
if __name__ == "__main__":
    # Тестовые данные 1: случайный перемешанный порядок
    test_array = [8, 3, 5, 1, 4, 2, 7, 6]
    print("До сортировки:", test_array)
    sorted_array = shell_sort(test_array.copy()) # Используйте copy, чтобы не изменять исходный массив
    print("После сортировки:", sorted_array)
   
    # Тестовые данные 2: содержит повторяющиеся элементы
    test_array2 = [5, 2, 9, 5, 2, 3, 5]
    print("\nДо сортировки:", test_array2)
    print("После сортировки:", shell_sort(test_array2.copy()))
   
    # Тестовые данные 3: обратный массив
    test_array3 = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
    print("\nПеред сортировкой:", test_array3)
    print("После сортировки:", shell_sort(test_array3.copy()))

Анализ кода:

  1. def shell_sort(arr):Определите функцию сортировки Шелла.
  2. n = len(arr)Получите длину массива.
  3. gap = n // 2Инициализируйте приращение. Это наиболее классическая начальная точка для последовательности приращений в сортировке Шелла.
  4. while gap > 0:Внешний цикл, управляющий приращением, которое постепенно уменьшается, пока не станет 0 (после того как оно фактически было 1 и выполнение завершилось,gap //= 2оно становится 0 и происходит выход).
  5. for i in range(gap, n):Внутренний цикл. Начиная с индексаgapНачните обход.iуказывает на текущий элемент, который нужно вставить. Обратите внимание, что этот цикл умело обрабатывает все элементы сgapподпоследовательности с ... в качестве интервала.
  6. temp = arr[i]иj = i: сохранить значение текущего элемента и использоватьjчтобы запомнить позицию, в которую его следует вставить в текущей подпоследовательности.
  7. while j >= gap and arr[j - gap] > temp:Это ядро сортировки вставками. Внутри одной и той же подпоследовательности (поj - gapиндексу для доступа к предыдущему элементу), если предыдущий элемент большеtempесли он больше, сдвинуть предыдущий элемент назадgapпозицию.
  8. arr[j] = temp: сохранённоеtempвставить значение в правильную позицию.
  9. gap //= 2После одного раунда сортировки уменьшить приращение вдвое и выполнить следующий раунд более точной сортировки.
  10. return arr: вернуть отсортированный массив.

Выбор последовательности приращений.

Выбор последовательности приращений напрямую влияет на производительность сортировки Шелла. Выше мы использовали исходную последовательность Шелла (n/2, n/4, ..., 1), но она не оптимальна. Ниже приведено несколько распространённых последовательностей приращений:

Название последовательности Формула генерации Характеристики и сложность.
Исходная последовательность Шелла $gap = \lfloor \frac{n}{2} \rfloor, gap = \lfloor \frac{gap}{2} \rfloor...$ Проста в реализации, временная сложность в худшем случае — $O(n^2)$.
Последовательность Хиббарда $1, 3, 7, 15, ..., 2^k - 1$ Временную сложность в худшем случае можно улучшить до $O(n^{3/2})$.
Последовательность Кнута $1, 4, 13, 40, ..., (3^k - 1) / 2$ (меньше n) Средняя временная сложность составляет примерно $O(n^{1.25})$, и она часто используется на практике.
Последовательность Седжвика $1, 5, 19, 41, 109, ...$ (смесь $9 \times 4^k - 9 \times 2^k + 1$ и $4^k - 3 \times 2^k + 1$) Это одна из наиболее известных последовательностей, сложность в худшем случае достигает $O(n^{4/3})$.

Пример реализации с использованием последовательности Кнута

Пример

def shell_sort_knuth(arr):
    n = len(arr)
    # Сгенерировать последовательность приращений Кнута: 1, 4, 13, 40, 121, ...
    gap = 1
    while gap < n // 3:
        gap = 3 * gap + 1  # Сгенерировать максимальное начальное приращение
   
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 3  # Кнут предлагает каждый раз делить на 3
    return arr

# Проверить версию с последовательностью Кнута
test_array = [33, 12, 56, 78, 2, 45, 67, 89, 1, 23]
print(Перед сортировкой с использованием последовательности Кнута:, test_array)
print(После сортировки с использованием последовательности Кнута:, shell_sort_knuth(test_array.copy()))

Характеристики алгоритма и анализ сложности

Временная сложность

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

  • Худший случайПри использовании оригинальной последовательности Шелла временная сложность в худшем случае равна $O(n^2)$.
  • Средний случай: Для лучших последовательностей шагов (таких как Кнут, Седжвик) средняя временная сложность находится между $O(n^{1.25})$ и $O(n^{1.5})$.
  • Лучший случайКогда массив уже отсортирован, сложность может приближаться к $O(n \log n)$.

Пространственная сложность

  • Сортировка Шелла — этосортировка на месте— алгоритм, требующий только константный объём дополнительной памяти (например,temp, gap, i, jпеременных), поэтому пространственная сложность равна $O(1)$.

Стабильность

  • Сортировка Шелла — этонеустойчивыйалгоритм сортировки. Потому что при сортировке группами по шагу равные элементы могут попасть в разные подпоследовательности, и их относительный порядок может измениться из-за перемещений.

Простое сравнение с другими алгоритмами сортировки

Особенности Сортировка Шелла Сортировка вставками Сортировка слиянием Быстрая сортировка
Средняя временная сложность. $O(n^{1.25})$ ~ $O(n^{1.5})$ $O(n^2)$ $O(n \log n)$ $O(n \log n)$
Пространственная сложность $O(1)$ $O(1)$ $O(n)$ $O(\log n)$
Стабильность неустойчивая Устойчивая Устойчивая неустойчивая
Преимущества Хорошая производительность для данных среднего размера, сортировка на месте Простая, эффективна для небольших объёмов данных или почти отсортированных данных Устойчивая, отличная временная сложность Самая быстрая в среднем случае.
Недостатки Анализ сложности затруднён, и выбор последовательности приращений оказывает большое влияние. Низкая эффективность при больших объёмах данных. Требует дополнительного пространства. В худшем случае она деградирует до $O(n^2)$.

Больше примеров кода.

Другие расширения