Apprenez les méthodes d'écriture et d'analyse courantes du tri des bulles Java

Maîtriser rapidement le tri à bulles Java : analyse de plusieurs méthodes d'écriture courantes

En informatique, le tri à bulles est un algorithme de tri simple mais inefficace. Son idée de base est de « faire bouillonner » progressivement des éléments plus gros jusqu'à la fin du tableau en comparant et en échangeant plusieurs fois les éléments adjacents.

Dans cet article, nous présenterons plusieurs méthodes courantes de tri de bulles Java et donnerons des exemples de code spécifiques pour aider les lecteurs à maîtriser rapidement cet algorithme de tri.

1. La manière de base d'écrire le tri à bulles

La manière de base d'écrire le tri à bulles est très simple. Elle échange les éléments adjacents via des boucles imbriquées, comparant ainsi les éléments du tableau un par un, et "Bubbling" jusqu'à la fin. .

Ce qui suit est un exemple de code Java d'écriture de base :

public void bubbleSort(int[] array) {
    int n = array.length;
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (array[j] > array[j+1]) {
                // 交换相邻的元素
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
}

2. Écriture optimisée du tri à bulles

Bien que le tri à bulles soit simple, son efficacité sera très faible lors du traitement de données à grande échelle. Afin d’améliorer l’efficacité du tri, nous pouvons ajouter quelques mesures d’optimisation.

Une méthode d'optimisation courante consiste à définir un bit d'indicateur. Si aucun échange ne se produit dans une certaine boucle, c'est-à-dire que le tableau est déjà en ordre, quittez la boucle plus tôt.

Ce qui suit est un exemple de code Java d'écriture optimisée :

public void optimizedBubbleSort(int[] array) {
    int n = array.length;
    boolean swapped;
    for (int i = 0; i < n-1; i++) {
        swapped = false;
        for (int j = 0; j < n-i-1; j++) {
            if (array[j] > array[j+1]) {
                // 交换相邻的元素
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
                swapped = true;
            }
        }
        if (swapped == false)
            break;
    }
}

3. Écriture optimisée du tri à bulles (réduisant encore le nombre de comparaisons)

Dans l'écriture optimisée, nous pouvons réduire davantage le nombre de comparaisons. Étant donné que chaque cycle d'opération de bouillonnement fera "faire bouillonner" le plus grand élément de la zone non ordonnée jusqu'à la fin de la zone non ordonnée, la longueur de la zone non ordonnée au cycle suivant est réduite de 1.

Sur la base de cette observation, nous pouvons enregistrer la dernière position d'échange lastSwapIndex dans la boucle interne. Étant donné que les éléments situés après cette position sont déjà en ordre, aucune comparaison n'est nécessaire.

Voici des exemples de code Java encore optimisés :

public void furtherOptimizedBubbleSort(int[] array) {
    int n = array.length;
    int lastSwapIndex;

    for (int i = 0; i < n-1; i++) {
        lastSwapIndex = 0;

        for (int j = 0; j < n-1-i; j++) {
            if (array[j] > array[j+1]) {
                // 交换相邻的元素
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
                lastSwapIndex = j+1;
            }
        }

        if (lastSwapIndex == 0)
            break;

        n = lastSwapIndex;
    }
}

Résumé :

Cet article présente les méthodes d'écriture courantes pour maîtriser rapidement le tri des bulles Java et donne des exemples de code spécifiques. Grâce à la compréhension et à la pratique de ces méthodes d’écriture, chacun peut mieux maîtriser et utiliser cet algorithme de tri classique. Bien entendu, l'efficacité du tri à bulles est relativement faible. Pour trier des données à grande échelle, il est recommandé de choisir un algorithme de tri plus efficace, tel qu'un tri rapide ou un tri par fusion.

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!