Explication détaillée des algorithmes de tri courants implémentés en Java

Les algorithmes de tri sont un concept important en informatique et sont au cœur de nombreuses applications. Dans la vie quotidienne et au travail, nous avons souvent besoin de trier des données, comme trier des listes, trier des valeurs, etc. Java, en tant que langage de programmation largement utilisé, fournit de nombreux algorithmes de tri intégrés. Cet article fournira une introduction détaillée aux algorithmes de tri courants implémentés en Java.

1. Tri à bulles

Le tri à bulles est l'un des algorithmes de tri les plus simples mais les plus lents. Il parcourt l'ensemble du tableau, compare les éléments adjacents et déplace les valeurs plus grandes vers la droite étape par étape, déplaçant finalement le plus grand élément vers la fin du tableau. Ce processus est similaire au processus de bulles montant du bas vers la surface, d’où le nom de tri à bulles.

Voici l'algorithme de tri à bulles implémenté en Java :

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

Complexité temporelle : O(n^2)

2. élément et déplacez-le à la fin de la section triée. Le tri par sélection est similaire au tri à bulles, mais il ne nécessite pas d'échange constant d'éléments à chaque itération, ce qui le rend plus rapide.

Voici l'algorithme de tri par sélection implémenté en Java :

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

Complexité temporelle : O(n^2)

3. Tri par insertion (Tri par insertion)

Le tri par insertion est un algorithme de tri plus efficace. le tableau trié et insérez l’élément non trié dans la position correcte. Le tri par insertion convient aux ensembles de données plus petits en raison du nombre réduit d'échanges.

Voici l'algorithme de tri par insertion implémenté en Java :

public static void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Complexité temporelle : O(n^2)

4 Quick Sort (Quick Sort)

Quick Sort est un algorithme de tri efficace qui utilise diviser pour conquérir. L'idée est de diviser le tableau en sous-tableaux plus petits, puis de trier les sous-tableaux de manière récursive et de les fusionner pour former le résultat final trié. La clé du tri rapide est de sélectionner l’élément du milieu et de trier par taille.

Ce qui suit est l'algorithme de tri rapide implémenté en Java :

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

public static int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

Complexité temporelle : O(n log n)

5 Merge Sort (Merge Sort)

Le tri par fusion est un autre algorithme de tri courant qui utilise des points. pour diviser le tableau en sous-tableaux plus petits, puis les trier un par un et les fusionner pour produire le résultat final trié. Le tri par fusion est généralement plus lent que le tri rapide, mais il est plus stable.

Voici l'algorithme de tri par fusion implémenté en Java :

public static void mergeSort(int[] arr, int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

public static void merge(int[] arr, int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int[] L = new int[n1];
    int[] R = new int[n2];
    for (int i = 0; i < n1; i++) {
        L[i] = arr[l + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[m + j + 1];
    }
    int i = 0, j = 0;
    int k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

Complexité temporelle : O(n log n)

Conclusion

Ce qui précède sont des algorithmes de tri courants en Java et leurs détails d'implémentation. Le tri par bulles et le tri par sélection sont plus simples mais ont une complexité temporelle plus élevée ; le tri par insertion est plus rapide et convient aux ensembles de données plus petits ; le tri rapide est plus rapide mais instable ; le tri par fusion est stable mais plus lent ; En utilisation réelle, la sélection doit être effectuée en fonction de différents échantillons de données et des besoins réels.

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!