연마 알고리즘: 정렬 의 병합 정렬

연마 알고리즘: 정렬 의 병합 정렬
탭 (스페이스 바 구분): 연마 알고리즘
연마 알고리즘: 정렬 의 병합 정렬
이해 병합 정렬
분 치 모델
점수
치료

코드 데모
알고리즘 분석

이해 병합 정렬
병합 정렬 (MERGE - SORT) 은 병합 사상 을 이용 한 정렬 방법 으로 이 알고리즘 은 분할 (divide - and - conquer) 의 전형 적 인 응용 이다.
쉽게 말 하면 정렬 할 배열 을 먼저 반 으로 나 누고 반 으로 나 누 어 정렬 한 다음 에 병합 하 는 것 이다.
분할 모델
우 리 는 독립 된 요소 로 구 분 될 때 까지 전체 배열 을 재 귀적 으로 분할 할 것 이다.... 와 같다

                 [8,4,5,7,1,3,6,2]
           [8,4,5,7]          [1,3,6,2]
        [8,4]     [5,7]     [1,3]    [6,2]
      [8]  [4]  [5]  [7]  [1]  [3]  [6]  [2]

그 다음 에 가장 작은 서브 문제, 즉 모든 독립 요소 에 대해 끊임없이 위로 두 개 씩 합 친다.

        [8]  [4]  [5]  [7]  [1]  [3]  [6]  [2]
        [4,8]     [5,7]     [1,3]    [2,6]
           [8,4,5,7]          [1,3,6,2]
               [1,2,3,4,5,6,7,8]

이런 구 조 는 마치 완전 이 진 트 리 와 같다 는 것 을 알 수 있다. 본 고의 병합 순 서 는 우 리 는 재 귀 를 통 해 실현 할 수 있다 (교체 하 는 방식 으로 실현 할 수도 있다).단 계 는 재 귀 분해 분자 서열 의 과정 으로 이해 할 수 있 고 재 귀 깊이 는 log 2n 이다.
나누다
점 에 있어 서 어 려 운 점 이 없 으 므 로 우 리 는 재 귀적 인 형식 을 사용한다.
다스리다
치료 에 있어 서 우 리 는 두 개의 질서 있 는 하위 서열 을 하나의 질서 있 는 서열 로 합 쳐 야 한다. 우 리 는 먼저 모든 요 소 를 하나의 보조 배열 에 복사 하고 보조 배열 을 두 개의 합병 할 배열 로 나 누 어야 한다.그 다음 에 두 개의 합병 대기 배열 을 비교 할 때 다음 과 같은 전략 을 사용 합 니 다. 1. 합병 대기 배열 의 두 노드 에 두 개의 지침 을 놓 고 요 소 를 비교 합 니 다.
예 를 들 어 위의 그림 에서 마지막 으로 합병 하려 면 [4, 5, 7, 8] 과 [1, 2, 3, 6] 두 개의 질서 있 는 하위 서열 을 최종 서열 [1, 2, 3, 4, 5, 6, 7, 8] 로 합 쳐 실현 절 차 를 살 펴 보 자.

1. [4,5,7,8] [1,2,3,6]    4，1     [1]
2. [4,5,7,8] [1,2,3,6]    4，2     [1,2]
3. [4,5,7,8] [1,2,3,6]    4，3     [1,2,3]
4. [4,5,7,8] [1,2,3,6]    4，6     [1,2,3,4]
5. [4,5,7,8] [1,2,3,6]    5，6     [1,2,3,4,5]
6. [4,5,7,8] [1,2,3,6]    7，6     [1,2,3,4,5,6]
7. [4,5,7,8] [1,2,3,6]   7     [1,2,3,4,5,6,7]
8. [4,5,7,8] [1,2,3,6]   8     [1,2,3,4,5,6,7,8]

코드 데모
복잡 한 코드 의 작성 에 대해 우 리 는 일반적으로 하나의 원칙 을 따른다. 즉, 먼저 주간 을 쓴 다음 에 각 작은 방법 을 쓴다.
이 알고리즘 에 대해 우 리 는 먼저 주간 함수 mergeSort 를 쓴 다음 sort 를 쓴 다음 merge 방법 을 씁 니 다.

package sort;

import java.util.Arrays;

/**
 * Created by japson on 4/18/2018.
 */
public class MergeSort {

    //          
    private static int[] temp;

    public static void main(String[] args) {
        int[] a =  {9,8,7,6,5,4,3,2,1};
        sort(a);
        System.out.println(Arrays.toString(a));
    }

    //               ，       
    public static void sort(int[] a) {
        //          
        temp = new int[a.length];
        sort(a,0,a.length-1);
    }

    //     ，     
    public static void sort(int[] a,int lo,int hi) {
        //            <=
        if (hi <= lo) return;
        int mid = (lo + hi)/2;
        sort(a,lo,mid);     //       ，        
        sort(a,mid+1,hi);   //       ，        
        merge(a,lo,mid,hi); //             
    }

    //            ，          ，           
    private static void merge(int[] a, int lo, int mid, int hi) {
        int i = lo;     //      
        int j = mid + 1;    //      

        //    k=hi，  hi 8，     9 
        for (int k = lo ; k <= hi ; k++) {
            temp[k] = a[k];
        }

        //    a  
        for (int k = lo ; k <= hi ; k++) {
            if (i > mid) {
                a[k] = temp[j];
                j ++;
            } else if (j > hi) {
                a[k] = temp[i];
                i++;
            } else if (temp[i] > temp[j]) {
                a[k] = temp[j];
                j++;
            } else {
                a[k] = temp[i];
                i++;
            }
        }
    }
}

알고리즘 분석
병합 정렬 은 안정 적 인 정렬 이 고 효율 적 인 정렬 이기 도 하 며 완전 이 진 트 리 특성 을 이용 한 정렬 은 일반 성능 이 그다지 나 쁘 지 않 습 니 다.
자바 에서 Arrays. sort () 는 TimSort 라 는 정렬 알고리즘 을 사 용 했 습 니 다. 바로 정렬 최적화 버 전 입 니 다.
매번 병합 작업 의 평균 시간 복잡 도 는 O (n) 이 고, 완전 이 진 트 리 의 깊이 는 | log2n | 입 니 다.전체 평균 시간 복잡 도 는 O (nlogn) 이다.그리고 병합 정렬 이 가장 좋 고 최 악 이 며 평균 시간 복잡 도 는 모두 O (nlogn) 이다.