Quelques algorithmes de tri à bulles Java courants : trier par ordre croissant

Tri des bulles Java : plusieurs méthodes d'écriture courantes, du plus petit au plus grand, des exemples de code spécifiques sont nécessaires

Le tri des bulles est un algorithme de tri simple qui compare à plusieurs reprises deux éléments adjacents et les trie en fonction de leur taille. Les échanges sont effectués jusqu'à ce que la séquence entière soit terminée. est en ordre. En Java, il existe plusieurs méthodes d'écriture et méthodes d'optimisation courantes pour le tri des bulles. Ce qui suit présente cinq des méthodes d'écriture courantes et fournit des exemples de code spécifiques.

La première façon d'écrire : le tri à bulles ordinaire

Le tri à bulles ordinaire imbrique directement deux niveaux de boucles. La boucle externe contrôle le nombre de tours de comparaison, et la boucle interne effectue des comparaisons et des échanges spécifiques.

public static void bubbleSort1(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

La deuxième façon d'écrire : optimiser la boucle externe

Basé sur la première façon d'écrire, si aucun échange n'est effectué lors d'un tour de tri, cela signifie que le tableau est déjà en ordre et que le tri peut être terminé plus tôt . Pour réaliser cette optimisation, nous pouvons ajouter un bit d'indicateur pour enregistrer si un échange a été effectué.

public static void bubbleSort2(int[] arr) {
    int n = arr.length;
    boolean swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

La troisième façon d'écrire : optimiser la boucle interne

Sur la base de la deuxième façon d'écrire, vous pouvez constater que chaque tour de comparaison fera « bouillonner » le plus grand élément jusqu'à la fin. Par conséquent, le nombre de comparaisons de boucles internes par tour peut être progressivement réduit.

public static void bubbleSort3(int[] arr) {
    int n = arr.length;
    int lastSwapIndex;
    for (int i = 0; i < n - 1; i++) {
        lastSwapIndex = 0;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                lastSwapIndex = j + 1;
            }
        }
        i = n - lastSwapIndex - 2;
    }
}

La quatrième façon d'écrire : optimiser les boucles internes et externes

Basé sur la troisième façon d'écrire, si le tableau n'échange pas dans un certain tour de comparaison, cela signifie que les éléments derrière le tableau sont déjà dans l'ordre , et le tri peut être terminé plus tôt.

public static void bubbleSort4(int[] arr) {
    int n = arr.length;
    int lastSwapIndex, rightBoundary;
    rightBoundary = n - 1;
    for (int i = 0; i < n - 1; i++) {
        lastSwapIndex = 0;
        for (int j = 0; j < rightBoundary; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                lastSwapIndex = j + 1;
            }
        }
        rightBoundary = lastSwapIndex;
        if (rightBoundary <= 1) {
            break;
        }
    }
}

La cinquième façon d'écrire : optimiser la boucle externe et la boucle interne

Basé sur la quatrième façon d'écrire, nous pouvons constater que chaque tour de comparaison trouvera le plus grand élément du tour en cours et le mettra dans le bon sens position . Par conséquent, nous pouvons trouver à la fois les valeurs maximales et minimales à chaque tour de comparaison et les trier.

public static void bubbleSort5(int[] arr) {
    int n = arr.length;
    int lastSwapIndex, leftBoundary, rightBoundary;
    leftBoundary = 0;
    rightBoundary = n - 1;
    while (leftBoundary < rightBoundary) {
        lastSwapIndex = 0;
        for (int j = leftBoundary; j < rightBoundary; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                lastSwapIndex = j + 1;
            }
        }
        rightBoundary = lastSwapIndex;
        for (int j = rightBoundary; j > leftBoundary; j--) {
            if (arr[j] < arr[j-1]) {
                int temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
                lastSwapIndex = j - 1;
            }
        }
        leftBoundary = lastSwapIndex;
    }
}

Ci-dessus sont les cinq méthodes d'écriture courantes de tri à bulles. Chaque méthode d'écriture a différentes méthodes d'optimisation. En utilisation réelle, vous pouvez choisir la méthode d'écriture appropriée en fonction de la situation spécifique. Grâce à ces optimisations, l’efficacité du tri des bulles peut être améliorée et le temps de tri peut être réduit.

Bien que le tri à bulles soit simple, ses performances sont médiocres lors du tri de données à grande échelle. Par conséquent, dans les applications pratiques, des algorithmes de tri plus efficaces, tels que le tri rapide, le tri par fusion, etc., sont plus couramment utilisés.

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!