algorithm
Оболочка
Поиск…
Основная информация о Shell
Оболочка Shell , также известная как уменьшающаяся сортировка приращения, является одним из старейших алгоритмов сортировки, названным в честь его изобретателя Дональда. L. Shell (1959). Это быстро, легко понять и легко реализовать. Однако его анализ сложности немного сложнее.
Идея сортировки Shell заключается в следующем:
- Упорядочить последовательность данных в двумерном массиве
- Сортировка столбцов массива
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;
}
}