병합 정렬이란 무엇인가요?
병합 정렬은 재귀 및 분할 정복 기술을 사용하여 데이터 시퀀스를 점점 더 작은 반 하위 테이블로 나눈 다음 반 하위 테이블을 정렬하고 마지막으로 재귀 방법을 사용하여 정렬된 반 하위 테이블을 더 작은 반 하위 테이블로 병합합니다. 더 작은 하위 테이블 순서.
핵심 아이디어
두 개의 정렬된 시퀀스를 하나의 큰 정렬된 시퀀스로 병합합니다. 재귀를 통해 레이어가 병합되는데, 이를 병합이라고 합니다.
(권장 튜토리얼: 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 비디오 튜토리얼
위 내용은 Java를 사용하여 병합 정렬을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!