Qu'est-ce que le tri par fusion ? Explication détaillée du tri par fusion en Java

Implémentation Java du tri par fusion

Le tri par fusion (MERGE-SORT) est un algorithme de tri efficace basé sur des opérations de fusion. Cet algorithme est un exemple très typique de la méthode diviser pour régner (pide and Conquer). application. Fusionnez les sous-séquences déjà ordonnées pour obtenir une séquence complètement ordonnée ; c'est-à-dire que vous devez d'abord rendre chaque sous-séquence ordonnée, puis ordonner les segments de la sous-séquence. Si deux listes ordonnées sont fusionnées en une seule liste ordonnée, on parle de fusion bidirectionnelle. Le processus de fusion est le suivant : comparez les tailles de a[i] et b[j], si a[i]≤b[j], copiez l'élément a[i] dans la première liste ordonnée dans r[k] et ajoutez 1 à i et k respectivement ; sinon, copiez l'élément b[j] dans la deuxième liste ordonnée dans r[k], et ajoutez 1 à j et k respectivement, et ainsi de suite, jusqu'à ce qu'après la récupération d'une liste ordonnée, le reste les éléments de l'autre liste ordonnée sont copiés dans les cellules de r de l'indice k à l'indice t. Nous utilisons généralement la récursion pour implémenter l'algorithme de tri par fusion. Tout d'abord, l'intervalle à trier [s, t] est divisé en deux par le point médian, puis la sous-plage de gauche est triée, puis la sous-plage de droite est triée, et enfin, l'intervalle de gauche et l'intervalle de droite sont fusionnés en intervalles ordonnés [s,t].

Deux points principaux :

1 Comment fusionner deux séquences ordonnées en une seule séquence ordonnée

2 Comment transformer ces deux séquences en une séquence ordonnée

Résoudre le premier problème :

Comment fusionner deux séries ordonnées. C'est très simple, il suffit de comparer le premier numéro des deux séquences et de prendre d'abord le plus petit. Après l'avoir pris, supprimez le numéro dans la séquence correspondante. Comparez-les ensuite si l’une des colonnes est vide, supprimez simplement les données de l’autre colonne une par une.

public static void merge(int[] nums, int low, int mid, int high) {  
        int[] temp = new int[high - low + 1];  
        int i = low;// 左指针  
        int j = mid + 1;// 右指针  
        int k = 0;  
  
        // 把较小的数先移到新数组中  
        while (i <= mid && j <= high) {  
            if (nums[i] < nums[j]) {  
                temp[k++] = nums[i++];  
            } else {  
                temp[k++] = nums[j++];  
            }  
        }  
  
        // 把左边剩余的数移入数组  
        while (i <= mid) {  
            temp[k++] = nums[i++];  
        }  
  
        // 把右边边剩余的数移入数组  
        while (j <= high) {  
            temp[k++] = nums[j++];  
        }  
  
        // 把新数组中的数覆盖nums数组  
        for (int k2 = 0; k2 < temp.length; k2++) {  
            nums[k2 + low] = temp[k2];  
        }  
    }

Deuxième question : Les groupes A et B peuvent être divisés en deux groupes. Par analogie, lorsque le groupe séparé ne comporte qu'une seule donnée, on peut considérer que le groupe est en ordre, et alors les deux groupes adjacents peuvent être fusionnés. De cette manière, le tri par fusion est effectué en décomposant d'abord le tableau de manière récursive, puis en fusionnant le tableau.

public static int[] sort(int[] nums, int low, int high) {  
        int mid = (low + high) / 2;  
        if (low < high) {  
            // 左边  
            sort(nums, low, mid);  
            // 右边  
            sort(nums, mid + 1, high);  
            // 左右归并  
            merge(nums, low, mid, high);  
        }  
        return nums;  
    }

Code complet :

package algorithm;import java.util.Arrays;public class MergeSort {	  public static int[] sort(int[] nums, int low, int high) {  
	        int mid = (low + high) / 2;  
	        if (low < high) {  
	              
	            sort(nums, low, mid);  
	             
	            sort(nums, mid + 1, high);  
	             
	            merge(nums, low, mid, high);  
	        }  
	        return nums;  
	    }  
	  
	    public static void merge(int[] nums, int low, int mid, int high) {  
	        int[] temp = new int[high - low + 1];  
	        int i = low;	        int j = mid + 1;  
	        int k = 0;  
	  
	        while (i <= mid && j <= high) {  
	            if (nums[i] < nums[j]) {  
	                temp[k++] = nums[i++];  
	            } else {  
	                temp[k++] = nums[j++];  
	            }  
	        }  
	  
	      
	        while (i <= mid) {  
	            temp[k++] = nums[i++];  
	        }  
	  
	      
	        while (j <= high) {  
	            temp[k++] = nums[j++];  
	        }  
	  
	        
	        for (int k2 = 0; k2 < temp.length; k2++) {  
	            nums[k2 + low] = temp[k2];  
	        }  
	    }  
	public static void main(String[] args) {		  int[] nums = { 29, 78, 800, 3, 551, 6, 97, 0, 5, 4 };  
		  
	        MergeSort.sort(nums, 0, nums.length-1);  
	        System.out.println(Arrays.toString(nums));  
	}

}

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!