¿Cuáles son los algoritmos de clasificación más utilizados?
Clasificación
Los algoritmos de clasificación utilizados en informática generalmente se dividen en las siguientes categorías:
Complejidad computacional basada en el tamaño de cadena (lista) (n) (peor , promedio y mejor desempeño). En general, un buen rendimiento es O.(n log n) y un mal rendimiento es Ω(n2). El rendimiento de clasificación ideal es O (n). Un algoritmo de clasificación que utiliza solo una operación de comparación de claves abstractas requiere al menos Ω(n log n) en promedio.
Uso de memoria (y uso de otros recursos informáticos)
Estabilidad: un algoritmo de clasificación estable mantiene el orden relativo de los registros basándose en claves iguales (en otras palabras, valores). Es decir, si hay dos registros R y S con valores clave iguales, y si R se clasifica antes que S en la secuencia original, entonces R también se clasificará antes que S en la secuencia ordenada, entonces este algoritmo de clasificación es estable.
Métodos generales: inserción, intercambio, selección, fusión, etc. La clasificación por intercambio incluye la clasificación por burbujas y la clasificación rápida. La clasificación por selección incluye la clasificación por vibración y la clasificación por montón.
La estabilidad no es un problema cuando elementos iguales son indistinguibles (como los números enteros). Sin embargo, supongamos que el siguiente par de números se va a ordenar por su dígito principal.
(4, 1) (3, 1) (3, 7) (5, 6)
En este caso, pueden ocurrir dos resultados diferentes, uno es Mantener orden relativo basado en valores clave iguales, y el otro es no mantener el orden relativo:
(3, 1) (3, 7) (4, 1) (5, 6) (Mantener orden)
(3, 7) (3, 1 ) (4, 1) (5, 6) (cambio de orden)
El algoritmo de clasificación inestable puede cambiar el mismo valor clave El orden relativo entre registros, pero el algoritmo de clasificación estable nunca cambia. Los algoritmos de clasificación inestables se pueden especializar en algoritmos de clasificación estables. Un enfoque consiste en ampliar manualmente la comparación clave-valor para que una comparación entre dos objetos con valores clave iguales utilice las entradas en el orden de datos original como desempate. Sin embargo, tenga en cuenta que esta clasificación suele conllevar una carga de espacio adicional.
Lista de algoritmos de clasificación
En esta tabla, n es el número de registros que se ordenarán y k es el número de valores clave distintos.
Estable
Clasificación de burbujas--O(n2)
Clasificación de cóctel (clasificación de burbujas bidireccional)--O(n2)
Ordenación por inserción--O(n2)
Ordenación por cubo--O(n); requiere O(k) memoria adicional
Ordenación por conteo--O(n+ k); requiere O(n+k) memoria adicional Clasificación de Gnome - O(n2)
Clasificación de bibliotecas - O(n log n), alta probabilidad, requiere (1+ε)n memoria adicional
Inestable
Ordenación por selección - O(n2)
Ordenación Shell - O(n log n) (si se usa la mejor versión actual)
Ordenación por peine - O(n log n)
Ordenación en montón - O(n log n)
Ordenación suave - O(n log n )
Ordenación rápida - O( n log n) tiempo esperado, peor caso O(n2) Generalmente se considera la clasificación más rápida conocida y es adecuada para secuencias grandes y desordenadas
Introclasificación - O(n log n)
Clasificación de pacientes: O (n log n + k) tiempo en el peor de los casos, requiere espacio O (n + k) adicional y también requiere Encontrar la subsecuencia creciente más larga (O (n log n)
Paciente clasificación: O (n log n) tiempo esperado, O (n2) tiempo en el peor de los casos.
Subsecuencia creciente más larga
Algoritmo de clasificación poco práctico
Clasificación Bogo: tiempo esperado O (n × n!), peor de los casos infinito.
Clasificación estúpida: O (n3); la versión recursiva requiere memoria adicional O (n2)
Clasificación de cuentas: O (n) u O (√n), pero requiere especial Refuerzo
Clasificación de panqueques: O (n), pero requiere hardware especial
Algoritmos de clasificación
Hay muchos algoritmos de clasificación con diferentes requisitos de espacio y eficiencia de tiempo. mismo. Algunos algoritmos de clasificación comunes se enumeran a continuación. Entre ellos, la clasificación por inserción y la clasificación por burbujas también se denominan clasificación simple. No tienen grandes requisitos de espacio, pero su eficiencia de tiempo es inestable. Las últimas tres clasificaciones tienen mayores requisitos de espacio que la clasificación simple, pero su eficiencia de tiempo puede ser estable. nivel muy alto. La clasificación básica es un algoritmo de clasificación de palabras clave dentro de un rango más pequeño.
Ordenación por inserción
Ordenación por burbuja
Ordenación por selección
Ordenación rápida
Ordenación por montón
Clasificación resumida
Clasificación comparativa
Clasificación por montaña
El proceso de implementación de la clasificación por inserción es el siguiente:
Primero, cree un nueva lista vacía
Primero cree una nueva lista vacía para contener la lista ordenada (la llamamos "lista ordenada").
Obtiene un número de la lista original y lo inserta en la lista ordenada, manteniéndola ordenada.
Repita el paso 2 hasta que la columna original esté vacía.
La complejidad temporal promedio de la ordenación por inserción es cuadrada, lo que no es muy eficiente, pero es fácil de implementar. Utiliza la idea de expansión incremental para aumentar gradualmente la longitud de la lista ordenada hasta que sea igual a la longitud de la lista original.
Ordenación por burbujas
El proceso de implementación de la ordenación por burbujas es el siguiente:
Primero, coloque todos los números a ordenar en una lista de trabajo.
Desde el primer número de la lista hasta el penúltimo número, comprueba uno por uno: si el número en una determinada posición es mayor que el siguiente, cámbialo por el siguiente.
Repita el paso 2 hasta que no sean posibles más intercambios.
La complejidad temporal promedio de la ordenación por burbujas es la misma que la de la ordenación por inserción, que también es ordenación cuadrada, pero también es un algoritmo muy fácil de implementar.
Ordenación por selección
La ordenación por selección se implementa de la siguiente manera:
Supongamos que hay n números para ordenar almacenados en una matriz y los subíndices de la matriz comienzan de 1 Comienza con n y termina con n.
i=1
Comenzando desde el i-ésimo elemento hasta el n-ésimo elemento de la matriz, encuentre el elemento más pequeño.
Intercambia el elemento más pequeño encontrado en el paso anterior con el elemento i-ésimo.
Si i=n-1 el algoritmo finaliza; de lo contrario, regrese al paso 3.
La complejidad temporal promedio de la clasificación selectiva también es O(n?).
Clasificación rápida
Ahora es el momento de profundizar en algoritmos de clasificación eficientes. Se ha demostrado que la clasificación rápida es uno de los algoritmos de clasificación más eficientes. Utiliza la idea de particionar: primero, garantiza que la primera mitad de la lista sea más pequeña que la segunda mitad, y luego ordena la primera mitad y la segunda mitad por separado, de modo que toda la lista esté en orden. Esta es una idea avanzada, por eso es eficiente. Porque en el algoritmo de clasificación, la eficiencia del algoritmo está directamente relacionada con el número de comparaciones entre números en la lista, y "garantizar que la primera mitad de la lista sea más pequeña que la segunda mitad de la lista" hace que cualquier número en la lista La primera mitad ya no está relacionada con la segunda mitad de la lista. Compare la mitad de los números, lo que reduce en gran medida el número de comparaciones innecesarias. Pero encontrar los datos es otra historia.
Ordenación del montón
La ordenación del montón es diferente del algoritmo anterior. Funciona así:
Primero, crea una nueva lista vacía, que es diferente de la inserción. ordenar. Igual que "lista ordenada" en .
Busca el número más grande de la lista, agrégalo al final de la "lista ordenada" y elimínalo de la lista original.
Repita el paso 2 hasta que la columna original esté vacía.
La complejidad temporal promedio de la clasificación del montón es nlogn, que es muy eficiente (debido a la estructura de datos del montón y sus maravillosas características, la operación de "encontrar el número más grande en la lista" solo requiere O (1) complejidad del tiempo, aunque mantenerla requiere complejidad de tiempo), pero es relativamente complejo de implementar (se puede decir que es uno de los siete algoritmos que es más difícil de implementar aquí).
La ordenación en montón y la ordenación por inserción pueden parecer similares, pero en realidad son algoritmos fundamentalmente diferentes. Al menos, su complejidad temporal difiere en un orden de magnitud, una es cuadrada y la otra es logarítmica.
Complejidad de tiempo promedio
Orden de inserción O(n2)
Orden de burbuja O(n2)
Orden de selección O(n2)
Ordenación rápida O(n log n)
Ordenación en montón O(n log n)
Ordenación por suma O(n log n)
Clasificación por base O (n)
Clasificación por montaña O (n1.25)
Clasificación por burbuja
654
Por ejemplo, suponiendo que Esto es, quiero ordenar de pequeño a grande, ¿cómo hago esto?
Paso 1: Compara 6 con 5, y cuando veas que es más grande, cámbialo. 564
Paso 2: Compara 5 con 4, y cuando encuentres que es más grande, cámbialo. 465
Paso 3: Compara 6 con 5, y cuando encuentres que es más grande, cámbialo.