Merge Sort es un algoritmo de clasificación eficaz y estable basado en operaciones de fusión. Este algoritmo es una aplicación muy típica del método divide y vencerás .
La clasificación por combinación combina dos subsecuencias ordenadas para obtener una secuencia completamente ordenada, es decir, primero ordena cada subsecuencia y luego ordena los segmentos de la subsecuencia. Si dos listas ordenadas se fusionan en una lista ordenada, lo llamamos fusión bidireccional .
La velocidad de clasificación por combinación es superada solo por la clasificación rápida, y la complejidad del tiempo es O (nlogn). El proceso de división utiliza la idea de dicotomía, que es un proceso recursivo. Para reducir el problema de abrir espacio continuamente durante el proceso recursivo, primero podemos abrir un espacio temporal antes de fusionar y ordenar, y usar este espacio. uniformemente durante el proceso recursivo Simplemente fusione.
Por ejemplo:
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,izquierda,r derecho,tem);print(arr);}publicstaticvoidmergeSort(int[]arr,intleft,intright,int[]tem){if(derecha-izquierda<1){return;}intmid=izquierda+(derecha-izquierda)/2 ;mergeOrdenar(arr,izquierda,medio,tem);mergeOrdenar(arr,medio+1,derecha,tem);merge(arr,izquierda,medio ,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++];} }mientras(l<=mi d){tem[index++]=arr[l++];} while(r<=right){tem[index++]=arr[r++];}for(inti=0;i<(right-left+1);i++ ){arr[izquierda +i]=tem[i];}}privatestaticvoidprint(int[]arr){for(inti:arr){System.out.print(i+t);}System.out.println();}} Los resultados de ejecución son los siguientes:
8623745191071019234586