algorithm
Оболочка

Основная информация о Shell

Оболочка Shell , также известная как уменьшающаяся сортировка приращения, является одним из старейших алгоритмов сортировки, названным в честь его изобретателя Дональда. L. Shell (1959). Это быстро, легко понять и легко реализовать. Однако его анализ сложности немного сложнее.

Идея сортировки Shell заключается в следующем:

1. Упорядочить последовательность данных в двумерном массиве
2. Сортировка столбцов массива

Shell sort улучшает сортировку вставки. Он начинается с сравнения элементов, находящихся далеко друг от друга, а затем элементов, находящихся далеко друг от друга, и, наконец, сравнения смежных элементов (фактически сортировки вставки).

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

Пример сортировки Shell:

Псевдокод для Shell Сортировка:

input
foreach element in input
{
    for(i = gap; i < n; i++)
    {
        temp = a[i]
        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
        {
            a[j] = a[j - gap]
        }
        a[j] = temp
    }
}

Вспомогательное пространство: O(n) total, O(1) auxiliary
Сложность времени: O(nlogn)

Реализация C #

public class ShellSort
{
    static void SortShell(int[] input, int n)
    {
        var inc = 3;
        while (inc > 0)
        {
            int i;
            for (i = 0; i < n; i++)
            {
                var j = i;
                var temp = input[i];
                while ((j >= inc) && (input[j - inc] > temp))
                {
                    input[j] = input[j - inc];
                    j = j - inc;
                }
                input[j] = temp;
            }
            if (inc / 2 != 0)
                inc = inc / 2;
            else if (inc == 1)
                inc = 0;
            else
                inc = 1;
        }
    }

    public static int[] Main(int[] input)
    {
        SortShell(input, input.Length);
        return input;
    }
}