Insira o tipo diretamente
1 ideia de classificação:
O RI recorde a ser classificado é inserido nos registros já classificados R1, R2, ..., R (N-1).
Para uma sequência aleatória, a partir do segundo elemento, inserindo o elemento na posição correspondente no elemento antes dele. Os elementos antes de serem classificados.
Primeira ordem: Insira o segundo elemento na lista ordenada na ordem anterior (neste momento, há apenas um elemento no anterior, é claro que é ordenado). Depois disso, os dois primeiros elementos dessa sequência são ordenados.
Segunda classificação: insira o terceiro elemento na lista ordenada do comprimento anterior 2, para que os dois primeiros elementos sejam encomendados.
E assim por diante até que o enésimo elemento seja inserido na lista ordenada do comprimento anterior (N-1).
2 Implementação de algoritmo:
// Insira diretamente a classificação void straight_insert_sort (int num [], int len) {int i, j, key; for (j = 1; j <len; j ++) {key = num [j]; i = j-1; while (i> = 0 && num [i]> key) {num [i+1] = num [i]; eu--; } num [i+1] = key; }}3 Análise de desempenho:
3.1 Complexidade do espaço: Como mencionado acima, é usada uma chave unitária auxiliar e a complexidade do espaço é O (1)
3.2 Complexidade do tempo:
3.2.1 Melhor caso: os registros a serem classificados já estão encomendados e, em seguida, classifique -os em uma viagem, as palavras -chave são comparadas uma vez e os registros são movidos duas vezes. Todo o processo
O número de comparações é
O número de movimentos de registros é
Complexidade do tempo o (n)
3.2.2 Pior caso: os registros a serem classificados já estão em ordem inversa, então os tempos de comparação de palavras-chave são i (de I-1 a 0) e os movimentos de registro (i+2) vezes. Todo o processo
O número de comparações é
O número de movimentos de registros é
Complexidade do tempo o (n^2)
3.2.3 Complexidade média do tempo: o (n^2)
3.3 Estabilidade: estável
Dobre a metade de inserção
1 ideia de classificação:
Com base na classificação direta, os registros a serem classificados RI são inseridos nos registros já classificados R1, R2, ..., R (n-1). Desde que os registros R1, R2, ..., R (n-1) foram classificados, "meio encontro" pode ser usada ao procurar a posição de inserção.
2 Implementação de algoritmo:
// dobra a metade inserir classificar void binary_insert_sort (int num [], int len) {int i, j, chave, baixa, alta, média; for (i = 1; i <len; i ++) {key = num [i]; baixo = 0; alto = i-1; médio = (baixo+alto)/2; // Encontre o ponto de inserção, o ponto de inserção final é baixo enquanto (baixo <= alto) {if (key <num [mid]) high = Mid-1; else Low = Mid+1; médio = (baixo+alto)/2; } // mova registro para (j = i; j> low; j-) {num [j] = num [j-1]; } // Insira gravar num [baixo] = key; }}3 Análise de desempenho:
3.1 Complexidade do espaço: Como mencionado acima, é usada uma chave unitária auxiliar e a complexidade do espaço é O (1)
3.2 Complexidade do tempo: embora a pesquisa semi-acabamento reduz o número de registros e comparações, ela não reduz o número de movimentos; portanto, a complexidade do tempo é a mesma que o algoritmo de pesquisa direta.
3.2.1 Melhor caso: complexidade do tempo o (n)
3.2.2 Pior caso: complexidade do tempo o (n^2)
3.2.3 Complexidade média do tempo: o (n^2)
3.3 Estabilidade: estável