> Java > Java시작하기 > Java를 사용하여 병합 정렬을 구현하는 방법

Java를 사용하여 병합 정렬을 구현하는 방법

王林
풀어 주다: 2020-03-30 16:25:51
앞으로
2290명이 탐색했습니다.

Java를 사용하여 병합 정렬을 구현하는 방법

병합 정렬이란 무엇인가요?

병합 정렬은 재귀 및 분할 정복 기술을 사용하여 데이터 시퀀스를 점점 더 작은 반 하위 테이블로 나눈 다음 반 하위 테이블을 정렬하고 마지막으로 재귀 방법을 사용하여 정렬된 반 하위 테이블을 더 작은 반 하위 테이블로 병합합니다. 더 작은 하위 테이블 순서.

핵심 아이디어

두 개의 정렬된 시퀀스를 하나의 큰 정렬된 시퀀스로 병합합니다. 재귀를 통해 레이어가 병합되는데, 이를 병합이라고 합니다.

(권장 튜토리얼: java 빠른 시작)

구현 코드:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

import java.util.Arrays;

 

/**

 * @author god-jiang

 * @date 2020/1/13

 */

//归并排序,时间复杂度为O(N*logN),空间复杂度为O(N)

public class MergeSort {

    public static void MergeSort(int[] arr, int start, int end) {

        //分治的结束条件

        if (start >= end) {

            return;

        }

        //保证不溢出取start和end的中位数

        int mid = start + ((end - start) >> 1);

        //递归排序并且合并

        MergeSort(arr, start, mid);

        MergeSort(arr, mid + 1, end);

        Merge(arr, start, mid, end);

    }

 

    //合并

    public static void Merge(int[] arr, int start, int mid, int end) {

        int[] temp = new int[end - start + 1];

        int p1 = start;

        int p2 = mid + 1;

        int p = 0;

        while (p1 <= mid && p2 <= end) {

            if (arr[p1] > arr[p2]) {

                temp[p++] = arr[p2++];

            } else {

                temp[p++] = arr[p1++];

            }

        }

        while (p1 <= mid) {

            temp[p++] = arr[p1++];

        }

        while (p2 <= end) {

            temp[p++] = arr[p2++];

        }

        for (int i = 0; i < temp.length; i++) {

            arr[i + start] = temp[i];

        }

    }

 

    public static void main(String[] args) {

        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};

        MergeSort(a, 0, a.length - 1);

        System.out.println(Arrays.toString(a));

    }

}

로그인 후 복사

실행 결과:

Java를 사용하여 병합 정렬을 구현하는 방법

권장 관련 비디오 튜토리얼: java 비디오 튜토리얼

위 내용은 Java를 사용하여 병합 정렬을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

관련 라벨:
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿