Java를 사용하여 병합 정렬을 구현하는 방법-Java시작하기-php.cn

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

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

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

핵심 아이디어

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

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

구현 코드:

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를 사용하여 병합 정렬을 구현하는 방법