Introdução
A classificação de montanhas (redução do método incremental) pertence à classificação da classe de inserção. É proposto por shell. A classificação da colina fez melhorias simples para a classificação direta da inserção: aumenta o intervalo entre os elementos na classificação da inserção e as inserções nesses elementos de intervalo, fazendo com que os itens de dados se movam em grande parte. Depois que esses itens de dados forem classificados uma vez, o algoritmo de classificação da colina reduz o intervalo de itens de dados e o classifica e prossegue por sua vez. O intervalo entre os itens de dados quando essa classificação é chamado de incrementos e a letra H é usada para representar esse incremento.
A sequência H comumente usada é proposta por Knuth. Esta sequência começa em 1 e é gerada pela seguinte fórmula:
h = 3 * h +1
O programa, por sua vez, precisa calcular a sequência H ao contrário e deve ser usado
h = (h-1)/3
Implementação de código
Código de implementação 1:
public static void Shellsort (int [] arr) {int temp; para (int delta = arr.length/2; delta> = 1; delta/= 2) {// classifica cada incremento uma vez para (int i = delta; i <arn.length; i ++) {for (int j = i; j> = delta && arr [j] <arr [-delta]; Arr [J-Delta] = arr [j]; arr [j] = temp; }} // loop i} // loop delta}Código de implementação 2:
public static void ShellSort2 (int [] arr) {int delta = 1; while (delta <arr.length/3) {// gerar delta delta = delta*3+1; // <o (n^(3/2)) por Knuth, 1973>: 1, 4, 13, 40, 121, ...} int temp; para (; delta> = 1; delta/= 3) {for (int i = delta; i <arr.length; i ++) {for (int j = i; j> = delta && arr [j] <arr [j-delta]; Arr [J-Delta] = arr [j]; arr [j] = temp; }} // loop i} // loop delta} Quando o programa acima o comparar com o método de inserção direta, você descobrirá que a diferença entre ele e o tipo de inserção direta é que o H na classificação de inserção direta será substituído por 1.
A classificação da concha é instável, a sobrecarga do espaço também é O (1) e a sobrecarga do tempo é estimada entre O (N3/2) e O (N7/6).