Un resumen de varios algoritmos de clasificación comunes
Para mí, un estudiante no especializado, los algoritmos parecen ser un punto difícil para mí. Verifiqué cierta información y aproveché esta oportunidad para aprender sobre varios algoritmos de clasificación.
Primero, comprendamos qué es un programa.
En cuanto a los algoritmos de clasificación, generalmente nos referimos al algoritmo de clasificación interno, es decir, los registros de datos se ordenan en la memoria.
Los algoritmos de clasificación se pueden dividir aproximadamente en dos tipos:
Uno es la clasificación por comparación, con una complejidad de tiempo O (nlogn) ~ O (n ^ 2), que incluye principalmente: clasificación de burbujas, clasificación por selección, clasificación por inserción, clasificación por combinación, clasificación por montón, clasificación rápida, etc.
Otro tipo de clasificación sin comparación, la complejidad del tiempo puede alcanzar O (n), que incluye principalmente: clasificación por conteo, clasificación por base, clasificación por cubos, etc.
La clasificación por burbujas visita repetidamente A través de los elementos que se van a ordenar, compare dos elementos adyacentes a la vez y cámbielos si están en el orden incorrecto, hasta que ya no sea necesario intercambiar elementos y se complete la clasificación. El nombre de este algoritmo proviene del hecho de que los elementos más pequeños (o más grandes) "flotarán" lentamente hasta la parte superior de la matriz mediante el intercambio.
La ordenación por selección es similar a la ordenación por burbujas, excepto que la ordenación por selección primero encuentra el valor mínimo (valor máximo) en la secuencia sin clasificar, lo coloca al principio de la secuencia y luego elimina los elementos restantes sin clasificar de la secuencia. Continúe buscando el elemento más pequeño (más grande) en la secuencia y colóquelo al final de la secuencia ordenada, y así sucesivamente hasta que todos los elementos estén ordenados.
La clasificación por inserción es más eficiente que la clasificación por burbujas y la clasificación por selección es similar a atrapar cartas de póquer en la vida.
La descripción del algoritmo específico de ordenación por inserción toma la matriz [3, 2, 4, 5, 1] como ejemplo.
Los primeros tres algoritmos de clasificación solo tienen valor didáctico y rara vez se utilizan en la práctica debido a su baja eficiencia. La clasificación por combinación es un método de clasificación ampliamente utilizado.
La idea básica es que fusionar dos matrices ya ordenadas es más rápido que ordenar todos los elementos desde cero. Por lo tanto, la matriz se puede desmontar en n matrices con un solo elemento y luego fusionarlas continuamente de dos en dos hasta que se complete toda la clasificación.
Tomemos, por ejemplo, ordenar la matriz [3, 2, 4, 5, 1] de pequeña a grande. Los pasos son los siguientes:
Con la función de combinación, usted. Puede ordenar cualquier matriz. El método básico es dividir continuamente la matriz en dos mitades hasta que cada mitad contenga solo cero elementos o un elemento, y luego usar la función de combinación para fusionar continuamente las matrices divididas en dos mitades hasta que se fusionen en una matriz ordenada completa.
La clasificación rápida es reconocida como uno de los algoritmos de clasificación más rápidos y tiene una amplia gama de aplicaciones.
Pasos rápidos del algoritmo de clasificación
Referencia:
Resumen de los algoritmos de clasificación más utilizados (1)
Resumen del algoritmo de Ruan Yifeng