Java归并排序详解（分治算法入门与实现）

Java 实现归并排序

下面是一个完整的 Java 归并排序实现，代码结构清晰，注释详细，适合初学者学习。

public class MergeSort {    // 主函数：启动归并排序    public static void mergeSort(int[] arr) {        if (arr == null || arr.length <= 1) {            return; // 空数组或单元素数组无需排序        }        int[] temp = new int[arr.length];        mergeSortHelper(arr, temp, 0, arr.length - 1);    }    // 递归分治函数    private static void mergeSortHelper(int[] arr, int[] temp, int left, int right) {        if (left < right) {            int mid = left + (right - left) / 2; // 防止整数溢出            // 分：递归排序左半部分            mergeSortHelper(arr, temp, left, mid);            // 分：递归排序右半部分            mergeSortHelper(arr, temp, mid + 1, right);            // 治：合并两个已排序的部分            merge(arr, temp, left, mid, right);        }    }    // 合并函数：将 [left, mid] 和 [mid+1, right] 合并为有序数组    private static void merge(int[] arr, int[] temp, int left, int mid, int right) {        // 将原数组复制到临时数组        for (int i = left; i <= right; i++) {            temp[i] = arr[i];        }        int i = left;      // 左子数组起始索引        int j = mid + 1;   // 右子数组起始索引        int k = left;      // 原数组写入位置        // 比较左右子数组元素，按顺序写回原数组        while (i <= mid && j <= right) {            if (temp[i] <= temp[j]) {                arr[k++] = temp[i++];            } else {                arr[k++] = temp[j++];            }        }        // 复制左子数组剩余元素（如果有的话）        while (i <= mid) {            arr[k++] = temp[i++];        }        // 复制右子数组剩余元素（如果有的话）        while (j <= right) {            arr[k++] = temp[j++];        }    }    // 测试示例    public static void main(String[] args) {        int[] arr = {38, 27, 43, 3, 9, 82, 10};        System.out.println("排序前：" + java.util.Arrays.toString(arr));        mergeSort(arr);        System.out.println("排序后：" + java.util.Arrays.toString(arr));    }}

代码解析

上述代码中：

• mergeSort 是对外提供的入口方法，负责初始化临时数组并调用递归函数。
• mergeSortHelper 执行分治逻辑：不断将数组二分，直到子数组长度为1。
• merge 负责将两个有序子数组合并成一个有序数组，这是归并排序的核心。

时间与空间复杂度

- 时间复杂度：无论最好、最坏还是平均情况，归并排序的时间复杂度都是 O(n log n)，非常稳定。

- 空间复杂度：由于需要一个与原数组等长的临时数组，空间复杂度为 O(n)。

为什么选择归并排序？

归并排序具有以下优点：

• 稳定：相等元素的相对位置不会改变。
• 效率高：时间复杂度始终为 O(n log n)。
• 适合大数据量：常用于外部排序（如处理无法全部加载到内存的大文件）。

通过本教程，你已经掌握了 Java归并排序 的基本原理和实现方式。归并排序作为 分治算法 的经典案例，不仅帮助你理解递归思想，也为学习其他高级算法打下坚实基础。

希望这篇 归并排序教程 对你有所帮助！继续练习，你将熟练掌握这一重要的 Java排序算法。