Maison  >  Article  >  Java  >  Plusieurs façons courantes d'écrire un tri à bulles en Java

Plusieurs façons courantes d'écrire un tri à bulles en Java

小老鼠
小老鼠original
2024-01-04 16:39:211000parcourir

Méthodes d'écriture courantes : 1. Tri à bulles de base ; 2. Tri à bulles amélioré : étant donné que chaque boucle externe déplacera le plus grand nombre vers la bonne position, le nombre de boucles internes peut être réduit, améliorant ainsi l'efficacité 3. Combinaison d'insertion ; tri et tri à bulles : Cette méthode d'écriture s'appuie sur l'idée du tri par insertion, en avançant progressivement les éléments triés, afin que les éléments non triés soient progressivement ordonnés. Cette méthode est appelée « séquençage de cocktails ».

Plusieurs façons courantes d'écrire un tri à bulles en Java

Le système d'exploitation de ce tutoriel : système Windows 10, ordinateur Dell G3.

Le tri à bulles est un algorithme de tri simple qui parcourt à plusieurs reprises le tableau à trier, compare deux éléments à la fois et les échange s'ils sont dans le mauvais ordre. Le travail de parcours du tableau est répété jusqu'à ce qu'aucun échange ne soit plus nécessaire, ce qui signifie que le tableau a été trié.

Voici plusieurs implémentations Java courantes du tri à bulles :

1 Tri à bulles de base :

java

public static void bubbleSort(int[] arr) {  
    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]) {  
                // swap arr[j+1] and arr[j]  
                int temp = arr[j];  
                arr[j] = arr[j + 1];  
                arr[j + 1] = temp;  
            }  
        }  
    }  
}

2. la position correcte, de sorte que le nombre de boucles internes peut être réduit, améliorant ainsi l'efficacité.

java

public static void bubbleSort(int[] arr) {  
    for (int i = 0; i < arr.length - 1; i++) {  
        boolean swapped = false;  
        for (int j = 0; j < arr.length - 1 - i; j++) {  
            if (arr[j] > arr[j + 1]) {  
                // swap arr[j+1] and arr[j]  
                int temp = arr[j];  
                arr[j] = arr[j + 1];  
                arr[j + 1] = temp;  
                swapped = true;  
            }  
        }  
        // If no two elements were swapped by inner loop, then the array is sorted  
        if (!swapped) break;  
    }  
}

3. Combinaison du tri par insertion et du tri à bulles : Cette méthode d'écriture s'inspire de l'idée du tri par insertion, en avançant progressivement les éléments triés, afin que les éléments non triés soient progressivement ordonnés. Cette méthode est appelée « séquençage de cocktails ».

java

public static void cocktailSort(int[] arr) {  
    int n = arr.length;  
    boolean swapped; // to flag if any swap has been made in a pass  
    for (int i = 0; i < n - 1; i++) {  
        swapped = false; // assume this pass will do nothing  
        for (int j = 0; j < n - 1 - i; j++) { // start with the second last element and go to the last one  
            if (arr[j] > arr[j + 1]) { // if the current element is greater than the next one, swap them  
                int temp = arr[j]; // swap elements  
                arr[j] = arr[j + 1];  
                arr[j + 1] = temp;  
                swapped = true; // flag to indicate a swap has been made in this pass  
            }  
        }  
        // if no two elements were swapped in this pass, then the array is sorted, so we can stop the sorting process  
        if (!swapped) break; // no swaps means the array is sorted, so we can stop the sorting process. This optimization is not required for correctness, but it can help in practice. If the array is already sorted, the outer loop will keep making passes without making any swaps, so we can stop early. This optimization can be applied to any version of bubble sort

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!

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn