Java implementa el algoritmo de clasificación de burbujas y ejemplos de optimización simples

principio

La clasificación de burbujas es probablemente un algoritmo que todos los programadores pueden usar y también es uno de los algoritmos más familiares.
Sus ideas no son complicadas:
Supongamos que la matriz arr [] está ordenada y tiene n elementos.
1. Si n = 1: obviamente, no hay necesidad de hacer cola. (De hecho, esta discusión parece ser innecesaria)
2. Si n> 1:
(1) Comenzamos con el primer elemento y comparamos cada dos elementos adyacentes. Si el elemento anterior es más grande que el siguiente, entonces el primero definitivamente se clasificará en el resultado final. Entonces, intercambiamos estos dos elementos. Luego compare los siguientes dos elementos adyacentes. De esta manera, hasta que se compare el último par de elementos, se completa la primera ronda de clasificación. Es cierto que el último elemento debe ser el más grande de la matriz (porque el relativamente grande se coloca en la parte posterior cada vez).
(2) Repita el proceso anterior, esta vez no necesitamos considerar el último porque ya está arreglado.
(3) Entonces, hasta que solo quede un elemento, el elemento debe ser el más pequeño, y luego nuestra clasificación puede terminar. Aparentemente, se realizó la clasificación N-1.
En el proceso anterior, cada vez (o "rueda" se clasifica, un número se "flotará lentamente desde una posición determinada hasta la posición final (dibuje un diagrama esquemático y dibuje la matriz verticalmente), al igual que las burbujas, por lo que se llama" método de clasificación de burbujas ".

Implementación del código:

 Public Class Bubblesort {public static void main (String [] args) {int store [] = {67, 69, 75, 87, 89, 90, 99, 100}; for (int i = 0; i <scatter.length -1; i ++) {// no solo realiza el orden de N -1 para (int j = 0; j <score.length -I -1; j ++) {// posterior int temp = sterter [j]; puntaje [j] = puntaje [j + 1]; puntaje [j + 1] = temp; }} System.out.print ("th" + (i + 1) + "Resultado de clasificación de secuencia:"); for (int a = 0; a <scatter.length; a ++) {system.out.print (score [a]+"/t"); } System.out.println (""); } System.out.print ("Resultado de clasificación final:"); for (int a = 0; a <scatter.length; a ++) {system.out.print (score [a]+"/t"); }}}

Rendimiento del algoritmo/complejidad
Ignoramos el tiempo en que las variables de bucle aumentan e inicializan automáticamente. Primero analice el número de comparaciones del algoritmo. Es fácil ver que la clasificación de burbujas anterior sin ninguna mejora se realizará en rondas N-1, independientemente de los datos de entrada, y el número de veces que cada ronda de clasificación debe compararse disminuye de N-1 a 0. Entonces, el número total de comparaciones es (N-1)+(N-2)+...+2+1 = (N-1) N/2iones (N^2)/2. (Como no sé cómo hacer cuadrados aquí, aquí, uso n^2 para representar cuadrados, lo mismo a continuación)
Echemos un vistazo a la cantidad de tareas. La tarea aquí se refiere a la operación de intercambio. Para el código anterior, 1 intercambio es igual a tres tareas. Como no cada vez que es necesario intercambiar, el número de operaciones de asignación está relacionado con los datos de entrada. En el mejor de los casos, es decir, cuando el pedido está al principio, el número de tareas es 0. En el peor de los casos, el número de tareas es (N-1) N/2. Suponiendo que los datos de entrada son la distribución promedio (o "completamente aleatoria"), entonces aproximadamente la mitad del número de intercambios. De los resultados anteriores, podemos obtener el caso promedio, con el número de tareas 3/2 * (n^2)/2 = 3/4 * (n^2).
En resumen, en cualquier caso, la complejidad del espacio de clasificación de burbujas (espacio adicional) es siempre o (1).

mejorar
La complejidad del tiempo óptima se muestra cuando los datos están completamente ordenados, que son o (n). En otros casos, casi siempre es o (n^2). Por lo tanto, el algoritmo funciona mejor cuando los datos se ordenan básicamente.
Sin embargo, ¿cómo puede el código anterior tener o (n) complejidad? De hecho, debido a que lo anterior se centra en las ideas básicas, es solo el caso más simple. Para hacer que el algoritmo tenga una complejidad o (n) en el mejor de los casos, se deben realizar algunas mejoras. El código mejorado es:

 public static void bubblesort (int [] arr) {int temp = 0; intercambio booleano; para (int i = arr.length -1; i> 0; --i) {// La longitud de cada tipo debe ser intercambiar = falso; for (int j = 0; j <i; ++ j) {// Desde el primer elemento al elemento i-th if (arr [j]> arr [j +1]) {temp = arr [j]; arr [j] = arr [j + 1]; arr [j + 1] = temp; swap = true; }} // loop j if (swap == false) {break; }} // bucle i} // método bubblesort

De hecho, debido a que la clasificación de burbujas apenas se usa en el caso de grandes cantidades de datos, las variables booleanas agregadas cuando se usan datos pequeños realmente causarán sobrecargas adicionales. Así que personalmente creo que el algoritmo mejorado anterior es solo puramente teórico. Por lo general, solo escriba el anterior burbujeando.

Estabilidad del algoritmo
Es fácil ver que cuando los elementos vecinos son iguales, no necesitamos intercambiar sus posiciones, por lo que la clasificación de burbujas es un tipo estable.

Algoritmo escenarios aplicables
La idea de la clasificación de burbujas es simple y el código es simple, que es especialmente adecuado para clasificar pequeños datos. Sin embargo, debido a la alta complejidad del algoritmo, no es adecuado para su uso cuando el volumen de datos es grande. Si debe usarlo cuando hay más datos, es mejor mejorar el algoritmo, como seleccionar el método de clasificación.