Merge Sort est un algorithme de tri efficace et stable basé sur des opérations de fusion. Cet algorithme est une application très typique de la méthode diviser pour régner .
Le tri par fusion combine deux sous-séquences ordonnées pour obtenir une séquence complètement ordonnée, c'est-à-dire qu'il faut d'abord trier chaque sous-séquence, puis trier les segments de la sous-séquence. Si deux listes ordonnées sont fusionnées en une seule liste ordonnée, nous appelons cela une fusion bidirectionnelle .
La vitesse du tri par fusion est juste derrière le tri rapide, et la complexité temporelle est O(nlogn). Le processus de fractionnement utilise l'idée de dichotomie, qui est un processus récursif. Afin de réduire le problème de l'ouverture continue de l'espace pendant le processus récursif, nous pouvons d'abord ouvrir un espace temporaire avant de fusionner et de trier, et d'utiliser cet espace. uniformément pendant le processus récursif.
Par exemple:
importjava.util.Arrays;publicclassMain{publicstaticvoidmain(String[]args){int[]arr=newint[]{86,23,7,45,19,10};intleft=0;intright=arr.length-1; int[]tem=Arrays.copyOf(arr,arr.length);print(arr);mergeSort(arr,left,right,tem);print(arr);}publicstaticvoidmergeSort(int[]arr,intleft,intright,int []tem){if(right-left<1){return;}intmid=left+(right-left)/2;mergeSort(arr,left,mid,tem);mergeSort(arr,mid+1,right,tem );merge(arr,left,mid,right,tem);}privatestaticvoidmerge(int[]arr,intleft,intmid,intright,int[]tem){intindex=0;intl=left,r=mid+1;while (l<=mid&&r<=right){if(arr[l]<arr[r]){tem[index++]=arr[l++];}else{tem[index++]=arr[r++];}}tandis que( l<=mid){tem[index++]=arr[l++];}while(r<=right){tem[index++]=arr[r++];}for(inti=0;i<(right-left+1 );i++){arr[left+i]=tem[i];}}privatestaticvoidprint(int[]arr){for(inti:arr){System.out.print(i+t);}System.out. println();}} Les résultats en cours d'exécution sont les suivants :
8623745191071019234586