Algorithme de tri par fusion

Compréhension approfondie de l'algorithme de tri par fusion

L'idée centrale de l'algorithme de tri par fusion est la méthode diviser pour régner, c'est-à-dire « diviser pour régner ». Il divise récursivement un tableau en sous-tableaux plus petits jusqu'à ce que chaque sous-tableau ne contienne qu'un seul élément (qui est maintenant trié). Il fusionne ensuite ces sous-tableaux en un tableau trié plus grand. Il convient de noter que le processus de tri a lieu pendant la phase de fusion et non pendant la phase de division.

Démonstration d'algorithme

Supposons que nous ayons un tableau à trier :

Nous divisons le tableau en deux sous-tableaux gauche et droit :

Continuez la division récursive jusqu'à ce que chaque sous-tableau n'ait qu'un seul élément :

Ensuite, fusionnez et triez ces sous-tableaux : valeurs plus petites à gauche, valeurs plus grandes à droite.

Enfin trié :

Implémentation du code (Java)

Le code Java original présente des problèmes d'efficacité que nous pouvons optimiser. Le code amélioré est le suivant :

import java.util.Arrays;

public static void mergeSort(int[] array) {
    int n = array.length;
    if (n < 2) {
        return;
    }
    int middle = n / 2;
    int[] left = Arrays.copyOfRange(array, 0, middle);
    int[] right = Arrays.copyOfRange(array, middle, n);

    mergeSort(left);
    mergeSort(right);

    int leftIndex = 0;
    int rightIndex = 0;
    int arrayIndex = 0;

    while (leftIndex < left.length || rightIndex < right.length) {
        if (leftIndex < left.length && (rightIndex >= right.length || left[leftIndex] <= right[rightIndex])) {
            array[arrayIndex++] = left[leftIndex++];
        } else {
            array[arrayIndex++] = right[rightIndex++];
        }
    }
}

Ce code optimisé utilise la méthode Arrays.copyOfRange() pour copier les éléments du tableau plus efficacement et simplifie les conditions de boucle et les instructions de jugement dans le processus de fusion, améliorant ainsi la lisibilité et l'efficacité du code.

J'espère que cette explication et ce code améliorés pourront vous aider à mieux comprendre l'algorithme de 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!