Algoritmo de clasificación basado en comparación
Algoritmos de clasificación basados en comparación: clasificación por burbujas, clasificación por selección, clasificación por inserción, clasificación Hill, clasificación por fusión, clasificación rápida.
1. Clasificación de burbujas
La clasificación de burbujas es un algoritmo de clasificación simple que atraviesa repetidamente los elementos que se van a ordenar y compara dos elementos adyacentes. Si el orden es incorrecto, intercámbielos. posiciones. Este proceso se repite hasta que no queden más elementos para intercambiar. La complejidad temporal de la clasificación de burbujas es O (n ^ 2), donde n es el número de elementos que se ordenarán.
2. Clasificación por selección
El principio de clasificación por selección es encontrar primero el elemento más pequeño (grande) entre los elementos no clasificados e intercambiar su posición con el primer elemento. Luego, busque el elemento más pequeño (más grande) de los elementos restantes sin clasificar e intercambie su posición con el segundo elemento. Este proceso se repite hasta que todos los elementos estén ordenados. La complejidad temporal de la clasificación por selección es O (n ^ 2).
3. Ordenación por inserción
El principio de ordenación por inserción es comenzar desde el primer elemento, que se puede considerar ordenado. Saque el siguiente elemento, escanee de atrás hacia adelante en la secuencia de elementos ordenados, busque la posición correspondiente e insértelo. Este proceso se repite hasta que todos los elementos estén ordenados. La complejidad temporal de la ordenación por inserción es O (n ^ 2).
4. Clasificación en colina
La clasificación en colina también se denomina clasificación incremental descendente, que es una mejora con respecto a la clasificación por inserción. Primero agrupa los elementos que se ordenarán en ciertos intervalos y realiza la clasificación por inserción en cada grupo de elementos. Luego, reduzca gradualmente el intervalo hasta que sea 1 y se convierta en un tipo de inserción normal. La complejidad temporal de la clasificación Hill es O (n log n).
5. Ordenación por combinación
La ordenación por combinación es un algoritmo de divide y vencerás. Divide los elementos que se van a ordenar en dos subgrupos a la vez y ordena cada subgrupo hasta el subgrupo. El número de elementos es 1. Luego combine los subgrupos ordenados en una matriz ordenada. La complejidad temporal de la ordenación por fusión es O (n log n).
6. Ordenación rápida
La ordenación rápida también es un algoritmo de divide y vencerás. Selecciona un elemento de referencia y divide los elementos que se van a ordenar en subarreglos que son más pequeños que el punto de referencia. elemento y aquellos que son mayores o iguales que el punto de referencia. Un subconjunto de elementos. Luego, los dos subarreglos se ordenan rápidamente de forma recursiva. La complejidad temporal de la clasificación rápida es O (n log n).