Java의 병합 정렬 프로그램-java지도 시간-php.cn

Java의 병합 정렬 프로그램

王林

풀어 주다： 2024-08-30 15:32:25

원래의

631명이 탐색했습니다.

Java의 병합 정렬 프로그램은 가장 널리 사용되고 효율적인 알고리즘 중 하나입니다. 병합 정렬은 주어진 문제를 여러 하위 문제로 나누고 각 하위 문제를 독립적으로 해결하는 분할 정복 기술을 기반으로 합니다. 하위 문제가 해결되면 결과를 결합하여 문제에 대한 최종 솔루션을 얻습니다. 병합 정렬 알고리즘은 주요 문제가 아닌 하위 문제를 다루기 때문에 재귀를 사용하여 구현할 수 있습니다.

병합 정렬은 어떻게 작동하나요?

병합 정렬 알고리즘을 사용하여 정렬해야 하는 정렬되지 않은 배열을 고려해 보겠습니다. 값이 18, 8, 4, 13, 10, 12, 7, 11인 배열을 정렬하는 단계는 다음과 같습니다.

무료 소프트웨어 개발 과정 시작

웹 개발, 프로그래밍 언어, 소프트웨어 테스팅 등

첫 번째 단계에서는 입력 배열을 하위 배열로 나눌 기준이 되는 피벗 요소를 찾는 것입니다.
요소 13이 피벗으로 선택되었다고 가정해 보겠습니다. 따라서 원래 배열은 두 개의 하위 배열로 나누어집니다. 첫 번째 하위 배열에는 18, 8, 4, 13이 포함되고 두 번째 하위 배열에는 나머지 요소 10, 12, 7, 11이 포함됩니다.
2단계에서 얻은 하위 배열은 1단계와 같이 더 세분화되며 계속됩니다.
기본 배열이 단일 요소가 있는 하위 배열로 분할되면 병합된 요소가 정렬된 순서로 정렬되도록 이러한 하위 배열을 다시 병합하기 시작합니다.
실제 분할 정복이 작동하는 방식은 다음과 같습니다.

Java의 병합 정렬 프로그램

다음은 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의 병합 정렬 프로그램

병합 정렬은 언제 사용해야 하나요?

병합 정렬은 다음 시나리오에서 사용할 수 있습니다.

정렬할 데이터 구조가 랜덤 액세스를 지원하지 않는 경우 병합 정렬이 유용하고 효율적일 수 있습니다.
높은 수준의 병렬 처리가 필요한 경우 병렬로 실행되는 여러 프로세스를 사용하여 서로 다른 하위 문제를 독립적으로 해결할 수 있으므로 병합 정렬을 사용할 수 있습니다.
목록을 병합하는 동안 포인터가 쉽게 변경될 수 있으므로 연결 목록으로 작업할 때 병합 정렬이 더 빠릅니다.
병합 정렬은 안정적인 정렬로 간주될 수 있습니다. 즉, 배열의 동일한 요소가 서로에 대해 원래 위치를 유지한다는 의미입니다. 높은 안정성이 필요한 경우 병합 정렬을 사용할 수 있습니다.

병합 정렬의 복잡성 분석

병합 정렬의 분석 복잡성은 다음과 같습니다.

병합 정렬은 재귀 알고리즘이며 병합 정렬은 배열을 두 개의 동일한 절반으로 나누고 이를 병합하는 데 선형 시간이 걸리기 때문에 세 가지 경우(최악, 최고 및 평균) 모두에서 시간 복잡도는 O(n*log n)입니다. .
병합 정렬의 공간 복잡도는 재귀적 접근 방식으로 작동하므로 O(n)입니다. 따라서 병합 정렬은 빠르고 공간적이며 시간 효율적인 알고리즘으로 간주될 수 있습니다.

병합 정렬과 다른 알고리즘 비교

아래에서는 병합 정렬과 다른 알고리즘을 비교합니다.

힙 정렬은 병합 정렬과 시간 복잡도가 동일하지만 병합 정렬의 O(n) 대신 O(1) 보조 공간만 필요합니다. 따라서 힙 정렬은 병합 정렬보다 공간 효율적입니다.
빠른 정렬 구현은 일반적으로 RAM 기반 배열 정렬 시 병합 정렬보다 성능이 뛰어납니다.
병합 정렬은 포인터가 쉽게 변경될 수 있으므로 연결 목록으로 작업할 때 빠른 정렬 및 힙 정렬 알고리즘보다 성능이 뛰어납니다.