La eficiencia de la clasificación generalmente se compara desde tres aspectos: la cantidad de comparaciones de datos, la cantidad de movimientos de datos y la cantidad de espacio de memoria ocupado.
Hagamos una comparación general de clasificación por burbujas, clasificación por selección, clasificación por inserción y clasificación rápida. El algoritmo de clasificación de burbujas generalmente no se usa porque su número de comparaciones y movimientos es el mayor entre varios algoritmos de clasificación. Su única ventaja es que el algoritmo es simple y fácil de entender, por lo que se puede usar cuando la cantidad de datos es pequeña. habrá algún valor de aplicación. La clasificación por selección tiene el mismo número de comparaciones que la clasificación por burbujas, que es n al cuadrado, pero reduce la cantidad de intercambios al mínimo, por lo que se puede aplicar cuando la cantidad de datos es pequeña y el intercambio de datos lleva más tiempo que comparar. seleccione ordenar.
En la mayoría de los casos, cuando la cantidad de datos es relativamente pequeña o está básicamente ordenada, el algoritmo de clasificación por inserción es la mejor opción. Para ordenar grandes cantidades de datos, la clasificación rápida suele ser el mejor método.
El algoritmo de clasificación anterior ocupa muy poco espacio de memoria y solo requiere una variable adicional para almacenar temporalmente los elementos de datos durante el intercambio. Por lo tanto, no hay comparación en el tamaño del espacio de memoria ocupado.
El número de comparaciones del ordenamiento por inserción sigue siendo n al cuadrado, pero en general es dos veces más rápido que el ordenamiento por burbuja y un poco más rápido que el ordenamiento por selección. A menudo se utiliza en las etapas finales de algoritmos de clasificación complejos, como la clasificación rápida.
Algoritmo: después del procesamiento i-1, se ha ordenado L [1..i-1]. El i-ésimo paso solo inserta L[i] en la posición apropiada de L[1..i-1],
De modo que L[1..i] vuelve a ser una secuencia ordenada. Para lograr este objetivo, podemos utilizar la comparación secuencial.
Primero compare L [i] y L [i-1]. Si L [i-1] <= L [i], entonces L [1..i] ha sido ordenado y el i-ésimo paso de procesamiento ha terminado;
De lo contrario, intercambie las posiciones de L [i] y L [i-1], y continúe comparando L [i-1] y L [i-2] hasta que una determinada posición j (1≤j≤i-1) sea encontró.
Hasta L[j] ≤L[j+1]
Ventajas: se mueven menos elementos y sólo se necesita un espacio auxiliar
Complejidad del tiempo n*n
Este es un buen método de clasificación cuando el número n de registros a ordenar es pequeño. Pero cuando n es muy grande, es inapropiado.
Por ejemplo: int[] valores = { 5, 2, 4, 1, 3 };
Proceso de clasificación:
1.ª vez: 2,5,4,1,3
2da vez: 2,4,5,1,3
3ra vez: 1,2,4,5,3
4ta vez: 1,2,3,4,5
código java:
Copie el código de código de la siguiente manera:
clase pública InsertarOrdenar {
público estático vacío principal (String [] argumentos) {
valores int[] = { 5, 2, 4, 1, 3 };
ordenar(valores);
for (int i = 0; i < valores.longitud; ++i) {
System.out.println(valores[i]);
}
}
clasificación vacía estática pública (valores int []) {
temperatura interna;
int j = 0;
for (int i = 1; i < valores.longitud; i++) {
if(values[i]<values[i-1]) // El juicio aquí es muy importante. Esto refleja la razón por la que la clasificación por inserción es más rápida que la clasificación por burbuja y la clasificación por selección.
{
temperatura = valores[i];
//Mover datos hacia atrás
para (j=i-1; j>=0 && temp<valores[j]; j--)
{
valores[j+1] =valores[j];
}
//Insertar datos en la posición j+1
valores[j+1] =temp;
System.out.print("ésimo" + (i + 1) + "ésimo:");
for (int k = 0; k < valores.longitud; k++) {
System.out.print(valores[k]+",");
}
System.out.println("");
}
}
}
}
Segundo ejemplo
Copie el código de código de la siguiente manera:
paquete cn.cqu.coce.xutao;
clase pública zhijiecharu {
principal vacío estático público (String args []) {
int a[]={1,2,34,67,8,9,6,7,56,34,232,99};
int i,j,k;
para(i=0;i<a.length;i++)
System.out.print(a[i]+"/t");
Sistema.out.println();
for(i=1;i<a.length;i++){
para(j=i-1;j>=0;j--)
si(a[i]>a[j])
romper;
si(j!=i-1){
temperatura interna;
temperatura=a[i];
para(k=i-1;k>j;k--)
a[k+1]=a[k];
a[k+1]=temperatura;
}
}
para(i=0;i<a.length;i++)
System.out.print(a[i]+"/t");
Sistema.out.println();
}
}