Principe: Comparez deux éléments adjacents et échangez des éléments avec de grandes valeurs à l'extrémité droite.
Idée: comparez deux nombres adjacents en séquence, placez les décimales devant et les grands nombres à l'arrière. Autrement dit, lors du premier voyage: comparez d'abord les premier et deuxième chiffres, mettez la décimale avant et les grands nombres après. Comparez ensuite le deuxième numéro et le troisième numéro, mettez la décimale avant et après le grand nombre, continuez comme ceci jusqu'à ce que les deux derniers numéros soient comparés, mettez la décimale avant et après le grand nombre. Répétez la première étape jusqu'à ce que tout le tri soit terminé.
Par exemple: trier le tableau: int [] arr = {6,3,8,2,9,1};
Première commande:
Premier tri: 6 et 3 comparer, 6 est supérieur à 3, position d'échange: 368291
Deuxième tri: 6 et 8 Comparez, 6 est inférieur à 8, pas de position d'échange: 368291
La troisième commande: 8 et 2 comparer, 8 est supérieure à 2, position d'échange: 362891
Quatrième commande: 8 et 9 comparer, 8 est inférieur à 9, pas de position d'échange: 362891
Cinquième ordre: 9 et 1 Comparez: 9 est supérieur à 1, Position d'échange: 362819
Le premier voyage a été comparé au total 5 fois, les résultats de tri: 362819
---------------------------------------------------------------------
Deuxième commande:
Premier tri: 3 et 6 comparer, 3 est inférieur à 6, pas de position d'échange: 362819
Deuxième tri: 6 et 2 comparer, 6 est supérieur à 2, position d'échange: 326819
La troisième commande: 6 et 8 comparer, 6 est supérieure à 8, pas de position d'échange: 326819
Quatrième ordre: 8 et 1 comparer, 8 est supérieur à 1, position d'échange: 326189
Le deuxième voyage a été comparé au total, et le résultat de tri était: 326189
---------------------------------------------------------------------
La troisième commande:
Premier tri: 3 et 2 comparer, 3 est supérieur à 2, position d'échange: 236189
Deuxième tri: 3 et 6 Comparez, 3 est inférieur à 6, pas de position d'échange: 236189
La troisième commande: 6 et 1 comparer, 6 est supérieure à 1, Position d'échange: 231689
Le deuxième voyage a été comparé au total, et le résultat de tri était: 231689
---------------------------------------------------------------------
La quatrième commande:
Premier tri: 2 et 3 comparer, 2 est inférieur à 3, pas de position d'échange: 231689
Deuxième tri: 3 et 1 comparer, 3 est supérieur à 1, position d'échange: 213689
Le deuxième voyage a été comparé au total, et le résultat de tri était: 213689
---------------------------------------------------------------------
La cinquième commande:
Premier tri: 2 et 1 comparer, 2 est supérieur à 1, position d'échange: 123689
Le deuxième voyage a été comparé au total, et le résultat de tri était: 123689
---------------------------------------------------------------------
Résultat final: 123689
---------------------------------------------------------------------
À partir de cela, nous pouvons voir que les nombres n doivent être triés et que les temps n-1 sont triés au total. Le nombre de temps de tri pour chaque PASS I est (ni), vous pouvez donc utiliser une instruction à double boucle pour contrôler le nombre de fois que la couche externe contrôlera le nombre de fois pour chaque voyage, c'est-à-dire,
pour (int i = 1; i <arr.length-1; i ++) {pour (int j = 1; j <arr.length-1-i; j ++) {// swap position}Avantages du tri des bulles: Chaque fois que vous triez, vous comparerez moins, car chaque fois que vous triez, vous trouverez une valeur plus grande. Comme mentionné ci-dessus: après la première comparaison, le dernier numéro doit être le plus grand nombre. Lors du tri de la deuxième fois, il vous suffit de comparer les autres nombres autres que le dernier numéro, et vous pouvez également constater que le plus grand nombre est classé après le nombre participant de la deuxième comparaison. Lorsque vous comparez la troisième fois, il vous suffit de comparer d'autres nombres autres que les deux derniers nombres, et ainsi de suite ... en d'autres termes, si vous n'effectuez pas de comparaison, chaque fois que vous comparez une fois, ce qui réduit la quantité de l'algorithme dans une certaine mesure.
En termes de complexité du temps:
1. Si nos données sont en ordre, nous n'avons qu'à faire un voyage pour terminer le tri. Le nombre requis de comparaisons et de mouvements enregistrés est à la fois la valeur minimale, c'est-à-dire: cmin = n-1; mmin = 0; Par conséquent, la meilleure complexité de temps pour le tri des bulles est O (n).
2. Si malheureusement, nos données sont une commande inverse, une commande N-1 est requise. Chaque ordre doit être comparé (1≤i≤n-1), et chaque comparaison doit être déplacée au record trois fois pour atteindre la position du record d'échange. Dans ce cas, les temps de comparaison et de mouvement atteignent tous deux le maximum: la pire complexité de temps du tri des bulles est: O (N2).
Pour résumer: la complexité du temps moyenne totale du tri des bulles est: O (N2).
Implémentation du code:
/ * * Bubble Sort * / public class Bubblesort {public static void main (String [] args) {int [] arr = {6,3,8,2,9,1}; System.out.println ("Le tableau avant le tri est:"); pour (int num: arr) {System.out.print (num + ""); } pour (int i = 1; i <arr.length; i ++) {// La boucle extérieure contrôle le nombre de temps de tri pour (int j = 1; j <arr.length-i; j ++) {// la boucle interne contrôle combien de fois [j]; arr [j] = arr [j-1]; arr [j-1] = temp; }}} System.out.println (); System.out.println ("Le tableau trié est:"); pour (int num: arr) {System.out.print (num + ""); }}}