개요
병합 정렬 방법은 2 개 (또는 2 개 이상)의 정렬 된 테이블을 새로운 주문 테이블로 병합하는 것입니다. 그런 다음 순서 대상 후속이 전체 순서 시퀀스로 병합됩니다.
병합 분류는 "분할 및 정복"에 속하는 재귀를 사용하여 구현됩니다. 대상 배열은 중간에서 2 개로 나누어지고 두 배열은 별도로 정렬됩니다. 정렬이 완료되면 두 배열이 함께 "병합"됩니다. 병합 분류에서 가장 중요한 것은 "병합"프로세스입니다. 병합 프로세스에서 병합 해야하는 두 배열과 일치하는 추가 공간이 필요합니다.
생식 이미지 :
단계
크기가 두 개의 정렬 된 시퀀스의 합이되도록 공간을 적용하십시오. 이 공간은 병합 된 시퀀스를 저장하여 두 개의 포인터를 설정하는 데 사용됩니다. 초기 위치는 두 개의 정렬 된 시퀀스의 시작 위치이며, 두 포인터가 가리키는 요소를 비교하고 비교적 작은 요소를 선택하고 병합 된 공간에 넣고 포인터를 다음 위치로 이동합니다. 포인터가 시퀀스의 끝에 도달 할 때까지 3 단계를 반복하십시오. 다른 시퀀스의 나머지 모든 요소를 병합 된 시퀀스의 끝에 직접 복사하십시오.
원시 데이터 :
3 5 2 6 2
병합의 전제 조건은 배열을 분리하여 배열을 2로 나눈 다음 두 개로 나누고 다시 나눌 수 없으며 병합하는 것입니다.
첫 번째 라운드는 분리되어 있습니다. 색인 2 ((0+4)/2 = 2)는 중간입니다.
[3 5 2] [6 2]
두 번째 분리 라운드, 별도 [3 5 2]
[3 5] [2] [6 2]
세 번째 분리 라운드, 분리 [3 5]
[3] [5] [2] [6 2]
병합 [3] [5]
[3 5] [2] [6 2]
병합 [3 5] [2]
[2 3 5] [6 2]
네 번째 라운드는 분리되어 분리됩니다 [6 2]
[2 3 5] [6] [2]
병합 [6] [2]
[2 3 5] [2 6]
병합 [2 3 5] [2 6]
[2 2 3 5 6]
코드 구현 (Java)
package com.coder4j.main.arithmetic.sorting; public class merge {private static int mark = 0; / ** * sort merge sort * * @param array * @param low * @param high * @return * / private static int [] sort (int [] array, int low, int high) {int mid = (Low + High) / 2; if (low <high) {Mark ++; System.out.println ( "Throwth in Progress" + Mark + "후속 분리, get"); System.out.println ( "[" + low + "-" + mid + "] [" + (mid + 1) + "-" + high + "]; // 왼쪽 배열 정렬 (Array, Low, Mid); // 오른쪽 배열 정렬 (배열, 중간 + 1, 높음); // 왼쪽 및 오른쪽 병합 (Array, Low, Mid, High); } 반환 배열; } / ** * 배열 병합 * * @param 배열 * @param low * @param mid * @param high * / private static void merge (int [] 배열, int low, int mid, int high) {system.out.println (merge : [ " + low +"-" + mid +"] 및 [ " + (mid + 1) +"-" +" "; int [] temp = new int [High -Low + 1]; int i = low; // 왼쪽 포인터 int j = mid + 1; // 오른쪽 포인터 int k = 0; // 작은 숫자를 새 배열로 먼저 이동하는 동안 (i <= mid && j <= high) {if (array [i] <array [j]) {temp [k ++] = 배열 [i ++]; } else {temp [k ++] = 배열 [j ++]; }} // 두 배열 중 하나에 나머지 요소가있을 수 있습니다. // 왼쪽의 나머지 번호를 배열로 이동하는 동안 (i <= mid) {temp [k ++] = 배열 [i ++]; } // 오른쪽의 나머지 번호를 배열로 이동하는 동안 (j <= high) {temp [k ++] = 배열 [j ++]; } // (int m = 0; m <temp.length; m ++)에 대한 새 배열에서 숫자를 덮어 씁니다. {array [m+low] = temp [m]; }} / ** * MERGE SORT * * @param array * @return * / public static int [] sort (int [] array) {return sort (array, 0, array.length -1); } public static void main (String [] args) {int [] array = {3, 5, 2, 6, 2}; int [] sorted = sort (배열); System.out.println ( "최종 결과"); for (int i : sorted) {system.out.print (i + ""); }}}출력 테스트 결과 :
첫 번째 분리가 수행되고 있으며, [0-2] [3-4]가 수행되고 있으며, 두 번째 분리가 수행되고 있으며 [0-1] [2-2]가 수행되고 있으며, 세 번째 분리가 수행되고 있으며, [0-0] [1-1] 병합 : [0-0]과 [1-1] 합병 : [0-1] 및 [3-2]가 수행되고 있으며, 4 차 분리가 수행되고 있으며 [4-4] 병합 : [3-3] 및 [4-4] 병합 : [0-2] 및 [3-4] 최종 결과 2 2 3 5 6
테스트 후 예제의 결과와 일치합니다.