Classificação de inserção direta
A idéia de inserir a classificação diretamente é fácil de entender, parece a seguinte:
1. Divida a matriz a ser classificada em duas partes: classificadas e não classificadas. No começo, o primeiro elemento é considerado classificado.
2. Comece com o segundo elemento, encontre a posição apropriada do elemento no subarray classificado e insira -o.
3. Repita o processo acima até que o último elemento seja inserido no subarray ordenado.
4. A classificação é concluída.
Exemplo:
A ideia é simples, mas o código não é tão fácil de escrever quanto a classificação de bolhas. Primeiro de tudo, como determinar a posição certa? Maior ou igual à esquerda, menor ou igual à direita? Não, muitas condições de contorno precisam ser consideradas e há muitos julgamentos. Em segundo lugar, a inserção de elementos em uma matriz exigirá inevitavelmente mover um grande número de elementos. Como controlar o movimento deles?
De fato, isso não é um problema com o próprio algoritmo e tem algo a ver com a linguagem de programação. Às vezes, o algoritmo em si já é muito maduro e ainda precisa ser ligeiramente alterado quando se trata da linguagem de programação específica. O que estamos falando aqui é o algoritmo Java, então vamos falar sobre Java.
Para resolver o problema acima, fizemos um pouco de refinamento da segunda etapa. Não começamos a comparação da posição inicial da sub-matriz, mas iniciamos a comparação inversa da cauda da sub-matriz. Desde que seja maior que o número que precisa ser inserido, nos movemos para trás. Até que o número não seja maior que o número, o número a ser inserido será colocado nessa posição vazia. Portanto, podemos escrever o seguinte código:
InsertArray.java
classe pública InsertArray {// Array Private Long [] arr; // o tamanho dos dados válidos no Array Private Int elems; // Construtor padrão public insertArray () {arr = new Long [50]; } public insertArray (int max) {arr = new Long [max]; } // Insira dados public void insert (valor longo) {arr [elems] = value; elems ++; } // mostra dados public void Display () {for (int i = 0; i <elems; i ++) {System.out.print (arr [i]+""); } System.out.println (); } // Insira classificar public void insertSort () {long Select = 0l; for (int i = 1; i <elems; i ++) {select = arr [i]; int j = 0; for (j = i; j> 0 && arr [j - 1]> = selecione; j--) {arr [j] = arr [j - 1]; } arr [j] = selecione; }}} Classe de teste:
TestInsertArray.java
classe pública testInserTarray {public static void main (string [] args) {insertArray iarr = new insertArray (); Iarr.insert (85); Iarr.insert (7856); Iarr.insert (12); Iarr.insert (8); Iarr.insert (5); Iarr.insert (56); iarr.display (); iarr.insertsort (); iarr.display (); }} Resultado de impressão:
Desempenho/complexidade do algoritmo
Agora, vamos discutir a complexidade do tempo do algoritmo de inserção direta. Independentemente da entrada, o algoritmo sempre executa as rodadas N-1 de classificação. No entanto, como o ponto de inserção de cada elemento é incerto e muito afetado pelos dados de entrada, sua complexidade não é certa. Podemos discutir as melhores, piores e médias situações.
1. Melhor caso: A partir das características do algoritmo, pode -se observar que quando a matriz a ser organizada está em ordem positiva (a matriz é ordenada e a ordem é a mesma da ordem necessária, que está em ordem crescente sob a premissa de discussão). O motivo é que, neste caso, cada elemento só precisa ser comparado uma vez e não precisa ser movido. A complexidade do tempo do algoritmo é O (n);
2. Pior caso: obviamente, quando a matriz a ser organizada está em ordem inversa, é o pior caso. Nesse caso, nosso número de comparações por rodada é I-1 e o número de atribuições é i. O número total de vezes é a soma dos primeiros n Termos da Série 2N-1, ou seja, n^2. A complexidade do tempo do algoritmo é O (n^2);
3. Situação média: a partir da análise acima, podemos obter que o número de operações do algoritmo sob a situação média é de aproximadamente (n^2)/2 (Nota: o cálculo aqui é baseado na atribuição e comparação. Se for baseado em movimento e comparação, é aproximadamente n^2/4). Obviamente, a complexidade do tempo ainda é O (n^2).
Quanto à complexidade espacial do algoritmo, todos os movimentos são realizados dentro dos dados. A única sobrecarga é que introduzimos uma variável temporária (algumas estruturas de dados são chamadas de "sentinelas" nos livros), portanto, sua complexidade espacial (espaço extra) é O (1).
Estabilidade do algoritmo
Como você só precisa encontrar uma posição que não seja maior que o número atual e não precisa trocar, inserir diretamente a classificação é um método de classificação estável.
Variantes de algoritmo
Se houver muitos dados a serem organizados, isso causará muita sobrecarga toda vez que você olha por trás para a frente. Para melhorar a velocidade de pesquisa, a pesquisa binária pode ser usada para otimização de desempenho. Como a eficiência da pesquisa binária é muito alta, a complexidade O (n) é garantida e a eficiência da pesquisa pode ser bastante aprimorada quando há mais dados ou os dados de entrada tendem a estar no pior. Em alguns livros, esse método é chamado de dobragem e metade da classificação de inserção. Sua implementação de código é bastante complicada e pode ser publicada se você tiver tempo no futuro.
Além disso, existem tipos de inserção de duas vias e tipos de inserção de tabela. A classificação de inserção bidirecional é aprimorada ainda mais com base na dobragem e na metade da espécie de inserção, e seu número de movimentos é bastante reduzido, cerca de n^2/8. No entanto, não evita o número de movimentos e não reduz o nível de complexidade. O tipo de inserção da tabela altera completamente a estrutura de armazenamento e não move registros, mas uma lista vinculada precisa ser mantida e o ponteiro da lista vinculado é modificado em vez de mover registros. Portanto, sua complexidade ainda é O (n^2).
Para classificação de inserção bidirecional e classificação de inserção de tabela, você pode consultar o livro "Data Structure" editado por Yan Weimin e Wu Weimin.
Algoritmo cenários aplicáveis
A classificação de inserção não é aplicável quando a matriz é grande devido à complexidade de O (n^2). No entanto, quando há relativamente poucos dados, é uma boa escolha, geralmente usada como expansão para classificação rápida. Por exemplo, no algoritmo de classificação do STL e no algoritmo QSORT do stdlib, a classificação de inserção é usada como um suplemento para classificação rápida e é usada para classificar um pequeno número de elementos. Por exemplo, na implementação do método de classificação usado no JDK 7 java.util.arrays, quando a duração da matriz a ser classificada for menor que 47, a classificação de inserção será usada.