Java归并排序详解（手把手教你掌握高效排序算法）

归并排序的步骤

1. 分解：将数组从中间分成两半，递归地对左右两部分进行排序。
2. 合并：将两个已排序的子数组合并成一个有序数组。

Java实现归并排序

下面是一个完整的Java归并排序代码示例，包含主方法和辅助合并函数：

public class MergeSort {    // 归并排序主方法    public static void mergeSort(int[] arr, int left, int right) {        if (left < right) {            int mid = left + (right - left) / 2;                        // 递归排序左半部分            mergeSort(arr, left, mid);                        // 递归排序右半部分            mergeSort(arr, mid + 1, right);                        // 合并两个有序部分            merge(arr, left, mid, right);        }    }    // 合并两个有序子数组    public static void merge(int[] arr, int left, int mid, int right) {        // 创建临时数组        int n1 = mid - left + 1;        int n2 = right - mid;                int[] leftArr = new int[n1];        int[] rightArr = new int[n2];                // 复制数据到临时数组        for (int i = 0; i < n1; i++) {            leftArr[i] = arr[left + i];        }        for (int j = 0; j < n2; j++) {            rightArr[j] = arr[mid + 1 + j];        }                // 合并临时数组回原数组        int i = 0, j = 0, k = left;        while (i < n1 && j < n2) {            if (leftArr[i] <= rightArr[j]) {                arr[k] = leftArr[i];                i++;            } else {                arr[k] = rightArr[j];                j++;            }            k++;        }                // 复制剩余元素        while (i < n1) {            arr[k] = leftArr[i];            i++;            k++;        }        while (j < n2) {            arr[k] = rightArr[j];            j++;            k++;        }    }    // 测试方法    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, 0, arr.length - 1);                System.out.println("排序后：" + java.util.Arrays.toString(arr));    }}  

算法分析

• 时间复杂度：无论最好、最坏还是平均情况，都是 O(n log n)，非常稳定。
• 空间复杂度：O(n)，因为需要额外的临时数组来存储数据。
• 稳定性：归并排序是稳定排序，相等元素的相对位置不会改变。

为什么选择归并排序？

在实际开发中，如果你需要一个时间复杂度稳定且适合大数据量的排序算法，归并排序是非常好的选择。例如 Java 标准库中的 Collections.sort() 在某些情况下就使用了归并排序或其变种（如 TimSort）。

总结

通过本篇Java排序教程，你已经掌握了Java归并排序的基本原理、完整实现以及性能特点。归并排序作为典型的分治算法Java实现，不仅实用，还能帮助你深入理解递归与分治思想。建议你动手敲一遍代码，加深理解！

关键词回顾：Java归并排序、归并排序算法、Java排序教程、分治算法Java。