Java 병합 정렬 구현 단계의 단계별 분석

Java 병합 정렬 코드 구현 프로세스의 단계별 분석

소개:
병합 정렬은 배열을 두 개의 작은 배열로 나눈 다음 두 배열을 각각 정렬하고 마지막으로 분할 정복 알고리즘입니다. 두 개의 정렬된 배열을 하나의 정렬된 배열로 병합합니다. 이 기사에서는 Java에서 병합 정렬의 구현 프로세스를 단계별로 분석하고 구체적인 코드 예제를 제공합니다.

1. 기본 아이디어:
   병합 정렬의 기본 아이디어는 정렬할 배열을 두 개의 작은 하위 배열로 재귀적으로 분할한 다음 두 개의 하위 배열을 정렬하고 순서가 지정된 배열로 병합하는 것입니다. 이 프로세스는 가장 작은 하위 배열에 요소가 하나만 있을 때까지 재귀적으로 계속되며, 그런 다음 정렬된 하위 배열을 병합하여 정렬이 완료됩니다.
2. 구현 과정:
   다음은 Java에서 병합 정렬을 구현하는 과정입니다.

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 m = 0; m < temp.length; m++) {
            array[left + m] = temp[m];
        }
    }

    // 测试
    public static void main(String[] args) {
        int[] array = {8, 5, 2, 9, 5, 6, 3};
        int n = array.length;

        MergeSort mergeSort = new MergeSort();
        mergeSort.mergeSort(array, 0, n - 1);

        System.out.println("归并排序结果：");
        for (int i = 0; i < n; i++) {
            System.out.print(array[i] + " ");
        }
    }
}

3. 설명 예:
   위 코드에서 mergeSort 메소드는 병합 정렬의 입력 함수이고, 정렬할 배열과 배열의 왼쪽 및 오른쪽 경계를 받습니다. 이 함수에서는 먼저 왼쪽과 오른쪽 경계가 분할 조건(예: 왼쪽 )을 충족하는지 확인합니다. 그렇다면 배열의 중간점을 찾아 <code>mergeSort 함수는 왼쪽과 오른쪽을 정렬합니다. 마지막으로 <code>merge 함수를 호출하여 두 개의 정렬된 하위 배열을 하나의 정렬된 배열로 병합합니다. mergeSort方法是归并排序的入口函数，它接收一个待排序的数组以及数组的左右边界。在该函数中，我们首先判断左右边界是否满足拆分的条件（即left ），如果满足，则找出数组的中点，并递归调用<code>mergeSort函数对左半部分和右半部分进行排序。最后，调用merge函数将两个有序的子数组合并为一个有序的数组。

merge函数中，我们创建一个临时数组来存储合并后的子数组，然后定义三个指针i、j、k

merge 함수에서는 병합된 하위 배열을 저장할 임시 배열을 만든 다음 세 개의 포인터 i, j를 정의합니다. , k는 각각 왼쪽 절반의 시작 위치, 오른쪽 절반의 시작 위치 및 임시 배열의 시작 위치를 가리킵니다. 왼쪽 절반과 오른쪽 절반의 요소 크기를 비교하고 더 작은 요소를 임시 배열에 넣은 다음 해당 포인터를 1비트 뒤로 이동합니다. 특정 하위 배열의 모든 요소가 임시 배열에 배치되면 하위 배열의 나머지 요소를 임시 배열의 끝에 복사합니다. 마지막으로 임시 배열의 요소를 원래 배열로 다시 복사합니다.
4. 
   
요약:

병합 정렬 알고리즘은 정렬할 배열을 더 작은 하위 배열로 재귀적으로 분할하고 이러한 정렬된 하위 배열을 병합하여 전체 정렬을 수행합니다. 실제로 병합 정렬 알고리즘의 시간복잡도는 O(nlogn)로 다른 정렬 알고리즘에 비해 안정성과 확장성이 우수합니다. Java 병합 정렬 코드의 구현 프로세스를 점진적으로 분석함으로써 기본 아이디어와 구현 방법을 더 잘 이해할 수 있습니다. 🎜🎜

위 내용은 Java 병합 정렬 구현 단계의 단계별 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!