Java의 병합 정렬 알고리즘 구현 및 최적화

Java 병합 정렬 알고리즘의 구현 및 최적화

병합 정렬은 정렬할 시퀀스를 여러 하위 시퀀스로 나누고 각 하위 시퀀스를 정렬하면 최종적으로 순서가 지정된 하위 시퀀스가 ​​되는 것입니다. 전체 순서대로 병합됩니다.

1. 병합 정렬 알고리즘 구현:
   병합 정렬 알고리즘의 구현은 분할 및 정복과 병합의 두 단계로 나눌 수 있습니다.

(1) 분할 및 정복:
먼저 정렬할 수열을 각 하위 수열에 요소가 하나만 있을 때까지 두 부분으로 나눕니다. 그런 다음 이러한 하위 시퀀스는 순서가 지정된 하위 시퀀스로 병합됩니다.

다음은 병합 정렬 알고리즘의 재귀적 구현을 ​​위한 샘플 코드입니다.

public class MergeSort {
    // 归并排序
    public void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            // 递归地对左右两边进行归并排序
            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);
            // 合并两个有序子序列
            merge(array, left, mid, right);
        }
    }

    // 合并两个有序子序列
    public void merge(int[] array, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left; // 左序列指针
        int j = mid + 1; // 右序列指针
        int k = 0; // 临时数组指针

        while (i <= mid && j <= right) {
            if (array[i] <= array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = array[i++];
        }

        while (j <= right) {
            temp[k++] = array[j++];
        }

        for (int l = 0; l < temp.length; l++) {
            array[left + l] = temp[l];
        }
    }
}

(2) 병합:
병합 함수의 기능은 두 개의 정렬된 하위 시퀀스를 정렬된 시퀀스로 병합하는 것입니다. 특정 구현에서는 병합된 결과를 저장하기 위한 임시 배열을 만들어야 합니다. 하위 시퀀스를 탐색할 때 하위 시퀀스의 요소를 비교하고 더 작은 요소를 임시 배열에 넣은 다음 해당 포인터를 이동합니다. 마지막으로 임시 배열의 요소가 원래 배열로 다시 복사됩니다.

2. 병합 정렬 알고리즘 최적화:
   병합 정렬 알고리즘은 재귀 프로세스 중에 많은 임시 하위 시퀀스 배열을 생성하므로 메모리 할당과 해제가 자주 발생하여 알고리즘의 공간 복잡성이 증가합니다. 이러한 오버헤드를 줄이기 위해 다음과 같은 최적화 방법을 통해 병합 정렬 알고리즘의 효율성을 향상시킬 수 있습니다.

(1) 소규모 하위 시퀀스에 삽입 정렬을 사용합니다.
서브 시퀀스의 크기가 상대적으로 작은 경우 삽입 정렬이 더 효율적입니다. 따라서 병합 정렬의 재귀적 과정에서 하위 시퀀스의 크기가 특정 임계값보다 작을 경우 재귀적 과정을 대체하기 위해 삽입 정렬을 사용할 수 있습니다.

public void mergeSort(int[] array, int left, int right) {
    if (left < right) {
        if (right - left <= THRESHOLD) {
            // 子序列的规模小于阈值，采用插入排序
            insertionSort(array, left, right);
        } else {
            int mid = (left + right) / 2;
            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);
            merge(array, left, mid, right);
        }
    }
}

(2) 병합 프로세스 최적화:
병합 프로세스 중에 먼저 두 개의 하위 시퀀스를 두 개의 임시 배열에 저장한 다음 두 개의 임시 배열을 원래 배열에 병합할 수 있습니다. 이렇게 하면 병합 프로세스 중에 임시 배열을 반복적으로 생성하는 것을 방지할 수 있습니다. 동시에 임시 배열의 크기는 고정되어 있으므로 재귀 과정에서 반복 생성을 피하기 위해 클래스의 멤버 변수로 정의할 수 있습니다.

public class MergeSort {
    private int[] temp;

    public void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            if (right - left <= THRESHOLD) {
                insertionSort(array, left, right);
            } else {
                int mid = (left + right) / 2;
                mergeSort(array, left, mid);
                mergeSort(array, mid + 1, right);
                merge(array, left, mid, right);
            }
        }
    }

    public void merge(int[] array, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int k = 0;

        while (i <= mid && j <= right) {
            if (array[i] <= array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = array[i++];
        }

        while (j <= right) {
            temp[k++] = array[j++];
        }

        for (int l = 0; l < k; l++) {
            array[left + l] = temp[l];
        }
    }
}

요약하면 위 내용은 Java 병합 정렬 알고리즘과 그 최적화 방법의 구현입니다. 병합 프로세스를 최적화하고 소규모 하위 시퀀스에 삽입 정렬을 사용하면 병합 정렬 알고리즘의 효율성이 향상되고 공간 오버헤드가 줄어들 수 있습니다. 실제 응용에서는 적절한 최적화 방법을 선택하고 정렬 순서의 특성을 기반으로 합리적인 선택을 하면 알고리즘을 더욱 효율적으로 만들 수 있습니다.

위 내용은 Java의 병합 정렬 알고리즘 구현 및 최적화의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!