Step by step analysis of the implementation steps of Java merge sort

Step by step analysis of the implementation process of Java merge sort code

Introduction:
Merge sort is a classic divide and conquer algorithm, which divides an array into two smaller ones arrays, then sort the two arrays separately, and finally merge the two sorted arrays into an ordered array. In this article, we will step by step analyze the implementation process of merge sort in Java and provide specific code examples.

1. Basic idea:
   The basic idea of ​​​​merging sort is to recursively split the array to be sorted into two smaller sub-arrays, and then sort the two sub-arrays and merge them is an ordered array. This process will continue recursively until the smallest subarray has only one element, and then the sorting is completed by merging these ordered subarrays.
2. Implementation process:
   The following is the implementation process of merge sort in 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. Example description:
   In the above code, mergeSortMethod is the entry function of merge sort, which receives an array to be sorted and the left and right boundaries of the array. In this function, we first determine whether the left and right boundaries meet the conditions for splitting (i.e. left ). If so, find the midpoint of the array and call <code>mergeSort## recursively. #Function sorts the left half and right half. Finally, call the merge function to merge the two ordered subarrays into one ordered array.

mergeIn the function, we create a temporary array to store the merged sub-array, and then define three pointers i, j, k respectively point to the starting position of the left half, the starting position of the right half and the starting position of the temporary array. We compare the size of the elements in the left half and the right half, put the smaller element into a temporary array, and move the corresponding pointer back one bit. If all elements of a certain subarray are placed in the temporary array, then we copy the remaining elements of the subarray to the end of the temporary array. Finally, we copy the elements in the temporary array back to the original array.

Summary:
4. The merge sort algorithm recursively splits the array to be sorted into smaller sub-arrays, and achieves overall sorting by merging these ordered sub-arrays. In practice, the time complexity of the merge sort algorithm is O(nlogn), and it has better stability and scalability than other sorting algorithms. By gradually analyzing the implementation process of Java merge sort code, we can better understand its basic ideas and implementation methods.
   

The above is the detailed content of Step by step analysis of the implementation steps of Java merge sort. For more information, please follow other related articles on the PHP Chinese website!