A eficiência da classificação é geralmente comparada a partir de três aspectos: o número de comparações de dados, o número de movimentações de dados e a quantidade de espaço de memória ocupado.
Vamos fazer uma comparação geral entre classificação por bolha, classificação por seleção, classificação por inserção e classificação rápida. O algoritmo de classificação por bolhas geralmente não é usado porque seu número de comparações e movimentos é o maior entre vários algoritmos de classificação. Sua única vantagem é que o algoritmo é simples e fácil de entender, portanto pode ser usado quando a quantidade de dados é pequena. será algum valor de aplicação. A classificação por seleção tem o mesmo número de comparações que a classificação por bolha, que é n ao quadrado, mas reduz o número de trocas ao mínimo, portanto pode ser aplicada quando a quantidade de dados é pequena e a troca de dados consome mais tempo do que comparar dados. Selecione classificar.
Na maioria dos casos, quando a quantidade de dados é relativamente pequena ou basicamente ordenada, o algoritmo de classificação por inserção é a melhor escolha. Para classificar grandes quantidades de dados, o quicksort geralmente é o melhor método.
O algoritmo de classificação acima ocupa muito pouco espaço de memória e requer apenas uma variável adicional para armazenar temporariamente os itens de dados durante a troca. Portanto, não há comparação no tamanho do espaço de memória ocupado.
O número de comparações da classificação por inserção ainda é n ao quadrado, mas em geral é duas vezes mais rápido que a classificação por bolha e um pouco mais rápido que a classificação por seleção. É frequentemente usado nos estágios finais de algoritmos de classificação complexos, como o quicksort.
Algoritmo: Após o processamento i-1, L[1..i-1] foi classificado. A i-ésima passagem apenas insere L[i] na posição apropriada de L[1..i-1],
Portanto, L[1..i] é uma sequência ordenada novamente. Para atingir esse objetivo, podemos usar a comparação sequencial.
Primeiro compare L[i] e L[i-1]. Se L[i-1]<=L[i], então L[1..i] foi classificado e a i-ésima passagem do processamento terminou;
Caso contrário, troque as posições de L[i] e L[i-1] e continue a comparar L[i-1] e L[i-2] até que uma certa posição j (1≤j≤i-1) seja encontrado.
Até L[j] ≤L[j+1]
Vantagens: menos elementos são movidos e apenas é necessário um espaço auxiliar
Complexidade de tempo n*n
Este é um bom método de classificação quando o número n de registros a serem classificados é pequeno. Mas quando n é muito grande, é inapropriado
Por exemplo: valores int[] = { 5, 2, 4, 1, 3 };
Processo de classificação:
1ª vez: 2,5,4,1,3
2ª vez: 2,4,5,1,3
3ª vez: 1,2,4,5,3
4ª vez: 1,2,3,4,5
código java:
Copie o código do código da seguinte forma:
classe pública InsertSort {
public static void main(String[] args) {
int[] valores = { 5, 2, 4, 1, 3 };
ordenar(valores);
for (int i = 0; i < valores.comprimento; ++i) {
System.out.println(valores[i]);
}
}
public static void sort(int[] valores) {
temperatura interna;
int j = 0;
for (int i = 1; i < valores.comprimento; i++) {
if(values[i]<values[i-1])//O julgamento aqui é muito importante. Isso reflete a razão pela qual a classificação por inserção é mais rápida do que a classificação por bolha e a classificação por seleção.
{
temperatura = valores[i];
//Move os dados para trás
for (j=i-1; j>=0 && temp<valores[j]; j--)
{
valores[j+1] =valores[j];
}
//Inserir dados na posição j+1
valores[j+1] =temp;
System.out.print("th" + (i + 1) + "th:");
for (int k = 0; k < valores.comprimento; k++) {
System.out.print(valores[k]+",");
}
System.out.println("");
}
}
}
}
Segundo exemplo
Copie o código do código da seguinte forma:
pacote cn.cqu.coce.xutao;
classe pública zhijiecharu {
public static void main(String args[]){
int a[]={1,2,34,67,8,9,6,7,56,34,232,99};
int eu,j,k;
para(i=0;i<a.comprimento;i++)
System.out.print(a[i]+"/t");
System.out.println();
for(i=1;i<a.comprimento;i++){
para(j=i-1;j>=0;j--)
se(a[i]>a[j])
quebrar;
se(j!=i-1){
temperatura interna;
temperatura=a[i];
para(k=i-1;k>j;k--)
uma[k+1]=uma[k];
a[k+1]=temperatura;
}
}
para(i=0;i<a.comprimento;i++)
System.out.print(a[i]+"/t");
System.out.println();
}
}