Я пытался научиться различным методам сортировки только ради того, чтобы иметь возможность использовать их в будущем, и прямо сейчас я изучаю сортировки оболочки. Я понимаю, как работают сами сортировки оболочки (по сути, это сортировка вставками, за исключением того, что она происходит только между промежутками, которые постепенно увеличиваются в размерах, так что элементы могут перемещаться на «большие расстояния»). Одна вещь, которую я слышал об этом алгоритме, заключается в том, что у вас есть свобода выбора последовательности пробелов, поскольку, очевидно, если вы выберете плохую последовательность, это может сделать последовательность менее эффективной, чем даже обычная сортировка вставками. Так я познакомился с последовательностью пробелов Чиуры (1, 4, 10, 23, 57, 132, 301, 701 и т. д., если я не ошибаюсь) и формулой последовательности пробелов Седжвика, которая, по моему мнению, равна 4*9^i-9*2^i+1.
Моя путаница начинается с попытки использовать их в контексте метода сортировки оболочек. В качестве примера я рассмотрел простую функцию для сортировки оболочки, написанную на Java компанией GeeksForGeeks.
Код: Выделить всё
public static void shellSort(int[] arr) {
int n = arr.length;
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
Я потратил около часа, пытаясь подумать о том, как можно реорганизовать этот метод, чтобы использовать формулу Седжвика или Чиуры, но я был в тупике. Для контекста я должен сказать, что я обучался этим алгоритмам сортировки, изучая, что представляет собой этот алгоритм как концептуально, так и с точки зрения базовой логики кода, а затем писал простые (но все же подходящие/функциональные) версии их на Java, чтобы у меня был справочник по их применению на других языках (поскольку Java был первым языком, который я выучил). Например, одна из проблем, над которой я размышлял, заключается в том, насколько «большой» должна быть последовательность. Должно ли первое/наибольшее значение пробела быть эквивалентным размеру массива/структуры или чему-то еще? Должны ли значения пробелов затем храниться в отдельном массиве для ссылки на параметр, или цикл for сможет справиться с этим за меня, если я напишу его правильно?
Мне бы очень хотелось сжать этот вопрос в TLDR, но я не могу придумать хороший вариант, поскольку я решил выделить для этого как можно больше контекста, о котором я мог подумать. Надеюсь, ты простишь меня за это.
Подробнее здесь:
https://stackoverflow.com/questions/798 ... equence-fo
Мобильная версия