Implémenter et optimiser l'algorithme de tri par fusion de Java

Implémentation et optimisation de l'algorithme de tri par fusion Java

Le tri par fusion est un algorithme de tri basé sur la comparaison. Son idée principale est de diviser la séquence à trier en plusieurs sous-séquences, de trier chaque sous-séquence, et enfin il y aura des sous-séquences ordonnées. sont fusionnés dans une séquence ordonnée globale.

1. Mise en œuvre de l'algorithme de tri par fusion :
   La mise en œuvre de l'algorithme de tri par fusion peut être divisée en deux étapes : diviser pour mieux régner et fusionner.

(1) Diviser pour régner :
Tout d'abord, divisez la séquence à trier en deux parties jusqu'à ce que chaque sous-séquence ne comporte qu'un seul élément. Ensuite, ces sous-séquences sont fusionnées en sous-séquences ordonnées.

Ce qui suit est un exemple de code pour une implémentation récursive de l'algorithme de tri par fusion :

public class MergeSort {
    // 归并排序
    public void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            // 递归地对左右两边进行归并排序
            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);
            // 合并两个有序子序列
            merge(array, left, mid, right);
        }
    }

    // 合并两个有序子序列
    public void merge(int[] array, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left; // 左序列指针
        int j = mid + 1; // 右序列指针
        int k = 0; // 临时数组指针

        while (i <= mid && j <= right) {
            if (array[i] <= array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = array[i++];
        }

        while (j <= right) {
            temp[k++] = array[j++];
        }

        for (int l = 0; l < temp.length; l++) {
            array[left + l] = temp[l];
        }
    }
}

(2) Fusion :
La fonction de la fonction de fusion est de fusionner deux sous-séquences ordonnées en une séquence ordonnée. Dans l'implémentation spécifique, nous devons créer un tableau temporaire pour stocker les résultats fusionnés. Lors du parcours d'une sous-séquence, nous comparons les éléments de la sous-séquence, plaçons le plus petit élément dans un tableau temporaire et déplaçons le pointeur correspondant. Enfin, les éléments du tableau temporaire sont copiés dans le tableau d'origine.

2. Optimisation de l'algorithme de tri par fusion :
   L'algorithme de tri par fusion générera de nombreux tableaux de sous-séquences temporaires au cours du processus récursif, ce qui entraînera une allocation et une libération fréquentes de mémoire, augmentant la complexité spatiale de l'algorithme. Afin de réduire cette surcharge, l'efficacité de l'algorithme de tri par fusion peut être améliorée grâce aux méthodes d'optimisation suivantes :

(1) Utilisez le tri par insertion pour les sous-séquences à petite échelle :
Lorsque la taille de la sous-séquence est relativement petite, l'insertion le tri est plus efficace. Par conséquent, lors du processus récursif de tri par fusion, lorsque la taille de la sous-séquence est inférieure à un certain seuil, le tri par insertion peut être utilisé pour remplacer le processus récursif.

public void mergeSort(int[] array, int left, int right) {
    if (left < right) {
        if (right - left <= THRESHOLD) {
            // 子序列的规模小于阈值，采用插入排序
            insertionSort(array, left, right);
        } else {
            int mid = (left + right) / 2;
            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);
            merge(array, left, mid, right);
        }
    }
}

(2) Optimisez le processus de fusion :
Pendant le processus de fusion, vous pouvez d'abord stocker les deux sous-séquences dans deux tableaux temporaires, puis fusionner les deux tableaux temporaires dans le tableau d'origine. De cette façon, vous évitez de créer à plusieurs reprises des tableaux temporaires pendant le processus de fusion. Dans le même temps, puisque la taille du tableau temporaire est fixe, il peut être défini comme variable membre de la classe pour éviter une création répétée pendant le processus récursif.

public class MergeSort {
    private int[] temp;

    public void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            if (right - left <= THRESHOLD) {
                insertionSort(array, left, right);
            } else {
                int mid = (left + right) / 2;
                mergeSort(array, left, mid);
                mergeSort(array, mid + 1, right);
                merge(array, left, mid, right);
            }
        }
    }

    public void merge(int[] array, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int k = 0;

        while (i <= mid && j <= right) {
            if (array[i] <= array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = array[i++];
        }

        while (j <= right) {
            temp[k++] = array[j++];
        }

        for (int l = 0; l < k; l++) {
            array[left + l] = temp[l];
        }
    }
}

En résumé, ce qui précède est l'implémentation de l'algorithme de tri par fusion Java et de sa méthode d'optimisation. En optimisant le processus de fusion et en utilisant le tri par insertion pour les sous-séquences à petite échelle, l'efficacité de l'algorithme de tri par fusion peut être améliorée et la surcharge d'espace peut être réduite. Dans les applications pratiques, choisir des méthodes d'optimisation appropriées et faire des choix raisonnables basés sur les caractéristiques de la séquence de tri peuvent rendre l'algorithme plus efficace.

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!