병합 정렬 알고리즘 상세 해석

1694 단어 데이터 구조
병합 순 서 는 재 귀 와 분 치 기술 로 이 루어 진 것 으로 정렬 대기 열 을 점점 작은 하위 서열 로 나 누 었 다. 즉, 재 귀 는 길이 가 1 인 하위 서열 로 나 누고 병합 하여 n / 2 (위 에서 정리) 의 길이 가 2 또는 1 인 하위 서열 을 얻 은 다음 에 이런 하위 서열 을 두 개 로 나 누 어 완전한 하위 서열 을 얻 을 때 까지 한다.대기 서열 [49, 38, 65, 97, 76, 13, 27] 에 대해 먼저 구분 한 다음 에 합병 대기 서열: [49 38 65 97 76 13 27] 길 이 는 1 개의 서열 이다. [49] [38] [97] [76] [13] [27] [27] 한 번 의 합병: [38 49] [65 97] [13 76] [27] 두 번 의 합병: [38 49 65 97] [13 27 76] 세 번 의 합병: [13 27 38 49 65 76] 합병 과정 에서하위 서열 의 정렬 실현: 하위 서열 에 따라 구 분 된 중간 값 n / 2, 즉 코드 중의 q, p 는 하위 서열 의 시작 색인 이 고 r 는 하위 서열 의 끝 색인 이다. 그러면 하나의 (p, r) 의 하위 서열 을 (p, q) 와 (q + 1, r) 의 두 서열 로 나 누 어 a, b 로 설정 하고 두 배열 을 각각 a, b 두 서열 로 저장 하 며 각각 작은 표지 i, j 로 a, b 두 서열 을 표시 한다.만약 a [i] < b [j], 작은 값 a [i] 를 다른 배열 에 저장 하고, 반대로 b [j] 를 다른 배열 에 저장 합 니 다.최종 b 의 서열 이 다 옮 겨 다 니 고 a 에 요소 가 옮 겨 다 니 지 않 으 면 a 의 나머지 요 소 를 다른 배열 에 저장 하고 반대로 b 의 요 소 를 저장 해 야 합 니 다.주: 다른 배열 은 길이 가 두 배열 의 합 인 새로운 배열 로 p 를 시작 위치 로 저장 합 니 다.구체 적 인 코드 는 다음 과 같 습 니 다 MergeSort. java
public class MergeSort {
    public static void main(String[] args){
        int[] a = {49,38,65,97,76,13,27};
        mergeSort(a,0,a.length-1);
        for (int i = 0; i < a.length; i ++){
            System.out.print( a[i] + "\t" );
        }
    }

    private static void mergeSort(int[] a, int p, int r) {
        if (p

출력:
13	27	38	49	65	76	97

알고리즘 시간 복잡 도 분석 병합 정렬 알고리즘 의 가장 좋 고 최 악, 평균 시간 복잡 도 는 O (nlogn) 이 며 알고리즘 의 보조 저장 공간 복잡 도 O (n) 는 안정성 을 가지 고 배열 서열 의 길이 가 클 때 비교적 좋다.
RESTful이 항상 사용자에게 가장 좋은 것은 아닙니다.
동일한 계정 내 S3 어플리케이션

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage