1. Введение
В этом учебнике мы опишем алгоритм сортировки Shell на Java.
2. Обзор сортировки оболочки
2.1. Описание объекта
Давайте сначала опишем алгоритм сортировки Shell, чтобы мы знали, что мы пытаемся реализовать.
Сорт оболочки основан на Алгоритм сортировки вставки , и он принадлежит к группе очень эффективных алгоритмов. В общем, алгоритм разбивает исходный набор на более мелкие подмножества, а затем каждый из них сортируется с помощью сортировки вставки .
Но, как это делает подмножества не просто. Он не выбирает соседние элементы для формирования подмножества, как мы могли бы ожидать. Скорее, сортировка оболочки использует так называемую интервал или разрыв для создания подмножества. Например, если у нас есть пробел Я это означает, что один подмножество будет содержать элементы которые Я позиции друг от друга.
Во-первых, алгоритм сортирует элементы, которые находятся далеко друг от друга. Затем разрыв становится меньше и сравниваются более близкие элементы. Таким образом, некоторые элементы, которые не в правильном положении могут быть расположены быстрее, чем если бы мы сделали подмножества из соседних элементов.
2.2. Пример
Рассмотрим это в примере с пробелами 3 и 1 и несортированным списком из 9 элементов:
Если мы будем следовать описанию выше, в первой итерации, мы будем иметь три подмножества с 3 элементами (подчеркнуто тем же цветом):
После сортировки каждого из подмножеов в первой итерации список будет выглядеть так:
Можно отметить, что, хотя у нас пока нет отсортированного списка, элементы теперь ближе к желаемым позициям.
Наконец, мы должны сделать еще один сорт с шагом одного, и это на самом деле основной сортировки вставки. Количество операций по смещению, которые мы должны выполнить для сортировки списка, теперь меньше, чем если бы мы не сделали первую итерацию:
2.3. Выбор последовательностей разрыва
Как мы уже упоминали, сортировка оболочки имеет уникальный способ выбора последовательностей зазоров. Это трудная задача, и мы должны быть осторожны, чтобы не выбрать слишком мало или слишком много пробелов. Более подробную информацию можно найти в наиболее предлагаемые последовательности пробелов листинг .
3. Осуществление
Давайте теперь рассмотрим реализацию. Мы будем использовать исходную последовательность Shell для интервальных приращений:
N/2, N/4, …, 1 (continuously dividing by 2)
Сама реализация не слишком сложна:
public void sort(int arrayToSort[]) {
int n = arrayToSort.length;
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int key = arrayToSort[i];
int j = i;
while (j >= gap && arrayToSort[j - gap] > key) {
arrayToSort[j] = arrayToSort[j - gap];
j -= gap;
}
arrayToSort[j] = key;
}
}
}Сначала мы создали последовательность зазоров с циклом, а затем сделали сортировку вставки для каждого размера разрыва.
Теперь мы можем легко протестировать наш метод:
@Test
public void givenUnsortedArray_whenShellSort_thenSortedAsc() {
int[] input = {41, 15, 82, 5, 65, 19, 32, 43, 8};
ShellSort.sort(input);
int[] expected = {5, 8, 15, 19, 32, 41, 43, 65, 82};
assertArrayEquals("the two arrays are not equal", expected, input);
}4. Сложность
Как правило, алгоритм сортировки Shell очень эффективен со средними списками . Сложность трудно определить, так как она во многом зависит от последовательности разрыва, но сложность времени варьируется между О(Н) и О(Н2) .
Наихудшей сложностью пространства является О(Н) с O(1) вспомогательное пространство.
5. Заключение
В этом учебнике мы описали сортировку Shell и проиллюстрировали, как мы можем реализовать ее на Java.
Как обычно, весь код можно найти более на GitHub .