Implémentation Java de l'algorithme de tri à bulles et son exemple d'optimisation simple

Principe

Le tri à bulles est probablement un algorithme que tous les programmeurs utiliseront, et c'est aussi l'un des algorithmes les plus connus.
L'idée n'est pas compliquée :
Supposons maintenant que nous voulions trier le tableau arr[], qui comporte n éléments.
1. Si n=1 : Il n'y a évidemment pas besoin de s'arranger. (En fait, cette discussion semble inutile)
2. Si n>1 :
(1) On part du premier élément et on compare tous les deux éléments adjacents si l'élément précédent est meilleur que l'élément suivant Big, alors. le premier sera définitivement classé derrière dans le résultat final. Nous échangeons donc ces deux éléments. Comparez ensuite les deux éléments adjacents suivants. Cela continue jusqu'à ce que la dernière paire d'éléments soit comparée et que le premier cycle de tri soit terminé. Vous pouvez être sûr que le dernier élément doit être le plus grand du tableau (car les plus grands sont placés à chaque fois à l'arrière).
(2) Répétez le processus ci-dessus, cette fois nous n'avons pas besoin de considérer le dernier car il est déjà aligné.
(3) Ceci est fait jusqu'à ce qu'il ne reste qu'un seul élément. Cet élément doit être le plus petit, puis notre tri peut être complété. Bien évidemment, un tri n-1 a lieu.
Dans le processus ci-dessus, à chaque tri (ou appelé "rond"), un nombre "flottera" lentement d'une certaine position à la position finale (dessinez un diagramme schématique et dessinez le tableau verticalement pour le voir) ), tout comme la bulle, on l'appelle donc "tri à bulles".

Implémentation du code :

public class BubbleSort{
   public static void main(String[] args){
     int score[] = {67, 69, 75, 87, 89, 90, 99, 100};
     for (int i = 0; i < score.length -1; i++){  //最多做n-1趟排序
       for(int j = 0 ;j < score.length - i - 1; j++){  //对当前无序区间score[0......length-i-1]进行排序(j的范围很关键，这个范围实在逐步缩小的)
         if(score[j] < score[j + 1]){  //把小的值交换到后面
           int temp = score[j];
           score[j] = score[j + 1];
           score[j + 1] = temp;
         }
       }      
       System.out.print("第" + (i + 1) + "次排序结果：");
       for(int a = 0; a < score.length; a++){
         System.out.print(score[a] + "\t");
       }
       System.out.println("");
     }
       System.out.print("最终排序结果：");
       for(int a = 0; a < score.length; a++){
         System.out.print(score[a] + "\t");
     }
   }
 }

Performances/complexité de l'algorithme
Nous ignorons le temps d'incrémentation et d'initialisation des variables de boucle. Analysez d’abord le nombre de comparaisons de l’algorithme. Il est facile de voir que le tri à bulles ci-dessus, sans aucune amélioration, effectuera n-1 tours de tri quelles que soient les données d'entrée, et le nombre de comparaisons requises pour chaque tour de tri diminue de n-1 à 0. Ensuite, le nombre total de comparaisons est (n-1) (n-2) ... 2 1 = (n-1)n/2≈(n^2)/2. (Comme je ne sais pas comment calculer le carré ici, ici, j'utilise n^2 pour représenter le carré, pareil ci-dessous)
Regardons le nombre d'affectations. L'affectation fait ici référence à l'opération d'échange. Pour le code ci-dessus, un échange équivaut à trois affectations. Comme l'échange n'est pas nécessaire à chaque fois, le nombre d'opérations d'affectation est lié aux données d'entrée. Dans le meilleur des cas, c'est-à-dire lorsqu'il est ordonné depuis le début, le nombre d'affectations est 0. Dans le pire des cas, le nombre d'affectations est (n-1)n/2. En supposant que les données d'entrée sont distribuées uniformément (ou "complètement aléatoires"), il y a alors environ la moitié du nombre d'échanges par rapport au nombre de comparaisons. D'après les résultats ci-dessus, nous pouvons déduire que dans le cas moyen, le nombre d'affectations est de 3/2 * (n^2)/2 = 3/4*(n^2).
Pour résumer, peu importe quel genre de Dans ce cas, la complexité spatiale (espace supplémentaire) du tri à bulles est toujours O(1).

Amélioration
montre la complexité temporelle optimale, qui est O(n) lorsque les données sont complètement ordonnées. Sinon, c'est presque toujours O(n^2). Par conséquent, l’algorithme fonctionne mieux lorsque les données sont essentiellement ordonnées.
Cependant, comment le code ci-dessus peut-il avoir une complexité O(n) ? En fait, comme ce qui précède se concentre sur l'idée de base, il ne s'agit que du cas le plus simple. Pour que l'algorithme ait une complexité O(n) dans le meilleur des cas, certaines améliorations doivent être apportées. Le code amélioré est :

<.>

public static void bubbleSort(int[] arr) {
  int temp = 0;
  boolean swap;
  for (int i = arr.length - 1; i > 0; --i) { // 每次需要排序的长度
    swap=false;
    for (int j = 0; j < i; ++j) { // 从第一个元素到第i个元素
      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;
    }
  }//loop i
}// method bubbleSort

En fait, étant donné que le tri à bulles n'est presque jamais utilisé lors de l'utilisation de grandes quantités de données, l'ajout de variables booléennes lors de l'utilisation de petites données entraînera une surcharge supplémentaire. Par conséquent, je pense personnellement que l’algorithme amélioré ci-dessus est purement théorique. Habituellement, pour le tri des bulles, écrivez simplement le premier.

Stabilité de l'algorithme

Il est facile de voir que lorsque les éléments adjacents sont égaux, nous n'avons pas besoin d'échanger leurs positions, le tri à bulles est donc un tri stable.

Scénarios applicables pour l'algorithme

Le tri à bulles a une idée simple et un code simple, particulièrement adapté au tri de petites données. Cependant, en raison de la grande complexité de l’algorithme, il ne convient pas à une utilisation lorsque la quantité de données est importante. S'il doit être utilisé lorsqu'il y a beaucoup de données, il est préférable d'améliorer l'algorithme, comme le tri par sélection.

Pour plus d'implémentation Java de l'algorithme de tri à bulles et ses exemples d'optimisation simples, veuillez faire attention au site Web PHP chinois !