AcWing算法基础课-787归并排序-Java题解

归并排序是一种有效的排序算法，属于分治法（Divide and Conquer）的一种，它的基本思想是将一个大数组分解成两个小数组，在对这两个小数组分别进行排序后，再将这两个已排序的小数组合并成一个完整的有序数组。归并排序的时间复杂度为O(n log n)，在最坏的情况下依然能够保持这个性能，是一种稳定的排序算法。

在Java中实现归并排序，主要分为三个步骤：分解、排序和合并。下面是一个完整的归并排序的Java代码示例，并附有详细的解释。

public class MergeSort {

    // 主函数，接收数组并调用合并排序方法
    public static void mergeSort(int[] arr) {
        if (arr.length < 2) {
            return; // 如果数组长度小于2，则无需排序
        }
        mergeSort(arr, 0, arr.length - 1);
    }

    // 递归实现的归并排序
    private static void mergeSort(int[] arr, int left, int right) {
        if (left >= right) {
            return; // 单个元素无需排序
        }

        int mid = left + (right - left) / 2; // 找到中间位置
        mergeSort(arr, left, mid); // 递归排序左半部分
        mergeSort(arr, mid + 1, right); // 递归排序右半部分
        merge(arr, left, mid, right); // 合并两个已排序的部分
    }

    // 合并两个排序好的子数组
    private static void merge(int[] arr, 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 (arr[i] <= arr[j]) {
                temp[k++] = arr[i++]; // 选择左边元素
            } else {
                temp[k++] = arr[j++]; // 选择右边元素
            }
        }

        // 将左边未处理完的元素复制到临时数组
        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        // 将右边未处理完的元素复制到临时数组
        while (j <= right) {
            temp[k++] = arr[j++];
        }

        // 将临时数组的内容复制回原数组
        for (i = 0; i < temp.length; i++) {
            arr[left + i] = temp[i];
        }
    }

    // 测试归并排序
    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("排序前：");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        mergeSort(arr); // 调用归并排序

        System.out.println("\n排序后：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

代码解析

1. 主函数 mergeSort(int[] arr)：

2. 首先检查数组的长度，如果少于2，则不需要排序。

3. 递归函数 mergeSort(int[] arr, int left, int right)：

4. 这个函数将数组进行分解，寻找中间点，再分别对左右两部分递归调用自身。

5. 合并函数 merge(int[] arr, int left, int mid, int right)：

6. 这个函数负责将两个已排序的子数组进行合并。我们使用一个临时数组 temp 来存储合并后的结果，然后将结果再拷贝回原数组。

7. 测试代码：

8. 在 main 方法中，我们创建一个乱序的数组，并调用 mergeSort 方法进行排序，最后打印排序前后的数组。

通过上述代码示例与解析，我们可以清楚地了解到归并排序的实现方法。归并排序尤其适合处理大规模数据，且由于其稳定性和较好的时间复杂度，使得它在实际应用中非常广泛。