자바 데이터 구조 정렬 알고리즘 (2) 병합 정렬

이 글에서는 주로 Java 데이터 구조 정렬 알고리즘의 병합 정렬을 소개합니다. 구체적인 예를 바탕으로 병합 정렬의 원리, 구현 기술 및 관련 주의 사항을 자세히 분석합니다. 자바 데이터 구조 정렬 알고리즘 병합 정렬. 참고하실 수 있도록 자세한 내용은 다음과 같습니다.

앞서 언급한 정렬 방식은 모두 키워드 크기에 따라 레코드 그룹을 순서대로 정렬하는 것입니다. 병합을 기반으로 두 개를 결합합니다. 두 개 이상의 순서 목록을 새로운 순서 목록으로 병합

병합 정렬 알고리즘:초기 시퀀스에 n개의 레코드가 포함되어 있다고 가정하고 먼저 이 n개의 레코드를 n개의 순서가 지정된 하위 시퀀스로 처리합니다. 각 하위 시퀀스는 1이고, 쌍으로 병합되어 길이가 2인 n/2개의 정렬된 하위 시퀀스를 얻습니다(n이 홀수인 경우 마지막 시퀀스의 길이는 1입니다). 이를 바탕으로 길이 2의 순서화된 서브 시퀀스를 밝게 병합하여 길이 4의 순서 있는 여러 서브 시퀀스를 얻습니다. 길이 n의 정렬된 시퀀스를 얻을 때까지 이를 반복합니다. 이 방법을 2방향 병합 정렬이라고 합니다(기본 작업은 정렬할 시퀀스에서 두 개의 인접한 정렬된 하위 시퀀스를 정렬된 시퀀스로 병합하는 것입니다).

알고리즘 구현 코드는 다음과 같습니다.

package exp_sort;
public class MergeSort {
  /**
   * 相邻两个有序子序列的合并算法
   *
   * @param src_array
   * @param low
   * @param high
   * @param des_array
   */
  public static void Merge(int src_array[], int low, int high,
      int des_array[]) {
    int mid;
    int i, j, k;
    mid = (low + high) / 2;
    i = low;
    k = 0;
    j = mid + 1;
    // compare two list
    while (i <= mid && j <= high) {
      if (src_array[i] <= src_array[j]) {
        des_array[k] = src_array[i];
        i = i + 1;
      } else {
        des_array[k] = src_array[j];
        j = j + 1;
      }
      k = k + 1;
    }
    // if 1 have,cat
    while (i <= mid) {
      des_array[k] = src_array[i];
      k = k + 1;
      i = i + 1;
    }
    while (j <= high) {
      des_array[k] = src_array[j];
      k = k + 1;
      j = j + 1;
    }
    for (i = 0; i < k; i++) {
      src_array[low + i] = des_array[i];
    }
  }
  /**
   * 2-路归并排序算法，递归实现
   *
   * @param src_array
   * @param low
   * @param high
   * @param des_array
   */
  public static void mergeSort(int src_array[], int low, int high,
      int des_array[]) {
    int mid;
    if (low < high) {
      mid = (low + high) / 2;
      mergeSort(src_array, low, mid, des_array);
      mergeSort(src_array, mid + 1, high, des_array);
      Merge(src_array, low, high, des_array);
    }
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array1[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    int array2[] = new int[array1.length];
    mergeSort(array1, 0, array1.length - 1, array2);
    System.out.println("\n----------after sort-------------");
    for (int ii = 0; ii < array1.length; ii++) {
      System.out.print(array1[ii] + " ");
    }
    System.out.println("\n");
  }
}

코드 설명: 병합 정렬에서는 한 번의 병합 과정에서 양방향 병합 알고리즘을 여러 번 호출해야 합니다. 병합 통과는 O(n)이고, 정렬된 두 목록을 병합하는 시간은 분명히 선형입니다. 왜냐하면 최대 n-1 비교가 이루어지기 때문입니다. 여기서 n은 총 요소 수입니다. 숫자가 여러 개인 경우, 즉 n이 1이 아닌 경우 데이터의 전반부와 후반부를 재귀적으로 병합 및 정렬하여 정렬된 데이터의 두 부분을 얻은 다음 이를 병합합니다.

알고리즘 분석: 이 알고리즘은 병합 연산(두 개의 정렬된 시퀀스를 하나의 시퀀스로 병합하는 연산을 의미하는 병합 알고리즘이라고도 함)을 기반으로 하는 효과적인 정렬 알고리즘입니다. 이 알고리즘은

분할 및 정복 방법

(pide 및 Conquer)의 매우 일반적인 응용 프로그램입니다. 문제를 몇 가지 작은 문제로 나눈 다음 이를 재귀적으로 해결합니다. 정복 단계는 분할된 단계에서 얻은 답변을 하나로 패치하는 것입니다. 분할 및 정복은 재귀의 매우 강력한 사용입니다. 참고: 퀵 정렬과 힙 정렬에 비해 병합 정렬의 가장 큰 특징은 안정적인 정렬 방법이라는 것입니다. 속도는 퀵 정렬에 이어 두 번째이며 일반적으로 무질서하지만 하위 항목이 상대적으로 정렬된 배열에 사용됩니다.

복잡성: 시간 복잡도:

O(nlogn)

——이 알고리즘의 최고, 최악 및 평균 시간 성능입니다. 공간 복잡도는 O(n)
비교 연산 횟수는 (nlogn) / 2와 nlogn - n + 1 사이입니다. 할당 작업 수는 (2nlogn)입니다. 병합 알고리즘의 공간 복잡도는 0(n)
주 메모리 정렬에 사용하기 어렵습니다. (병합 정렬은 더 많은 메모리를 차지합니다. 주요 문제는 정렬된 두 테이블을 병합하려면 선형 추가 메모리가 필요하고 데이터 비용도 든다는 것입니다. 임시
배열
에 복사한 다음 다시 복사하는 등의 일부 추가 작업은 정렬 속도를 심각하게 저하시키지만 매우 효율적이며 주로 중요한 내부 정렬 응용 프로그램에 사용됩니다. , 빠른 정렬이 일반적으로 선택됩니다.

병합 작업 단계는 다음과 같습니다. 1단계: 정렬된 두 시퀀스의 합이 되도록 공간을 적용합니다. 이 공간은 병합된 시퀀스를 저장하는 데 사용됩니다.

2단계: 두 개의 포인터를 설정합니다. 초기 위치는 각각 정렬된 두 시퀀스의 시작 위치입니다

3단계: 두 포인터가 가리키는 요소를 비교하고 상대적으로 작은 요소를 선택하여 병합 공간에 넣은 다음 포인터를 다음 위치
특정 포인터가 시퀀스의 끝에 도달할 때까지 3단계를 반복합니다.
다른 시퀀스의 나머지 요소를 모두 병합된 시퀀스의 끝에 직접 복사합니다.

병합 정렬의 단계는 다음과 같습니다. 시퀀스에는 총 n 개의 요소가 있습니다): 시퀀스의 각 요소 복사 두 개의 인접한 숫자가 병합되어 바닥(n/2) 시퀀스를 형성합니다. 정렬 후 각 시퀀스에는 두 개의 요소가 포함됩니다.

위 시퀀스는 다시 병합되어 바닥을 형성합니다. (n/4) 시퀀스, 각각 4개의 요소가 포함되어 있습니다

모든 요소가 정렬될 때까지 2단계를 반복하세요

[관련 권장 사항]

1

Java 데이터 구조 정렬 알고리즘 (1) 트리 선택 정렬

2. Java의 선택 정렬에 대한 자세한 설명( Selection Sort_java) 예제 튜토리얼

3. java 데이터 구조 정렬 알고리즘 (3) 단순 선택 정렬

4. java 데이터 구조 정렬 알고리즘(4) 선택 정렬

위 내용은 자바 데이터 구조 정렬 알고리즘 (2) 병합 정렬의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!