Analyse étape par étape des étapes de mise en œuvre du tri par fusion Java

Analyse étape par étape du processus d'implémentation du code de tri par fusion Java

Introduction :
Le tri par fusion est un algorithme classique de division et de conquête, qui divise un tableau en deux tableaux plus petits, puis trie les deux tableaux séparément, et enfin Fusionnez deux tableaux triés en un seul tableau trié. Dans cet article, nous analyserons étape par étape le processus d'implémentation du tri par fusion en Java et fournirons des exemples de code spécifiques.

1. Idée de base :
   L'idée de base du tri par fusion est de diviser récursivement le tableau à trier en deux sous-tableaux plus petits, puis de trier les deux sous-tableaux et de les fusionner en un tableau ordonné. Ce processus se poursuivra de manière récursive jusqu'à ce que le plus petit sous-tableau ne contienne qu'un seul élément, puis le tri sera complété par la fusion de ces sous-tableaux ordonnés.
2. Processus d'implémentation :
   Voici le processus d'implémentation du tri par fusion en Java :

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 m = 0; m < temp.length; m++) {
            array[left + m] = temp[m];
        }
    }

    // 测试
    public static void main(String[] args) {
        int[] array = {8, 5, 2, 9, 5, 6, 3};
        int n = array.length;

        MergeSort mergeSort = new MergeSort();
        mergeSort.mergeSort(array, 0, n - 1);

        System.out.println("归并排序结果：");
        for (int i = 0; i < n; i++) {
            System.out.print(array[i] + " ");
        }
    }
}

3. Exemple de description :
   Dans le code ci-dessus, la méthode mergeSort est la fonction d'entrée du tri par fusion, qui reçoit un tableau à trier et les limites gauche et droite du tableau. Dans cette fonction, nous déterminons d'abord si les limites gauche et droite remplissent les conditions de fractionnement (c'est-à-dire left ) Si tel est le cas, recherchez le point médian du tableau et appelez <code>mergeSort trie les moitiés gauche et droite. Enfin, appelez la fonction <code>merge pour fusionner les deux sous-tableaux ordonnés en un seul tableau ordonné. mergeSort方法是归并排序的入口函数，它接收一个待排序的数组以及数组的左右边界。在该函数中，我们首先判断左右边界是否满足拆分的条件（即left ），如果满足，则找出数组的中点，并递归调用<code>mergeSort函数对左半部分和右半部分进行排序。最后，调用merge函数将两个有序的子数组合并为一个有序的数组。

merge函数中，我们创建一个临时数组来存储合并后的子数组，然后定义三个指针i、j、k

Dans la fonction merge, nous créons un tableau temporaire pour stocker le sous-tableau fusionné, puis définissons trois pointeurs i, j , k pointe respectivement vers la position de départ de la moitié gauche, la position de départ de la moitié droite et la position de départ du tableau temporaire. Nous comparons la taille des éléments dans la moitié gauche et la moitié droite, plaçons le plus petit élément dans un tableau temporaire et reculons le pointeur correspondant d'un bit. Si tous les éléments d'un certain sous-tableau sont placés dans le tableau temporaire, alors nous copions les éléments restants du sous-tableau à la fin du tableau temporaire. Enfin, nous copions les éléments du tableau temporaire vers le tableau d'origine.
4. 
   
Résumé :

L'algorithme de tri par fusion divise de manière récursive le tableau à trier en sous-tableaux plus petits et réalise un tri global en fusionnant ces sous-tableaux ordonnés. En pratique, la complexité temporelle de l'algorithme de tri par fusion est O(nlogn), et il a une meilleure stabilité et évolutivité que les autres algorithmes de tri. En analysant progressivement le processus de mise en œuvre du code de tri par fusion Java, nous pouvons mieux comprendre ses idées de base et ses méthodes de mise en œuvre. 🎜🎜

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!