Java에서 병합 정렬 알고리즘을 구현하는 방법 예제에 대한 자세한 설명

이 글에서는 주로 Java의 병합 정렬 알고리즘에 대한 자세한 설명을 소개합니다. 병합 정렬 알고리즘은 O(N logN)의 시간 복잡도를 갖는 정렬 알고리즘이므로 다음과 같습니다. 일상 생활과 업무에서 매우 중요하며, 필요한 친구는 java.elements의 병합 정렬 알고리즘에 대한 자세한 설명을 참조할 수 있으며, 각 요소는 단일 개체이며, 인접한 두 요소는 다음과 같습니다. 작은 것에서 큰 것 또는 큰 것에서 작은 것까지 전체를 형성합니다. 각 전체는 하나 또는 두 개의 요소를 포함하며, 각 전체가 정렬되므로 전체가 계속해서 "병합"됩니다. 병합 후 각 전체에는 3~4개의 요소가 포함되며, 모든 전체가 하나의 전체로 병합될 때까지 인접한 전체가 계속 병합되며 최종 전체는 원래 배열을 정렬한 결과입니다.

 인접한 전체의 경우 병합의 아이디어는 두 전체 중 가장 작은 요소를 가져와(실제로 오름차순으로 정렬되어 있다고 가정) 매번 새 배열에 넣은 다음 순서대로 반복하는 것입니다. 결국 두 전체의 요소를 가져온 후에 전체가 오름차순으로 정렬됩니다. 병합 과정은 두 개의 오름차순 덱 A와 B를 갖는 것과 같습니다(그림 참조). 매번 맨 위에서 하나의 요소를 가져와서 덱 C에 배치합니다.

그림에서 볼 수 있듯이 , 두 개의 인접한 전체 A와 B에 대해 그 안에 있는 요소는 오름차순으로 정렬됩니다. 이제 임시 배열 C가 있고 A와 B의 맨 위에 있는 두 요소가 비교되고 더 작은 요소가 제거됩니다. C를 입력합니다. 검색된 요소 전체에 대해 요소를 가리키는 아래 첨자를 한 비트 아래로 이동합니다. 계속해서 두 전체 중 더 작은 최상위 요소를 꺼내 C에 넣습니다. 루프는 차례로 특정됩니다. 전체 요소를 가져오고 다른 전체 요소를 모두 C로 직접 이동합니다. 전체 C에 대해 A와 B를 정렬하여 얻습니다. A와 B는 두 개의 인접한 전체이므로 결국 C의 요소를 A와 B로 구성된 공통 전체에 복사하면 됩니다. 이는 A와 B를 병합하고 동시에 정렬하는 목적도 달성합니다.排 다음은 병합 및 정렬의 특정 알고리즘입니다.

public class MergeSort {
 public static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] arr) {
  AnyType[] tmp = ((AnyType[]) new Comparable[arr.length]);
  mergeSort(arr, 0, arr.length - 1, tmp);
 }

 private static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] arr, int start, int end, AnyType[] tmp) {
  if (start < end) {
   int mid = (start + end) >> 1;
   mergeSort(arr, start, mid, tmp);
   mergeSort(arr, mid + 1, end, tmp);
   merge(arr, start, mid, end, tmp);
  }
 }

 private static <AnyType extends Comparable<? super AnyType>> void merge(AnyType[] arr, int start, int mid, int end, AnyType[] tmp) {
  int i = start, j = mid + 1, k = start;
  while (i <= mid && j <= end) {
   if (arr[i].compareTo(arr[j]) < 0) {
    tmp[k++] = arr[i++];
   } else {
    tmp[k++] = arr[j++];
   }
  }

  while (i <= mid) {
   tmp[k++] = arr[i++];
  }

  while (j <= end) {
   tmp[k++] = arr[j++];
  }

  for (int m = start; m <= end; m++) {
   arr[m] = tmp[m];
  }
 }
}

코드에는 두 가지 주요 방법이 있습니다. 첫 번째 방법은 재귀 방법의 경우 이 방법의 기능 정의를 명확히 하세요. 여기서 이 재귀적 방법의 목적은 들어오는 배열의 시작과 끝 사이의 요소를 정렬하는 것이며 tmp는 보조 배열입니다. 이 메서드의 구체적인 구현에서는 먼저 계속해서 재귀를 호출하여 시작과 중간 사이의 요소를 정렬한 다음 재귀를 호출하여 중간에서 끝 사이의 요소를 정렬하는 것임을 알 수 있습니다. 처음부터 중간까지, 중간부터 끝까지 정렬되는데 이때 두 번째 메소드를 호출해야 합니다.

         

  두 번째 방법의 기능은 정렬된 두 부분을 병합하는 것입니다

첫 번째 방법의 경우 마지막 단계는 이 방법의 이전 두 단계에서 정렬된 부분을 병합하는 두 번째 방법을 실행하는 것입니다. . 두 번째 방법의 구현 아이디어는 앞에서 설명한 것과 동일합니다. 두 개의 카드 더미 중 가장 작은 요소를 가져와 임시 배열에 넣습니다. 두 번째 데크에 배열을 추가하고 마지막으로 임시 배열의 요소를 원래 배열에 다시 넣습니다.

이번 글에서는 주로 병합 정렬의 개념을 자세히 설명하고, 구체적인 코드와 아이디어를 바탕으로 코드를 분석합니다.

위 내용은 Java에서 병합 정렬 알고리즘을 구현하는 방법 예제에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!