Principio: Compare dos elementos adyacentes e elementos de intercambio con grandes valores con el extremo derecho.
Idea: Compare dos números adyacentes en secuencia, coloque los decimales en el frente y los grandes números en la parte posterior. Es decir, en el primer viaje: primero compare los primeros y segundos números, coloque el decimal antes y los grandes números después. Luego compare el segundo número y el tercer número, coloque el decimal antes y después del gran número, continúe así hasta que se comparan los dos últimos números, coloque el decimal antes y después del gran número. Repita el primer paso hasta que se complete toda la clasificación.
Por ejemplo: para ordenar la matriz: int [] arr = {6,3,8,2,9,1};
Primer orden:
Primer tipo: 6 y 3 Compare, 6 es mayor que 3, Swap Posición: 368291
Segundo clasificación: 6 y 8 Compare, 6 es inferior a 8, no hay posición de intercambio: 368291
El tercer orden: 8 y 2 comparan, 8 es mayor que 2, Swap Posición: 362891
Cuarto pedido: 8 y 9 Compare, 8 es inferior a 9, sin intercambio de posición: 362891
Quinto Orden: 9 y 1 Compare: 9 es mayor que 1, Swap Posición: 362819
El primer viaje se comparó en total 5 veces, clasificando los resultados: 362819
---------------------------------------------------------------------
Segundo orden:
Primera clasificación: 3 y 6 Compare, 3 es inferior a 6, no hay posición de intercambio: 362819
Segundo clasificación: 6 y 2 Compare, 6 es mayor que 2, Posición de intercambio: 326819
El tercer pedido: 6 y 8 comparan, 6 es mayor que 8, no hay posición de intercambio: 326819
Cuarto orden: 8 y 1 comparar, 8 es mayor que 1, Swap Posición: 326189
El segundo viaje se comparó en total, y el resultado de la clasificación fue: 326189
---------------------------------------------------------------------
El tercer orden:
Primer tipo: 3 y 2 comparar, 3 es mayor que 2, Swap Posición: 236189
Segundo clasificación: 3 y 6 Compare, 3 es inferior a 6, no hay posición de intercambio: 236189
El tercer orden: 6 y 1 comparar, 6 es mayor que 1, Swap Posición: 231689
El segundo viaje se comparó en total, y el resultado de la clasificación fue: 231689
---------------------------------------------------------------------
El cuarto orden:
Primera clasificación: 2 y 3 Compare, 2 es inferior a 3, no hay posición de intercambio: 231689
Segundo clasificación: 3 y 1 compare, 3 es mayor que 1, Swap Posición: 213689
El segundo viaje se comparó en total, y el resultado de la clasificación fue: 213689
---------------------------------------------------------------------
El quinto orden:
Primer tipo: 2 y 1 comparar, 2 es mayor que 1, Swap Posición: 123689
El segundo viaje se comparó en total, y el resultado de la clasificación fue: 123689
---------------------------------------------------------------------
Resultado final: 123689
---------------------------------------------------------------------
A partir de esto, podemos ver que los números N deben clasificarse, y los tiempos N-1 se clasifican en total. El número de tiempos de clasificación para cada i-pass es (Ni), por lo que puede usar una instrucción de doble bucle para controlar cuántas veces la capa externa controlará el número de veces para cada viaje, es decir, es, es decir,
para (int i = 1; i <arr.length-1; i ++) {for (int j = 1; j <arr.length-1-i; j ++) {// Swap Posición}Ventajas de la clasificación de burbujas: cada vez que clasifique, comparará menos, porque cada vez que clasifique, encontrará un valor mayor. Como se mencionó anteriormente: después de la primera comparación, el último número debe ser el número más grande. Al clasificar la segunda vez, solo necesita comparar otros números que no sean el último número, y también puede encontrar que el número más grande se clasifica después del número que participa en la segunda comparación. Al comparar la tercera vez, solo necesita comparar otros números distintos de los dos últimos números, y así sucesivamente ... en otras palabras, si no realiza una comparación, cada vez que se compara una vez, lo que reduce la cantidad del algoritmo hasta cierto punto.
En términos de complejidad del tiempo:
1. Si nuestros datos están en orden, solo necesitamos hacer un viaje para completar la clasificación. El número requerido de comparaciones y movimientos de registro son el valor mínimo, es decir: cmin = n-1; mmin = 0; Por lo tanto, la mejor complejidad del tiempo para la clasificación de burbujas es O (N).
2. Si desafortunadamente nuestros datos son un orden inverso, se requiere el pedido de N-1. Cada orden debe compararse (1≤i≤n-1), y cada comparación debe moverse al registro tres veces para alcanzar la posición de registro de intercambio. En este caso, los tiempos de comparación y movimiento alcanzan el máximo: la peor complejidad de tiempo de la clasificación de burbujas es: O (N2).
En resumen: la complejidad total promedio de tiempo de burbuja es: O (N2).
Implementación del código:
/ * * Sort de burbujas */public class Bubblesort {public static void main (string [] args) {int [] arr = {6,3,8,2,9,1}; System.out.println ("La matriz antes de clasificar es:"); for (int num: arr) {system.out.print (num+""); } para (int i = 1; i <arr.length; i ++) {// El bucle externo controla el número de tiempos de clasificación para (int j = 1; j <arr.length-i; j ++) {// El bucle interno controla cuántas veces cada vez que se clasifica si (arr [j-1]> arr [j]) {int temp = arr [j]; arr [j] = arr [j-1]; arr [j-1] = temp; }}} System.out.println (); System.out.println ("La matriz ordenada es:"); for (int num: arr) {system.out.print (num+""); }}}