Bubble Sort est l’un des algorithmes de tri les plus simples en programmation. Il parcourt à plusieurs reprises la séquence à trier, en comparant deux éléments à la fois et en les échangeant s'ils sont dans le mauvais ordre. Répétez le travail de visite du tableau jusqu'à ce qu'il n'y ait plus d'éléments à échanger, ce qui signifie que le tableau a été trié.
Le tri à bulles est comme des bulles émergeant de l'eau, dans le tri à bulles, le nombre le plus petit ou le plus grand, selon que nous trions le tableau par ordre croissant ou décroissant, les bulles apparaissent vers le début ou la fin du tableau.
1) Comparez les éléments adjacents si le premier est plus grand que le second, échangez-les deux.
2) Faites de même pour chaque paire d’éléments adjacents, en commençant par la première paire et en terminant par la dernière paire, auquel cas le dernier élément doit être le plus grand nombre.
3) Répétez les étapes ci-dessus pour tous les éléments sauf le dernier.
4) Continuez à répéter les étapes ci-dessus pour de moins en moins d’éléments jusqu’à ce qu’il n’y ait plus de paires de nombres à comparer.
Le tri à bulles fonctionne mal par rapport à d’autres algorithmes de tri tels que le tri rapide, le tri par fusion ou le tri shell. La complexité moyenne des cas de ces algorithmes est O(nlogn), tandis que la complexité moyenne des cas du tri à bulles est O(n^2).
Dans le meilleur des cas, le tri à bulles est meilleur que le tri rapide avec des performances O(n). Le tri à bulles est trois fois plus lent que le tri rapide ou le tri par fusion, même avec n=100, mais il est plus facile à mettre en œuvre et à mémoriser.
La complexité et les performances du tri à bulles sont les suivantes :
1) Dans le pire des cas, les performances du tri à bulles sont O(n^2)
2) La meilleure performance du tri à bulles est O(n)
3) La performance moyenne du tri à bulles est O(n^2)
//Tri des bulles publicstaticvoidbubbleSort(int[]arr){//La boucle externe est utilisée pour contrôler le nombre de tours de la boucle du tableau for(inti=0;i<arr.length-1;i++){//La boucle interne La boucle est utilisée pour compléter la comparaison des valeurs d'élément et échanger les valeurs d'élément plus grandes vers l'arrière for(intj=0;j<arr.length-1-i;j++){if(arr[j]>arr [j+1]){inttemp= arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}}}//Résultat de sortie pour(intn:nums){Système .out.println(n);} }Par exemple:
publicclassMain{publicstaticvoidmain(String[]args){inta[]={6,1,15,32,9};for(inti=1;i<a.length;i++){for(intj=0;j<a .length-1;j++){if(a[j]>a[j+1]){inttemp=a[j];a[j]=a[j+1];a[j+1]=temp ;}}}System.out.println(Le résultat du tri des bulles est :);for(inttemp:a){System.out.print(temp+);}}}Les résultats en cours d'exécution sont les suivants :
Le résultat du tri à bulles est : 1691532
Vous pouvez l'essayer vous-même !