Merge Sort ist ein effektiver und stabiler Sortieralgorithmus, der auf Zusammenführungsoperationen basiert. Dieser Algorithmus ist eine sehr typische Anwendung der Divide-and-Conquer-Methode .
Durch die Zusammenführungssortierung werden zwei geordnete Teilsequenzen kombiniert, um eine vollständig geordnete Sequenz zu erhalten. Das heißt, zuerst wird jede Teilsequenz sortiert und dann werden die Teilsequenzsegmente sortiert. Wenn zwei geordnete Listen zu einer geordneten Liste zusammengeführt werden, nennen wir das eine bidirektionale Zusammenführung .
Die Geschwindigkeit der Zusammenführungssortierung ist nach der Schnellsortierung an zweiter Stelle und die Zeitkomplexität beträgt O(nlogn). Der Aufteilungsprozess nutzt die Idee der Dichotomie, bei der es sich um einen rekursiven Prozess handelt. Um das Problem der kontinuierlichen Raumeröffnung während des rekursiven Prozesses zu verringern, können wir vor dem Zusammenführen und Sortieren zunächst einen temporären Raum öffnen und diesen Raum nutzen einheitlich während des rekursiven Prozesses. Einfach zusammenführen.
Zum Beispiel:
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++];}}while( 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();}} Die Laufergebnisse sind wie folgt:
8623745191071019234586