O tipo de Shell é um algoritmo de classificação muito "mágico". Diz -se que é "mágico" porque ninguém pode explicar claramente o que seu desempenho pode realmente alcançar. Classificação da colina porque DL. A Shell recebeu o nome de proposta em 1959. Como o carro Hoare propôs a classificação rápida em 1962, geralmente é usado classificação rápida porque é mais simples. No entanto, muitos matemáticos ainda estão incansavelmente procurando a melhor complexidade da classificação de colinas. Como programadores comuns, podemos aprender as idéias de Hill.
A propósito, antes da classificação de Hill aparecer, havia uma visão geral no mundo dos computadores de que "os algoritmos de classificação não podem romper o O (N2)". O surgimento da classificação de colinas quebrou essa maldição e, em breve, algoritmos como classificação rápida foram lançados um após o outro. Nesse sentido, a classificação de Hill nos leva a uma nova era.
Visão geral do algoritmo/idéias
A proposta de classificação da colina é baseada principalmente nos dois pontos a seguir:
1. O algoritmo de classificação de inserção pode atingir aproximadamente a complexidade O (n) e extremamente eficiente quando a matriz é basicamente ordenada.
2. No entanto, a classificação de inserção só pode mover dados por um bit por vez, e o desempenho se deteriorará rapidamente quando a matriz for grande e basicamente desordenada.
Com base nisso, podemos usar um método de classificação de inserção agrupado, que é o método específico: (faça uma matriz de 16 elementos como exemplo)
1. Selecione um delta de incremento, que é maior que 1 e selecione o subarray da matriz por esse incremento para a classificação de inserção direta. Por exemplo, se o incremento for 5 for selecionado, os elementos com subscritos 0, 5, 10, 15 serão classificados.
2. Mantenha o Delta do Incremento e mova o primeiro elemento, por sua vez, para inserção e classificação até que a rodada seja concluída. Para o exemplo acima, as matrizes [1, 6, 11], [2, 7, 12], [3, 8, 13], [4, 9, 14] são classificadas por sua vez.
3. Reduza o incremento e repita o processo acima continuamente até que o incremento diminua para 1. Obviamente, a última vez é o tipo de inserção direta.
4. A classificação é concluída.
Como pode ser visto a partir do exposto, o incremento está diminuindo constantemente, de modo que a classificação das colinas é novamente chamada de "classificação reduzida de incremento".
Implementação de código
tipo de pacote; classe pública ShellSorttest {public static int conting = 0; public static void main (string [] args) {int [] data = new int [] {5, 3, 6, 2, 1, 1, 9, 4, 8, 7}; impressão (dados); Shellsort (dados); impressão (dados); } public static void ShellSort (int [] dados) {// Calcule o valor máximo de h int h = 1; while (h <= data.length / 3) {h = h * 3 + 1; } while (h> 0) {for (int i = h; i <data.length; i += h) {if (data [i] <data [i - h]) {int tmp = data [i]; int j = i - h; while (j> = 0 && data [j]> tmp) {data [j + h] = dados [j]; j -= h; } dados [j + h] = tmp; impressão (dados); }} // Calcule o próximo valor H H = (H - 1) / 3; }} public static void print (int [] dados) {for (int i = 0; i <data.length; i ++) {System.out.print (data [i]+"/t"); } System.out.println (); }} Resultados em execução:
5 3 6 2 1 9 4 8 7 1 3 6 2 5 9 4 8 7 1 2 3 6 5 9 4 8 7 1 2 3 5 6 9 4 8 7 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
Desempenho/complexidade do algoritmo
As seqüências incrementais classificadas por Hill podem ser tomadas a qualquer momento, e o único requisito é que a última deva ser 1 (porque é necessário garantir que seja ordenado por 1). No entanto, a seleção de seqüências diferentes terá um enorme impacto no desempenho do algoritmo. O código acima demonstra dois incrementos.
Lembre -se: é melhor não ter fatores comuns que não sejam 1 para cada dois elementos na sequência incremental! (Obviamente, a classificação por 2 em sequência não é muito significativa).
Abaixo estão algumas sequências incrementais comuns.
O primeiro incremento é o inicialmente proposto por Donald Shell, isto é, a dobra é reduzida para 1. Segundo a pesquisa, usando incrementos das montanhas, a complexidade do tempo ainda é O (n2).
O segundo incremento hibbard: {1, 3, ..., 2^k-1}. A complexidade do tempo dessa sequência incremental é de aproximadamente O (n^1,5).
O terceiro incremento incremento de Sedgewick: (1, 5, 19, 41, 109, ...), que gera uma sequência 9*4^i - 9*2^i + 1 ou 4^i - 3*2^i + 1.
Estabilidade do algoritmo
Todos sabemos que a classificação de inserção é um algoritmo estável. No entanto, a classificação do shell é um processo de múltiplas inserções. Em uma inserção, podemos garantir que a ordem dos mesmos elementos não seja movida, mas em várias inserções, é inteiramente possível que os mesmos elementos sejam movidos em diferentes rodadas de inserção e a estabilidade seja finalmente destruída. Portanto, a classificação de shell não é um algoritmo estável.
Algoritmo cenários aplicáveis
Embora a classificação da concha seja rápida, é uma classificação de inserção, afinal, e sua ordem de magnitude não é tão boa quanto a estrela em ascensão - a classificação rápida O (NN) é rápida. A classificação de shell não é um bom algoritmo diante de uma grande quantidade de dados. No entanto, é completamente possível usar dados pequenos e médios.