Java의 병합 정렬 프로그램은 가장 널리 사용되고 효율적인 알고리즘 중 하나입니다. 병합 정렬은 주어진 문제를 여러 하위 문제로 나누고 각 하위 문제를 독립적으로 해결하는 분할 정복 기술을 기반으로 합니다. 하위 문제가 해결되면 결과를 결합하여 문제에 대한 최종 솔루션을 얻습니다. 병합 정렬 알고리즘은 주요 문제가 아닌 하위 문제를 다루기 때문에 재귀를 사용하여 구현할 수 있습니다.
병합 정렬 알고리즘을 사용하여 정렬해야 하는 정렬되지 않은 배열을 고려해 보겠습니다. 값이 18, 8, 4, 13, 10, 12, 7, 11인 배열을 정렬하는 단계는 다음과 같습니다.
무료 소프트웨어 개발 과정 시작
웹 개발, 프로그래밍 언어, 소프트웨어 테스팅 등
다음은 Java에서 병합 정렬 구현을 보여주는 코드 예제입니다.
코드:
package com.edubca.sorting; public class MergeSort { private int[] array; private int[] tempMergedArr; private int length; public static void main(String a[]){ int[] inputArr = {18, 8, 4, 13, 10, 12, 7, 11}; MergeSort mergeSort = new MergeSort(); mergeSort.sort(inputArr); for(int i:inputArr){ System.out.print(i + " "); } } public void sort(int inputArr[]) { this.array = inputArr; this.length = inputArr.length; this.tempMergedArr = new int[length]; performMergeSort(0, length - 1); } private void performMergeSort(int lowerIndex, int higherIndex) { if (lowerIndex < higherIndex) { int middle = lowerIndex + (higherIndex - lowerIndex) / 2; // Sort the left side of the array call performMergeSort recursively performMergeSort(lowerIndex, middle); // Sort the right side of the array call performMergeSort recursively performMergeSort(middle + 1, higherIndex); // Merge subparts using a temporary array mergeData(lowerIndex, middle, higherIndex); } } private void mergeData (int lowerIndex, int middle, int higherIndex) { for (int i = lowerIndex; i <= higherIndex; i++) { tempMergedArr[i] = array[i]; } int i = lowerIndex; int j = middle + 1; int k = lowerIndex; while (i <= middle && j <= higherIndex) { if (tempMergedArr[i] <= tempMergedArr[j]) { array[k] = tempMergedArr[i]; i++; } else { array[k] = tempMergedArr[j]; j++; } k++; } while (i <= middle) { array[k] = tempMergedArr[i]; k++; i++; } } }
위 코드는 정렬된 배열을 출력으로 생성합니다.
출력:
병합 정렬은 다음 시나리오에서 사용할 수 있습니다.
병합 정렬의 분석 복잡성은 다음과 같습니다.
아래에서는 병합 정렬과 다른 알고리즘을 비교합니다.
이 기사에서는 병합 정렬이 알고리즘과 관련하여 이해해야 할 중요한 개념이라는 결론을 내렸습니다.
위 내용은 Java의 병합 정렬 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!