¿Qué es la clasificación por burbujas?
La clasificación de burbujas se refiere a un método de clasificación por computadora. Su complejidad temporal es O (n ^ 2), aunque no es tan buena como O (nlogn, base 2) de clasificación en montón y clasificación rápida. Hay dos ventajas: 1. La "complejidad de programación" es muy baja y es fácil escribir el código. 2. Tiene estabilidad. La estabilidad aquí significa que el orden relativo de los mismos elementos en la secuencia original aún se mantiene en la secuencia. secuencia ordenada. Ni la clasificación en montón ni la clasificación rápida son estables. Sin embargo, la clasificación por fusión unidireccional y bidireccional y la clasificación de árbol binario desequilibrado son más rápidas y estables que la clasificación de burbujas, pero no tan rápidas como la clasificación de montón y la clasificación rápida. La clasificación de burbujas se completa mediante n-1 subclasificaciones. La i-ésima subclasificación es desde el primer número hasta el n-i-ésimo número si el i-ésimo número es mayor que el siguiente número (en orden ascendente, si es menor). , en orden descendente), intercambiar dos números
El concepto básico de clasificación de burbujas (BubbleSort) es comparar dos números adyacentes en secuencia, poniendo el decimal delante y el número grande detrás. Es decir, en la primera pasada: primero compara el primer y segundo número, pon el decimal primero y el número grande al final. Luego compara el segundo número y el tercer número, pon el decimal delante y el número grande detrás, y continúa así hasta comparar los dos últimos números, pon el decimal delante y el número grande detrás. Este es el final del primer viaje, dejando el número mayor al final. En el segundo paso: aún comience la comparación desde el primer par de números (porque puede deberse al intercambio del segundo número y el tercer número que el primer número ya no sea menor que el segundo número), coloque el decimal primero , y el número grande Después de colocarlo, se continúa la comparación hasta el penúltimo número (la primera a la última posición ya es la más grande. Al final de la segunda pasada, se obtiene un nuevo número máximo en el penúltimo). posición (de hecho, es el número más grande de toda la secuencia). Continúe así y repita el proceso anterior hasta que finalmente se complete la clasificación. Debido a que en el proceso de clasificación, los números pequeños siempre se colocan hacia adelante y los números grandes hacia atrás, lo que equivale a que las burbujas suban, por eso se llama clasificación de burbujas. Implementado con un bucle doble, la variable del bucle externo se establece en i y la variable del bucle interno se establece en j. El bucle exterior se repite 9 veces y el bucle interior se repite 9, 8,..., 1 vez. Los dos elementos comparados cada vez están relacionados con el bucle interno j. Se pueden identificar mediante a[j] y a[j 1] respectivamente. Los valores de i son 1, 2,..., 9. Para cada uno Los valores de an i y j son 1, 2,...10-i.
Generar
En muchos programas, necesitamos ordenar una secuencia para facilitar las estadísticas, y la clasificación por burbujas siempre ha sido popular debido a su método de pensamiento conciso.
Proceso de clasificación
Imagínese que la matriz ordenada R[1..N] se erige verticalmente y cada elemento de datos se considera como una burbuja ponderada. Según la burbuja de luz, no se puede. en la burbuja pesada De acuerdo con el principio siguiente, la matriz R se escanea de abajo hacia arriba. Cada vez que se escanea una burbuja ligera que viola este principio, se la hace "flotar" hacia arriba. Esto se repite hasta que las dos últimas burbujas sean las siguientes. uno más ligero arriba y el más pesado Hasta la próxima.