¿Cuáles son los algoritmos de clasificación más utilizados?
Clasificación
Los algoritmos de clasificación utilizados en informática suelen dividirse en:
La complejidad computacional (peor, promedio y mejor rendimiento) depende del tamaño de la lista (norte). En términos generales, un buen desempeño es o(n log n) y un mal desempeño es ω(N2). El rendimiento ideal de clasificación es O (n). Los algoritmos de clasificación que utilizan solo una operación de comparación de claves abstractas requieren al menos ω (n log n) en promedio.
Uso de memoria (y otros usos de recursos informáticos)
Estabilidad: un algoritmo de clasificación estable mantendrá el orden relativo de los registros basándose en claves iguales (en otras palabras, valores). Es decir, un algoritmo de clasificación es estable, es decir, cuando hay dos registros R y S con la misma clave, y R aparece antes de S en la secuencia original, R también aparecerá antes de S en la secuencia ordenada.
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 selectiva incluye la clasificación por agitación y la clasificación por acumulación.
La estabilidad no es un problema cuando elementos iguales son indistinguibles, como los números enteros. Sin embargo, supongamos que los siguientes pares de números se ordenarán por su primer número.
(4, 1) (3, 1) (3, 7) (5, 6)
En este caso pueden ocurrir dos resultados diferentes, uno es Se mantiene el orden relativo basado en valores clave iguales, mientras que el otro no:
(3,1)(3,7)(4,1)(5,6)(Mantener orden)
(3, 7) (3, 1) (4, 1) (5, 6) (orden cambiado)
El algoritmo de clasificación inestable puede cambiar registros en el mismo orden relativo de valor clave, pero algoritmos de clasificación estables no. Un algoritmo de clasificación inestable puede considerarse particularmente estable. Un enfoque es extender manualmente la comparación de valores clave para que una comparación entre dos objetos que de otro modo tendrían el mismo valor clave decida utilizar el elemento en el orden de datos original como resultado final. Sin embargo, tenga en cuenta que este pedido suele conllevar una carga de espacio adicional.
Lista de algoritmos de reemplazo
En esta tabla, n es el número de registros que se ordenarán y k es el número de valores clave diferentes.
Estable
Clasificación de burbujas): O(N2)
Clasificación de cócteles (clasificación de burbujas bidireccional): O(N2)
Inserción sort)—O(N2)
Clasificación de cubos—O(n); requiere O(k) memoria adicional.
Clasificación de conteo: O(n+k); requiere O(n+k) memoria adicional.
Ordenación por fusión): O(n log n); requiere O(n) memoria adicional.
Clasificación por fusión in situ (N2)
La clasificación de árbol binario-o(n log n) requiere o(n) memoria adicional.
Clasificación de casilleros: o(n+k); requiere o(k) memoria adicional.
Clasificación Radix: O(n k); requiere O(n) memoria adicional.
Gnome sort-O(N2)
La biblioteca sort-o(n log n) con mayor probabilidad requiere (1+ε)n memoria adicional.
Volátil
Clasificación por selección) - O(N2)
Clasificación por shell) - O(n log n) si se utiliza la mejor versión actual).
Clasificación combinada: O(n log n)
Clasificación en montón): O(n log n)
Clasificación suave: O(n log n)
clasificación rápida) - O(n log n n) tiempo esperado, O(N2) peor caso para series aleatorias grandes, generalmente se considera la clasificación más rápida conocida.
Clasificación de introducción: O(n log n)
Clasificación de pacientes: O(n log n+k) el tiempo adicional del caso requiere espacio O(n+k) adicional, y usted también Necesitamos encontrar la subsecuencia creciente más larga.
Algoritmo de clasificación poco práctico
bogo sort-o (n×n!) tiempo esperado, peor caso infinito.
Clasificación estúpida: O(n3); la versión recursiva requiere O(N2) memoria adicional.
beadssort - O(n) u O(√n), pero requiere hardware especial.
Clasificación de panqueques: O(n), pero requiere hardware especial.
Algoritmos de clasificación
Existen muchos algoritmos de clasificación y sus requisitos de espacio y eficiencia de tiempo varían. Algunos algoritmos de clasificación comunes se enumeran a continuación. La clasificación por inserción y la clasificación por burbujas también se denominan clasificación simple. No requieren mucho espacio, pero su eficiencia de tiempo es inconsistente. Los últimos tres tipos requieren un poco más de espacio que la clasificación simple, pero la eficiencia del tiempo se puede estabilizar en un nivel superior. La clasificación Radix es un algoritmo de clasificación para palabras clave en un rango pequeño.
Clasificación por inserción
Clasificación por burbujas
Clasificación por selección
Clasificación rápida
Clasificación en montón
Clasificación por fusión
Clasificación Radix
Clasificación Shell
Clasificación por inserción
La implementación de la ordenación por inserción es la siguiente:
p>Primero, cree una lista vacía para contener la secuencia ordenada (la llamamos "lista ordenada").
Toma un número de la serie original e insértalo en la "Lista Ordenada" para mantenerlo ordenado.
Repite el paso 2 hasta que la serie original quede vacía.
La complejidad temporal promedio de la ordenación por inserción es cuadrada, lo que es menos eficiente pero fácil de implementar. Con la ayuda de la idea de "expandir gradualmente el resultado", aumenta gradualmente la longitud de la lista ordenada hasta que su longitud sea igual a la longitud de la lista original.
Clasificación de burbujas
La clasificación de burbujas se implementa de la siguiente manera:
Primero, coloque todos los números que deben ordenarse en la hoja de trabajo.
Comprueba un número desde el primero hasta el penúltimo número de la lista: si un número es mayor que el número que está debajo, cámbialo por el número que está debajo.
Repite el paso 2 hasta que ya no puedas intercambiar.
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 cuadrada, pero también es un algoritmo muy fácil de implementar.
Método de clasificación por selección
La clasificación por selección se implementa de la siguiente manera:
Supongamos que se van a organizar n números en la matriz y el subíndice de la matriz comienza desde 1 y termina con n .
i=1
Encuentre el elemento más pequeño desde el elemento I hasta el elemento N de la matriz.
Intercambia el elemento más pequeño encontrado en el paso anterior por el elemento I-ésimo.
Si I = n-1, el algoritmo finaliza, en caso contrario se regresa al paso 3.
La complejidad temporal promedio de la clasificación por selección también es O(n?).
Clasificación rápida
De ahora en adelante, estaremos expuestos a algoritmos de clasificación eficientes. . La práctica ha demostrado que la clasificación rápida es el más eficaz de todos los algoritmos de clasificación. Adopta la idea de dividir y conquistar: primero asegúrese de que la primera mitad de la lista sea más pequeña que la segunda mitad, y luego ordene la primera mitad y la segunda mitad respectivamente para ordenar la lista completa. Este es un concepto avanzado y la razón por la que es eficiente. Porque en un algoritmo de clasificación, la eficiencia del algoritmo está directamente relacionada con el número de comparaciones entre los números de la lista y "asegúrese de que la primera mitad de la lista sea más pequeña que la segunda mitad" para que cualquier número en la primera la mitad ya no se compara con un número en la segunda mitad, lo que reduce en gran medida las comparaciones innecesarias entre números. Pero encontrar los datos es otra historia.
Clasificación del montón
La clasificación del montón es diferente del algoritmo anterior, es así:
Primero, crea una lista vacía, cuya función es la misma que insertando en la clasificación Lo mismo para "Lista ordenada".
Encuentra el número más grande de la secuencia, agrégalo al final de la lista ordenada y elimínalo de la secuencia original.
Repite el paso 2 hasta que la serie original quede vacía.
La complejidad temporal promedio de la clasificación del montón es nlogn, que es 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 secuencia" solo requiere O ( 1) Complejidad del tiempo, el mantenimiento requiere una complejidad de tiempo), pero la implementación es relativamente compleja (se puede decir que es difícil de implementar entre los siete algoritmos aquí).
La ordenación en montón y la ordenación por inserción pueden parecer similares, pero en realidad son algoritmos esencialmente diferentes. Al menos, su complejidad temporal es de un orden de magnitud diferente: una es cuadrada y la otra es logarítmica.
Complejidad de tiempo promedio
Clasificación por inserción O(N2)
Clasificación por burbujas O(N2)
Clasificación por selección O(N2))
Clasificación rápida
Clasificación en montón O(n log n)
Clasificación por fusión O(n log n)
Clasificación por raíz
p>Clasificación Hill O(n 1.25)
Clasificación de burbujas
654
Por ejemplo, quiero que se ordene de pequeño a grande. ¿cómo hacerlo?
Paso uno: compara 6 y 5. Si encuentra que es más grande de lo que es, reemplácelo. 564
Paso 2: Compara 5 y 4. Si encuentra que es más grande de lo que es, reemplácelo. 465
Paso 3: Compara 6 y 5. Si encuentra que es más grande de lo que es, reemplácelo. 456