Red de conocimiento informático - Material del sitio web - Algoritmo de clasificación basado en comparación

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).