병합 정렬 중의 분치와 병합

컴퓨터 과학에서 분치와 귀속은 혼동되기 쉬운 두 개념이다.나는 양자 간의 관계를 분명히 할 필요가 있다고 생각한다.나의 이해는 분치는 일종의 사상이고 귀속은 일종의 수단이다.다음은 백과사전에서 분치와 귀속에 대한 정의이다.
[분치 알고리즘]의 기본 사상은 하나의 규모가 N인 문제를 K개의 규모가 비교적 작은 하위 문제로 분해하는 것이다. 이런 하위 문제는 서로 독립되고 원래의 문제와 성질이 같다.자문제의 해를 구하면 원문제의 해를 얻을 수 있다.즉, 목표를 나누어 프로그램을 완성하는 알고리즘으로 간단한 문제는 이분법으로 완성할 수 있다.
프로그램이 자신의 프로그래밍 기교를 호출하는 것을 [귀속]이라고 한다.귀속은 하나의 알고리즘으로 프로그램 설계 언어에서 광범위하게 응용된다.하나의 과정이나 함수는 그 정의나 설명에서 자신을 직접 또는 간접적으로 호출하는 방법이 있다. 이것은 보통 대형 복잡한 문제를 층층이 원래의 문제와 비슷한 규모가 작은 문제로 바꾸어 해답을 구한다. 귀속 전략은 소량의 프로그램만 있으면 문제 풀이 과정에 필요한 여러 차례의 중복 계산을 묘사할 수 있어 프로그램의 코드량을 크게 줄일 수 있다.
많은 정렬 알고리즘 중에서 하나의 알고리즘은 분치와 귀속의 관계를 직관적이고 명확하게 나타낼 수 있는데 그것이 바로 [귀합 정렬]이다.
병합 정렬의 기본적인 사고방식은 하나의 수조를 두 부분으로 나누고 두 부분을 각각 정렬한 다음에 두 부분을 병합하여 최종 결과를 얻는 것이다.
듣자니 아직 뭔가 부족한 것 같다. 여기서 부족한 것은 바로 분치사상이다. 하나의 규모가 N인 문제를 2개의 규모가 N/2인 문제로 분해하는 것이다. 그들의 규모는 여전히 매우 크기 때문에 컴퓨터가 그것들을 쉽게 해결할 수 있을 때까지 계속 분해해야 한다.병합 정렬 중의 자수 그룹의 길이가 2일 때(즉 자수 그룹에 두 개의 원소만 있음) 병합은 일종의 정렬이 된다.다음에 병합된 가장 작은 소자수 그룹을 병합을 기다리는 일부분으로 더 큰 자수 그룹에 되돌려주면 병합 정렬의 분치가 완성된다.
상술한 분치 사상을 바탕으로 돌아가는 것보다 더 좋은 해결 방법은 없을 것이다.먼저 하나의 예를 보십시오.
초기화 역순 배열 a:16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
매번 병합수조의 하계가 로, 상계가hi라고 가정하고 대칭점mid=lo+(hi-lo)/2를 정의한다.
다음은 귀속을 이용한 귀합 과정(빨간색 부분은 매번 귀합된 수조)이다.
lo=0, mid=0, hi=115 16 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
lo=2, mid=2, hi=3 15 16 13 14 12 11 10 9 8 7 6 5 4 3 2 1 
lo=0, mid=1, hi=313 14 15 16 12 11 10 9 8 7 6 5 4 3 2 1 
lo=4, mid=4, hi=5 13 14 15 16 11 12 10 9 8 7 6 5 4 3 2 1 
lo=6, mid=6, hi=7 13 14 15 16 11 12 9 10 8 7 6 5 4 3 2 1 
lo=4, mid=5, hi=7 13 14 15 16 9 10 11 12 8 7 6 5 4 3 2 1 
lo=0, mid=3, hi=79 10 11 12 13 14 15 16 8 7 6 5 4 3 2 1 
lo=8, mid=8, hi=9 9 10 11 12 13 14 15 16 7 8 6 5 4 3 2 1 
lo=10, mid=10, hi=11 9 10 11 12 13 14 15 16 7 8 5 6 4 3 2 1 
lo=8, mid=9, hi=11 9 10 11 12 13 14 15 16 5 6 7 8 4 3 2 1 
lo=12, mid=12, hi=13 9 10 11 12 13 14 15 16 5 6 7 8 3 4 2 1 
lo=14, mid=14, hi=15 9 10 11 12 13 14 15 16 5 6 7 8 3 4 1 2 
lo=12, mid=13, hi=15 9 10 11 12 13 14 15 16 5 6 7 8 1 2 3 4 
lo=8, mid=11, hi=15 9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8 
lo=0, mid=7, hi=151 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
구현 코드:

public class merge_sort {
	private static int[] aux;// 

	public static void sort(int[] a){
		aux=new int[a.length];
		sort(a, 0, a.length-1);
	}// 
	
	private static void sort(int[] a, int lo, int hi){
		if (hi<=lo)
			return;// 

		int mid=lo+(hi-lo)/2;
		sort(a, lo, mid);//s1: 
		sort(a, mid+1, hi);//s2: 
		merge(a, lo, mid, hi);//s1 s2 
	}
	
	public static void merge(int[] a, int lo, int mid, int hi){
		int i=lo, j=mid+1;
		for (int k=lo; k<=hi; k++)
			aux[k]=a[k];
		
		for (int k=lo; k<=hi; k++)
			if (i>mid)
				a[k]=aux[j++];
			else if (j>hi)
				a[k]=aux[i++];
			else if (aux[j]

통합 프로세스:

 （ ， ）

            merge(a, 0, 0, 1)

            merge(a, 2, 2, 3)

        merge(a, 0, 1, 3)

            merge(a, 4, 4, 5)

            merge(a, 6, 6, 7)

        merge(a, 4, 5, 7)

    merge(a, 0, 3, 7)

            merge(a, 8, 8, 9)

            merge(a, 10, 10, 11)

        merge(a, 8, 9, 11)

            merge(a, 12, 12, 13)

            merge(a, 14, 14, 15)

        merge(a, 12, 13, 15)

    merge(a, 8, 11, 15)

merge(a, 0, 7, 15)