알고리즘 개요/아이디어
병합 분류는 "분할 및 정복"이라는 전략을 기반으로합니다. 기본 아이디어는 다음과 같습니다.
1. 순서가 2 개의 배열의 경우 순서 배열로 병합하면 다음 코드를 쉽게 쓸 수 있습니다.
// a와 b는 모두 Ascend.public void merge (int [] a, int [] b, int [] c) {int i = 0, j = 0, k = 0; while (i <= a.length && j <= b.length) {if (a [i] <= b [i]) {c [k ++] = a [i ++]; } else {c [k ++] = b [j ++]; }} while (i <= a.length) {c [k ++] = a [i ++]; }} 이러한 병합 알고리즘이 효율적이고 시간 복잡성이 O (N)에 도달 할 수 있음을 쉽게 알 수 있습니다.
2. 정렬 해야하는 비정규 배열이 있지만 완전히 분할 된 두 개의 서브 어레이 A와 B가 별도로 주문됩니다. 위의 코드의 도움으로 쉽게 구현할 수 있습니다.
3. 그래서 A와 B가 무질서하면 어떻게해야합니까? 더 작은 배열로 나눌 수 있습니다.
4. 가장 작은 곳으로 나누면 각 서브 어레이에는 하나의 요소 만 있으면 주문 배열로 간주 될 수 있습니다.
5.이 가장 작은 배열부터 시작하여 위의 단계와 병합하면 전체 배열이 배열됩니다.
요컨대, 병합 분류는 재귀를 사용하고 먼저 배열을 서브 어레이로 분해 한 다음 배열을 병합하는 것입니다.
예
여기 예입니다. 배열 a = {2,1,3,5,2,3}를 정렬하려면 배열을 두 개의 서브 배열로 나누어 {2,1,3} 및 {5,2,3}로 나눕니다. 이 두 서브 어레이를 정렬 한 후 {1,2,3} 및 {2,3,5}가되어 두 배열을 병합하여 최종 순서 배열을 얻습니다. 코드 구현은 다음과 같습니다.
void sort (int [] a) {int [] aux = new int [a.length]; // aux array mergesort (a, 0, a.length -1, aux);} void mergesort (int [] a, int lo, int hi, int [] aux) {if (hi <= lo) return; int mid = lo + (hi -lo) / 2; Mergesort (a, lo, mid, aux); MERGESORT (A, MID + 1, HI, AUX); merge (a, lo, mid, hi, aux);} void merge (int [] a, int lo, int mid, int hi, int [] aux) {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 [i] <= aux [j]) a [k] = aux [i ++]; else a [k] = aux [j ++]; }} 또 다른 구현 : 상향식 정렬을 병합합니다
위의 구현에서는 큰 문제를 작은 문제로 나누고 별도로 해결 한 다음 모든 작은 문제에 대한 답을 사용하여 전체 큰 문제를 해결하는 것과 같습니다. 큰 배열의 작은 배열을 작은 배열로 나누는 것은 일종의 종류입니다. 상향식 정렬 인 또 다른 구현이 있습니다. 즉, 먼저 2를 병합 한 다음 4 및 4를 병합합니다 ... 코드 구현은 다음과 같습니다.
void sort (int [] a) {int n = a.length; int [] aux = new int [n]; for (int sz = 1; sz <n; sz + = sz) {for (int lo = 0; lo <n -sz; lo + = sz + sz) {// 각 합병 라운드에서 마지막 시간에 합병 된 두 번째 서브 어레이는 첫 번째 하위 배열 (a, lo, lo, lo + sz -1, math.min)보다 작을 수 있습니다. }}}