使用Java实现归并排序算法

归并排序的Java实现¶

什么是归并排序？¶

归并排序（Merge Sort）是一种基于分治思想的高效排序算法。它的核心思路是将一个大问题分解为多个小问题，解决小问题后再合并结果。具体来说，就是先将数组分成两半，递归地对每一半进行排序，最后将两个有序的子数组合并成一个完整的有序数组。

归并排序的核心步骤¶

归并排序遵循“分而治之”的思想，分为三个步骤：
1. 分解（Divide）：将待排序数组从中间分成左右两个子数组，直到每个子数组只有一个元素（此时自然有序）。
2. 解决（Conquer）：递归地对左右两个子数组进行排序。
3. 合并（Combine）：将两个有序的子数组合并成一个更大的有序数组。

用Java实现归并排序¶

下面通过一个具体的例子来理解如何用Java实现归并排序。我们使用一个简单的整数数组作为示例，逐步讲解代码逻辑。

1. 递归排序方法（mergeSort）¶

首先，我们需要一个递归方法来实现分解和解决步骤。方法的核心逻辑是：
- 如果数组长度小于等于1，直接返回（已经是有序的）。
- 计算数组中间位置，递归排序左右两个子数组。
- 合并两个有序子数组。

public class MergeSort {
    // 归并排序主方法
    public static void mergeSort(int[] arr) {
        // 递归终止条件：数组长度小于等于1时，无需排序
        if (arr.length <= 1) {
            return;
        }
        // 计算中间索引，将数组分成左右两部分
        int mid = arr.length / 2;
        // 递归排序左半部分
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        mergeSort(left);
        // 递归排序右半部分
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);
        mergeSort(right);
        // 合并左右两个有序子数组
        merge(arr, left, right);
    }
}

2. 合并方法（merge）¶

合并是归并排序的关键步骤，需要将两个有序子数组合并为一个有序数组。具体逻辑：
- 使用三个指针分别遍历左子数组、右子数组和合并后的结果数组。
- 比较左右子数组的元素，将较小的元素放入结果数组。
- 将剩余未遍历完的元素直接复制到结果数组。

import java.util.Arrays;

public class MergeSort {
    // ... 省略mergeSort方法 ...

    // 合并两个有序子数组到原数组arr
    private static void merge(int[] result, int[] left, int[] right) {
        int i = 0; // 左子数组指针
        int j = 0; // 右子数组指针
        int k = 0; // 结果数组指针
        // 比较左右子数组元素，将较小值放入结果数组
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result[k] = left[i];
                i++;
            } else {
                result[k] = right[j];
                j++;
            }
            k++;
        }
        // 将左子数组剩余元素复制到结果数组
        while (i < left.length) {
            result[k] = left[i];
            i++;
            k++;
        }
        // 将右子数组剩余元素复制到结果数组
        while (j < right.length) {
            result[k] = right[j];
            j++;
            k++;
        }
    }
}

3. 完整代码与测试¶

将上述方法整合，编写一个完整的Java程序并测试：

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 3, 7, 6, 1, 8};
        System.out.println("排序前：" + Arrays.toString(arr));
        mergeSort(arr);
        System.out.println("排序后：" + Arrays.toString(arr));
    }

    // 归并排序主方法
    public static void mergeSort(int[] arr) {
        if (arr.length <= 1) {
            return;
        }
        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);
        mergeSort(left);
        mergeSort(right);
        merge(arr, left, right);
    }

    // 合并两个有序子数组
    private static void merge(int[] result, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result[k] = left[i];
                i++;
            } else {
                result[k] = right[j];
                j++;
            }
            k++;
        }
        while (i < left.length) {
            result[k] = left[i];
            i++;
            k++;
        }
        while (j < right.length) {
            result[k] = right[j];
            j++;
            k++;
        }
    }
}

运行结果：

排序前：[5, 2, 9, 3, 7, 6, 1, 8]
排序后：[1, 2, 3, 5, 6, 7, 8, 9]

算法分析¶

时间复杂度：
每次合并需要遍历整个数组（O(n)），递归深度为 log n（将数组分解为两半的次数），因此总时间复杂度为 O(n log n)。
空间复杂度：
需要额外的临时数组（长度为 n）存储合并结果，空间复杂度为 O(n)。
稳定性：
归并排序是稳定排序（相等元素的相对顺序不会改变），因为合并时若两元素相等，会优先取左子数组的元素放入结果数组。

总结¶

归并排序通过“分而治之”的思想实现高效排序，时间复杂度为 O(n log n)，适合处理大数据量的排序场景。虽然需要额外空间，但逻辑清晰且易于理解，是初学者学习分治算法的经典案例。通过递归分解和合并有序子数组，最终得到完整的有序数组。