Comment implémenter un algorithme de tri par fusion à l'aide de Java

Comment utiliser Java pour implémenter l'algorithme de tri par fusion

Introduction :
Le tri par fusion est un algorithme de tri classique basé sur la méthode diviser pour régner. L'idée est de diviser le tableau à trier en couches de sous-tableaux plus petites. par couche, puis passer L'opération de fusion fusionne séquentiellement les sous-tableaux en un tableau global ordonné. Dans cet article, nous présenterons en détail comment implémenter l'algorithme de tri par fusion à l'aide de Java et fournirons des exemples de code spécifiques.

Étapes de l'algorithme :
L'algorithme de tri par fusion comprend principalement trois étapes : le fractionnement, la fusion et le tri.

1. Split :
   Tout d'abord, nous devons diviser le tableau à trier en sous-tableaux plus petits couche par couche jusqu'à ce que chaque sous-tableau ne contienne qu'un seul élément. En termes d'implémentation spécifique, une méthode récursive peut être utilisée pour diviser continuellement le tableau en deux jusqu'à ce que la longueur du tableau soit 1.
2. Fusionner :
   Ensuite, nous devons fusionner les sous-tableaux divisés couche par couche. En termes d'implémentation spécifique, vous pouvez partir du sous-tableau inférieur et fusionner deux sous-tableaux ordonnés adjacents pour former un nouveau sous-tableau ordonné. Ensuite, fusionnez vers le haut couche par couche jusqu'à ce que l'ensemble du tableau soit fusionné. L'opération de fusion peut utiliser la méthode du double pointeur pour comparer tour à tour les éléments des deux sous-tableaux ordonnés et placer les éléments les plus petits dans le tableau de résultats jusqu'à ce que les deux sous-tableaux aient été parcourus.
3. Tri :
   Enfin, une fois la fusion terminée, l'ensemble du tableau est en ordre. La complexité temporelle de l'algorithme dépend du nombre d'opérations de fractionnement et de fusion, c'est-à-dire du nombre de niveaux de récursivité. Plus précisément, la complexité temporelle est O(nlogn), où n est la longueur du tableau.

Implémentation du code Java :
Ce qui suit est un exemple de code de l'algorithme de tri par fusion écrit en Java :

public class MergeSort {
    public static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int i = 0; i < n1; ++i) {
            L[i] = arr[left + i];
        }
        for (int j = 0; j < n2; ++j) {
            R[j] = arr[mid + 1 + j];
        }

        int i = 0, j = 0;
        int k = left;
        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++;
        }
    }

    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

    public static void main(String[] args) {
        int[] arr = { 38, 27, 43, 3, 9, 82, 10 };
        mergeSort(arr, 0, arr.length - 1);

        System.out.println("归并排序后的数组为：");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

Analyse du code :
L'exemple de code ci-dessus implémente les trois étapes de fractionnement, de fusion et de tri de l'algorithme de tri par fusion. Parmi elles, la méthode merge() est utilisée pour fusionner deux sous-tableaux ordonnés, et la méthode mergeSort() est utilisée pour diviser et fusionner des tableaux de manière récursive. Dans la méthode main(), nous pouvons appeler la méthode mergeSort() en passant le tableau à trier, et enfin obtenir un tableau ordonné.

Résumé :
Le tri par fusion est un algorithme de tri efficace qui peut obtenir de bonnes performances dans le pire des cas. Le tri par fusion peut trier des tableaux de n'importe quelle longueur en divisant et en fusionnant les tableaux à trier couche par couche. Dans des applications pratiques, nous pouvons utiliser le tri par fusion pour résoudre des problèmes de tri de données à grande échelle.

J'espère que cet article vous aidera à comprendre et à utiliser l'algorithme de tri par fusion, merci d'avoir lu !

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!