Exemple simple d'analyse du tri à bulles en Java

Cet article présente principalement en détail des exemples simples de tri de bulles Java, qui ont une certaine valeur de référence. Les amis intéressés peuvent s'y référer

Principe de l'algorithme

Comparez. éléments adjacents. Si le premier est plus grand que le second, échangez-les tous les deux.

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. À ce stade, le dernier élément doit être le plus grand nombre.

Répétez les étapes ci-dessus pour tous les éléments sauf le dernier.

Continuez à répéter les étapes ci-dessus pour de moins en moins d'éléments à chaque fois jusqu'à ce qu'il n'y ait plus de paires de nombres à comparer.

2. Idées d'implémentation

Utilisez une double boucle pour implémenter, avec la variable de boucle externe définie sur i et la variable de boucle interne définie sur j. S'il y a n nombres à trier, la boucle externe est répétée n-1 fois et la boucle interne est répétée n-1, n-2,..., 1 fois. Les deux éléments comparés à chaque fois sont liés à la boucle interne j. Ils peuvent être identifiés respectivement par a[j] et a[j+1]. Les valeurs de i sont 1, 2,..., n-1. . , pour chaque i, la valeur de j est 0,1,2,...n-i.

Supposons que la longueur du tableau soit N :

1. Comparez les deux données adjacentes avant et après. Si les premières données sont supérieures aux dernières données, les deux données seront échangées.
2． De cette façon, après avoir parcouru les 0èmes données jusqu'aux N-1èmes données du tableau, les données les plus volumineuses « couleront » vers la N-1ème position du tableau.
3. N=N-1, si N est différent de 0, répétez les deux étapes précédentes, sinon le tri est terminé.

3. Implémentation du code

package sort;
import java.util.Arrays;
/**
 * 冒泡排序
 * 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
 * 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
 * 针对所有的元素重复以上的步骤，除了最后一个。
 * 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
 */

public class BubbleSort {
  public static void bubbleSort(int[] arr) {
    boolean flag=true;
    while (flag) {
      flag=false;
      int temp = 0;
      for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
          if (arr[j] > arr[j + 1]) {   //交换两数位置
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
            flag=true;
          }
        }
        if (!flag){
          break;
        }
        }
      }
    }
  public static void main(String[] args){
    int a[]=new int[]{345,22,43,12,65,335,124,636,3};
    BubbleSort.bubbleSort(a);
    System.out.print(Arrays.toString(a));
  }
}

4. Analyse des performances

Si l'état initial de la séquence d'enregistrements est « ordre positif », le processus de tri à bulles n'a besoin d'effectuer qu'un seul tri, et seules n-1 comparaisons sont requises pendant le processus de tri, et les enregistrements ne sont pas déplacés à l'inverse, si l'état initial ; état de la séquence d'enregistrement Pour "l'ordre inverse", n (n-1)/2 comparaisons et déplacements d'enregistrement sont nécessaires. Par conséquent, la complexité temporelle totale du tri à bulles est O(n*n).

5. Optimisation de l'algorithme

Inconvénients et méthodes d'amélioration de la méthode de tri des bulles :

D'abord, pendant le processus de tri, après avoir exécuté le dernier Après tri, bien que les données aient été complètement triées, le programme ne peut pas déterminer si le tri est terminé. Afin de résoudre ce problème, un indicateur peut être défini et sa valeur initiale est définie sur true, indiquant que la table triée est une table non ordonnée. ., définissez la valeur de l'indicateur sur true avant le début de chaque tri et modifiez l'indicateur sur false pendant l'échange de données. Au début d'un nouveau tour de tri, vérifiez ce flag. Si ce flag est faux, cela signifie qu'aucune donnée n'a été échangée la dernière fois, alors le tri se terminera sinon, le tri sera effectué

; Deuxièmement, dans le tri à bulles, il peut y avoir aucun échange de données en une seule analyse, ou il peut y avoir un ou plusieurs échanges de données. Dans l'algorithme de tri à bulles traditionnel et dans certains algorithmes améliorés ces dernières années, seules les informations indiquant s'il y a un échange de données. une analyse est enregistrée et les données sont Les informations de localisation où l'échange a lieu ne sont pas traitées. Afin d'utiliser pleinement ces informations, un tri local à bulles peut être effectué sur chaque paire de données en ordre inverse dans le cadre d'une analyse globale, appelée tri local à bulles. Le tri à bulles local a la même complexité temporelle que l'algorithme de tri à bulles, et le nombre de comparaisons et de déplacements des mots-clés requis est exactement le même dans l'ordre direct et inverse. Étant donné que le nombre de mouvements de données entre le tri à bulles local et le tri à bulles est toujours le même et que le nombre de comparaisons de mots-clés requis par le tri à bulles local est souvent inférieur à celui du tri à bulles local, cela signifie que le tri à bulles local est susceptible d'avoir un le nombre moyen de comparaisons est inférieur. Le tri à bulles a été amélioré. Lorsque l'avantage du nombre réduit de comparaisons n'est pas suffisant pour compenser la surcharge supplémentaire causée par la complexité du programme, et lorsque la quantité de données est importante, les performances temporelles du tri à bulles local sont réduites. nettement meilleur que celui du tri à bulles. Pour N données non ordonnées, lorsque nous effectuons un tri à bulles, si les k-èmes données et les k+1-èmes données sont dans l'ordre inverse, alors un tri à bulles vers l'avant est effectué sur les k+1-èmes données, de sorte que Move à la position appropriée, c'est-à-dire ajuster les données k+1 précédentes à la séquence positive. Parce que cette méthode de bouillonnement ne fait bouillonner que les premières données k+1, nous l'appelons - bouillonnement local

package sort;

import java.util.Arrays;

public class BubbleSort {
  public static void bubbleSort(int[] arr) {
    boolean flag=true;
    while (flag) {
      flag=false;
      int temp = 0;
      for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
          if (arr[j] > arr[j + 1]) {   //交换两数位置
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
            flag=true;
          }
        }
        if (!flag){
          break;
        }
        }
      }
    }
  public static void main(String[] args){
    int a[]=new int[]{345,22,43,12,65,335,124,636,3};
    BubbleSort.bubbleSort(a);
    System.out.print(Arrays.toString(a));
  }
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!