图解Java经典算法归并排序的原理与实现

算法原理

归并排序是一种基于分治思想的排序算法，它将一个大的问题分解成若干个子问题，然后将子问题拆分到足够小的规模，最后对每个小问题进行解决，最终合并所有解决得到原始问题的解决方案。归并排序的执行过程可以简单地描述为两个步骤，分别为“分”和“治”。

分

归并排序的第一个步骤是分解，它将原始数组分解成若干个子数组，每个子数组包含 n/2 个元素的子问题。这个过程一直重复直到每个子数组包含一个或零个元素。为了更好地说明这个过程，下面是一个示例：

假设我们有以下未排序的数组：

[23, 1, 45, 78, 87, 56, 12, 57]

我们使用归并排序对该数组进行排序，这个过程可以分成以下几个步骤：

1. 分解：将原始数组分解成若干个子数组

   [23, 1, 45, 78, 87, 56, 12, 57] -> [23, 1, 45, 78] [87, 56, 12, 57]
[23, 1, 45, 78] -> [23, 1] [45, 78]
[23, 1] -> [23] [1]
[45, 78] -> [45] [78]
[87, 56, 12, 57] -> [87, 56] [12, 57]
[87, 56] -> [87] [56]
[12, 57] -> [12] [57]

2. 治：合并每个子数组，将它们按照从小到大的顺序组合起来，获得最终的排序结果

   [23] [1] -> [1, 23]
[45] [78] -> [45, 78]
[87] [56] -> [56, 87]
[12] [57] -> [12, 57]
[1, 23] [45, 78] -> [1, 23, 45, 78]
[12, 57] [56, 87] -> [12, 56, 57, 87]
[1, 23, 45, 78] [12, 56, 57, 87] -> [1, 12, 23, 45, 56, 57, 78, 87]

算法实现

下面是归并排序的Java代码实现。在本示例中，mergeSort 方法接收一个整数类型的数组作为输入，并返回一个已排序的数组。

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {23, 1, 45, 78, 87, 56, 12, 57};
        int[] sortedArr = mergeSort(arr);
        System.out.println(Arrays.toString(sortedArr));
    }

    public static int[] mergeSort(int[] arr) {
        if (arr.length <= 1) {
            return arr;
        }

        int[] left = new int[arr.length / 2];
        int[] right = new int[arr.length - left.length];

        System.arraycopy(arr, 0, left, 0, left.length);
        System.arraycopy(arr, left.length, right, 0, right.length);

        left = mergeSort(left);
        right = mergeSort(right);

        return merge(left, right);
    }

    private static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int leftIdx = 0;
        int rightIdx = 0;
        int resIdx = 0;

        while (leftIdx < left.length && rightIdx < right.length) {
            if (left[leftIdx] < right[rightIdx]) {
                result[resIdx++] = left[leftIdx++];
            } else {
                result[resIdx++] = right[rightIdx++];
            }
        }

        while (leftIdx < left.length) {
            result[resIdx++] = left[leftIdx++];
        }

        while (rightIdx < right.length) {
            result[resIdx++] = right[rightIdx++];
        }

        return result;
    }
}

在上面的实现中，我们使用了递归的方式实现了分治的过程。当传入的数组小于等于一个元素时，我们直接返回该数组，否则，我们将该数组分成 left 和 right 两个数组，然后分别对它们调用 mergeSort 方法，递归地将 left 和 right 拆分直到长度为 1。在每次递归结束后，我们将 left 和 right 合并到同一个数组里面，并按照大小顺序排序。

示例说明

示例 1：普通数组排序

下面是一个普通的未排序数组：

[23, 1, 45, 78, 87, 56, 12, 57]

我们使用上面给出的 MergeSort Java类对该数组进行排序，最终排序结果为：

[1, 12, 23, 45, 56, 57, 78, 87]

示例 2：带有重复元素的数组排序

下面是另一个未排序的数组，里面包含重复元素：

[23, 1, 12, 78, 87, 56, 12, 57]

我们使用 MergeSort 对该数组进行排序，最终会得到以下结果：

[1, 12, 12, 23, 56, 57, 78, 87]

正如我们所期望的，该算法能够正确地处理重复元素，而不会对重复元素顺序进行错误的调整。