Comprendre l'algorithme de tri à bulles (avec des exemples en Java)

Explication détaillée du Bubble Sort : un algorithme de tri simple

Le tri à bulles est l'un des algorithmes de tri les plus simples. Il fonctionne en comparant à plusieurs reprises les éléments adjacents et en les échangeant s'ils sont en panne. Par exemple, si l'ordre de tri est croissant, les éléments adjacents sont comparés et le plus grand élément est placé à droite. À chaque itération, nous comparons uniquement les éléments non triés et plaçons le plus grand élément à la dernière position des éléments non triés dans le tableau.

Cet algorithme porte bien son nom de tri à bulles car les éléments se déplacent vers le côté droit du tableau à chaque itération, comme une bulle remontant à la surface de l'eau.

Comment fonctionne le tri à bulles

Supposons que nous voulions trier ce tableau par ordre croissant :

Première itération

Dans la première itération, nous essayons de déplacer le plus grand élément vers la fin du tableau. Nous comparerons donc à plusieurs reprises les éléments adjacents et les échangerons s’ils sont en panne.

Les éléments qui ont été déplacés vers la bonne position sont considérés comme triés.

Itérations suivantes

Ce processus est répété pour toutes les itérations jusqu'à ce que le tableau soit trié. A chaque itération, nous comparons uniquement les éléments non triés puisque les éléments triés sont déjà dans le bon ordre.

Nous parcourons le tableau n-1 fois, où n est la longueur du tableau. Autrement dit, puisque notre tableau comporte six éléments, nous ne parcourons le tableau que cinq fois. En effet, après la cinquième itération, les cinq éléments ont été placés dans leurs positions correctes, donc l'élément final non trié est considéré comme trié. Une fois toutes les itérations terminées, nous obtiendrons un tableau trié.

Mise en place du tri à bulles

public class BubbleSortTest {
    public static void main(String[] args) {
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("未排序数组: " + Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("已排序数组: " + Arrays.toString(arr));
    }

    public static void bubbleSort(int[] arr) {
        int size = arr.length;

        // 循环遍历数组 size-1 次
        for (int i = 0; i < size - 1; i++) {
            // 比较相邻元素
            for (int j = 0; j < size - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

L'exécution de ce code imprimera le résultat suivant dans la console :

<code>未排序数组: [8, 2, 6, 4, 9, 1]
已排序数组: [1, 2, 4, 6, 8, 9]</code>

Dans cette implémentation du tri à bulles, nous parcourrons le tableau à chaque fois, même si le tableau est déjà trié. Nous pouvons optimiser davantage le code afin que le tri s'arrête une fois le tableau trié.

Tri à bulles optimisé

public static void bubbleSortOptimised(int[] arr){
    int size = arr.length;
    boolean swapped;

    // 循环遍历数组 size-1 次
    for (int i = 0; i < size - 1; i++) {
        swapped = false;
        // 比较相邻元素
        for (int j = 0; j < size - i - 1; 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;
    }
}

Avec cette implémentation, si nous essayons de trier un tableau déjà trié, nous n'itérerons qu'une seule fois et nous arrêterons lorsqu'aucun tri n'aura lieu.

Complexité du tri à bulles

Complexité temporelle :

Meilleur des cas (O(n)) :

Le meilleur des cas est que le tableau d'entrée est déjà trié. L'algorithme ne parcourt le tableau qu'une seule fois pour vérifier s'il est trié et n'effectue aucun échange.

Cas moyen (O(n²)) :

Lorsque les éléments du tableau d'entrée sont dans un ordre aléatoire. L'algorithme doit itérer plusieurs fois et effectuer des échanges pour trier le tableau.

Pire des cas (O(n²)) :

Le pire des cas est que le tableau d'entrée soit trié dans l'ordre inverse. L'algorithme effectue n-1 itérations et effectue le nombre maximum d'échanges.

Complexité spatiale O(1) :

Le tri à bulles est un algorithme de tri sur place, c'est-à-dire qu'il ne nécessite aucune mémoire supplémentaire proportionnelle à la taille du tableau d'entrée.

Conclusion

Le tri à bulles est un algorithme facile à comprendre et à mettre en œuvre. Cependant, en raison de sa complexité temporelle élevée, il n’est pas adapté au traitement de grands ensembles de données. Le tri à bulles peut être utilisé lorsque vous travaillez avec de petits ensembles de données ou lorsque vous ne vous souciez pas de la complexité.

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!