Introducción
La clasificación de la colina (reduciendo el método incremental) pertenece a la clasificación de la clase de inserción. Es propuesto por Shell. La clasificación de las colinas ha realizado mejoras simples para la clasificación de inserción directa: aumenta el intervalo entre elementos en la clasificación de inserción e insertos en estos elementos de intervalo, lo que hace que los elementos de datos se muevan a través de un gran tramo. Después de que estos elementos de datos se clasifican una vez, el algoritmo de clasificación de la colina reduce el intervalo de los elementos de datos y luego lo clasifica, y continúa a su vez. El intervalo entre los elementos de datos cuando esta clasificación se llama incrementos, y la letra H se usa para representar este incremento.
La secuencia H comúnmente utilizada es propuesta por Knuth. Esta secuencia comienza a partir de 1 y se genera mediante la siguiente fórmula:
H = 3 * H +1
El programa a su vez debe calcular la secuencia H en reversa y debe usarse
H = (H-1)/3
Implementación del código
Código de implementación 1:
public static void shellsort (int [] arr) {int temp; para (int delta = arr.length/2; delta> = 1; delta/= 2) {// ordene cada incremento una vez para (int i = delta; i <arr.length; i ++) {for (int j = i; j> = delta && arr [j] <arr [j-delta]; j- = delta) {// nota que el incremento y la diferencia son la diferencia y la diferencia arr [j-delta]; arr [j-delta] = arr [j]; arr [j] = temp; }} // bucle i} // bucle delta}Código de implementación 2:
public static void shellSort2 (int [] arr) {int delta = 1; while (delta <arr.length/3) {// Generar delta delta = delta*3+1; // <o (n^(3/2)) por Knuth, 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; }} // bucle i} // bucle delta} Cuando el programa anterior lo compara con el método de inserción directa, encontrará que la diferencia entre él y el tipo de inserción directa es que la H en el tipo de inserción directa será reemplazada por 1.
La clasificación de concha es inestable, su sobrecarga de espacio también es O (1), y se estima que la sobrecarga de tiempo se encuentra entre O (N3/2) y O (N7/6).