当前位置:网站首页>Tri des bulles et optimisation du tri des bulles

Tri des bulles et optimisation du tri des bulles

2022-01-15 02:41:24 Vers le Haut

La pensée

UnforBoucle à travers le tableau,Jeanarr[ i ]Etarr[ i+1 ]Comparaison,Siarr[ i ] > arr[ i+1 ]C'est un échange.,
Chaque tour de comparaison fait ressortir le plus grand nombre dans le tableau,Le premier tour est de trouver le plus grand

Insérer la description de l'image ici

Complexité temporelle O(n)2

public class BubbleDemo {
    

    public static void main(String[] args) {
    

        int[] arr = {
    8,4,2,1,23,344,12};

        //i Comparer le nombre de Tours
        for (int i = 0; i < arr.length-1; i++) {
    
            //j Nombre de fois
            for (int j = 0; j < arr.length-i-1 ; j++) {
    
                //Comparaison
                if(arr[j]>arr[j+1]){
    
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        
        //Produits
        for (int a : arr) {
    
            System.out.println(a);
        }
    }

}

Optimisation:

Optimisation des roues

  • La pensée: Parce que si vous arrivez à un certain tour, il n'y a pas d'échange. ( C'est - à - dire que le tableau complet n'est pas satisfait arr[ i ] > arr[ i+1 ] ), Indique que le tableau est ordonné , On peut s'arrêter et comparer. ,Prends - en un.boolean Le marquage est parfait.

Optimiser le nombre de comparaisons par cycle

  • La pensée: Si le tableau est spécial , C'est - à - dire que la partie postérieure du tableau est ordonnée , Ce programme produit de nombreuses comparaisons invalides , Pour une optimisation adaptée à ce cas particulier , Sur la base de l'ordre des bulles , Nous pouvons enregistrer l'endroit où l'échange a été généré pour la dernière fois au cours du dernier tour. , C'est - à - dire que nous avons trouvé xGrand( L'indice de données est enregistré comme suit: index), C'est un tour de recherche x-1Un grand nombre, On ne peut le trouver que dans la partie précédente. (0-index)
public class BubbleSort {
    
    public static void main(String[] args) {
    
        //int[] arr={16,49,23,56,4,11,12};
        int[] arr={
    2,19,18,16,20,21,62};
        int index=arr.length-1;
        for (int i = 0; i < arr.length-1; i++) {
    //Nombre de roues de commande
            boolean flag=true;// Utilisé pour enregistrer si un échange est généré , L'absence d'échange indique que les éléments sont ordonnés 
            int n=index; // Utilisé pour réduire chaque cycle de comparaison   Il y a une séquence ordonnée derrière.   Nombre de comparaisons répétées pour , Parce que le tri des bulles est le plus grand à la fois 
            for (int j = 0; j < n ; j++) {
    // Contrôler le nombre de Tours 
                if(arr[j]>arr[j+1]){
    
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    flag=false;
                    index=j;
                }
                System.out.println(Arrays.toString(arr));
                System.out.println(index);
            }
            System.out.println();
            if(flag) break;
        }

    }
}

版权声明
本文为[Vers le Haut]所创,转载请带上原文链接,感谢
https://chowdera.com/2022/01/202201080601056332.html

随机推荐