병합 정렬(Merge Sort) 은 병합 연산을 기반으로 하는 효과적이고 안정적인 정렬 알고리즘입니다. 이 알고리즘은 분할 및 정복 방법을 적용한 매우 일반적인 방법입니다.
병합 정렬은 두 개의 정렬된 하위 시퀀스를 결합하여 완전히 정렬된 시퀀스를 얻습니다. 즉, 먼저 각 하위 시퀀스를 정렬한 다음 하위 시퀀스 세그먼트를 정렬합니다. 두 개의 순서 목록이 하나의 순서 목록으로 병합되는 경우 이를 양방향 병합 이라고 합니다.
병합 정렬의 속도는 퀵 정렬에 이어 두 번째이며 시간 복잡도는 O(nlogn)입니다. 분할 과정은 재귀 과정인 이분법(dichotomy) 개념을 활용한 것으로, 재귀 과정에서 계속해서 공간이 열리는 문제를 줄이기 위해 병합, 정렬 이전에 먼저 임시 공간을 열고 이 공간을 활용할 수 있다. 재귀 프로세스 중에 균일하게 병합하십시오.
예를 들어:
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(오른쪽-왼쪽<1){return;}intmid=왼쪽+(오른쪽-왼쪽)/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. 인쇄();}} 실행 결과는 다음과 같습니다.
8623745191071019234586