Введение
Сортировка холма (уменьшение постепенного метода) принадлежит к сортировке класса вставки. Это предложено Shell. Сортировка холма сделала простые улучшения для прямой сортировки вставки: она увеличивает интервал между элементами в сортировке вставки и вставлена в эти элементы интервала, что приводит к перемещению элементов данных в течение большого количества. После того, как эти элементы данных отсортированы один раз, алгоритм сортировки холма уменьшает интервал элементов данных, а затем сортирует, и продолжается по очереди. Интервал между элементами данных, когда эти сортировки называются приращениями, и буква H используется для представления этого приращения.
Обычно используемая H -последовательность предлагается Knuth. Эта последовательность начинается с 1 и генерируется следующей формулой:
h = 3 * h +1
Программа, в свою очередь, должна вычислить последовательность H в обратном направлении, и должна использоваться
H = (H-1)/3
Реализация кода
Код реализации 1:
public static void shellsort (int [] arr) {int temp; for (int delta = arr.length/2; delta> = 1; delta/= 2) {// сортировать каждый приращение один раз для (int i = delta; i <arr.length; i ++) {for (int j = i; j> = delta && arr [j] <arr [j-delta]; j- = delta) {// rite riter и delta empta]; arr [j-delta] = arr [j]; arr [j] = temp; }} // цикл I} // Loop Delta}Код реализации 2:
public static void shellsort2 (int [] arr) {int delta = 1; while (delta <arr.length/3) {// генерировать Delta delta = delta*3+1; // <o (n^(3/2)) от Кнута, 1973>: 1, 4, 13, 40, 121, ...} int temp; for (; delta> = 1; delta/= 3) {for (int i = delta; i <arr.length; i ++) {for (int j = i; j> = delta && arr [j] <arr [j-delta]; j- = delta) {temp = arr [j-delta]; arr [j-delta] = arr [j]; arr [j] = temp; }} // цикл I} // Loop Delta} Когда вышеупомянутая программа сравнивает его с методом прямой вставки, вы обнаружите, что разница между ней и сортом прямой вставки заключается в том, что H в сортировке прямого вставки будет заменена на 1.
Сортировка оболочки нестабильна, его пространственные накладные расходы также являются O (1), и по оценкам, накладные расходы между O (N3/2) и O (N7/6).