详解十大经典排序算法（五）：归并排序（Merge Sort）

算法原理

归并排序的核心思想是将一个大的数组分割成多个小的子数组，然后分别对这些子数组进行排序，最后将排序后的子数组合并起来，得到一个有序的大数组。

算法描述

归并排序（Merge Sort）是一种经典的排序算法，其原理基于分治（Divide and Conquer）策略。它的核心思想是将一个大问题分割成多个小问题，解决小问题后再将它们合并以得到最终结果。

具体步骤如下：

1. 分割（Divide）：将待排序的数组递归地分割成两个子数组，直到每个子数组只包含一个元素。
2. 排序（Conquer）：对每个子数组进行排序，通常使用递归来排序。
3. 合并（Merge）：将排好序的子数组合并成一个新的有序数组。
4. 重复步骤2和步骤3，直到整个数组都被排序。

动画演示

代码实现

public static void mergeSort(int[] array) {
        if (array == null || array.length <= 1) {
            return; // 如果数组为空或只有一个元素，无需排序
        }
        int[] temp = new int[array.length]; // 创建一个临时数组来辅助排序
        mergeSort(array, 0, array.length - 1, temp); // 调用归并排序函数
    }

    private static void mergeSort(int[] array, int left, int right, int[] temp) {
        //直到每个子数组只包含一个元素 即：left == right
        //也就是说最小排序单位是长度为2的数组，当长度为2时，此时无法再递归，而进行排序
        if (left < right) {
            int mid = (left + right) / 2;
            // 对左半部分进行归并排序
            mergeSort(array, left, mid, temp);
            // 对右半部分进行归并排序
            mergeSort(array, mid + 1, right, temp);
            // 合并两个有序数组
            merge(array, left, mid, right, temp);
        }
    }

    private static void merge(int[] array, int left, int mid, int right, int[] temp) {
        int i = left; // 左数组的起始索引
        int j = mid + 1; // 右数组的起始索引
        int k = left; // 临时数组的起始索引

        // 比较左右两个数组的元素，将较小的元素放入临时数组
        while (i <= mid && j <= right) {
            if (array[i] <= array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }

        // 将左数组剩余部分复制到临时数组
        while (i <= mid) {
            temp[k++] = array[i++];
        }

        // 将右数组剩余部分复制到临时数组
        while (j <= right) {
            temp[k++] = array[j++];
        }

        // 将临时数组的元素复制回原数组
        for (i = left; i <= right; i++) {
            array[i] = temp[i];
        }
    }

算法复杂度

• 平均时间复杂度为 O(n log n)，其中 n 是待排序数组的大小。
• 最好情况和最坏情况下的时间复杂度也都是 O(n log n)。
• 归并排序需要额外的空间来存储临时数组，在最坏情况下需要与输入数组一样大的空间，因此空间复杂度是 O(n)。

归并排序的优化方式

上述代码实现了基本的归并排序算法，但它在合并过程中存在一个潜在的优化点。在归并排序的合并阶段，将左右两个有序数组合并为一个有序数组时，可以通过判断左边数组的最大值和右边数组的最小值来优化合并操作，避免不必要的比较。

这个优化点可以通过添加一个条件来判断是否需要合并，如果左边数组的最大值小于等于右边数组的最小值，则无需合并，因为两个数组已经是有序的，不需要进行额外的比较和移动。

private static void merge(int[] array, int left, int mid, int right, int[] temp) {
    int i = left; // 左数组的起始索引
    int j = mid + 1; // 右数组的起始索引
    int k = left; // 临时数组的起始索引

    // 如果左数组的最大值小于等于右数组的最小值，则无需合并，直接返回
    if (array[mid] <= array[j]) {
        return;
    }

    // 比较左右两个数组的元素，将较小的元素放入临时数组
    while (i <= mid && j <= right) {
        if (array[i] <= array[j]) {
            temp[k++] = array[i++];
        } else {
            temp[k++] = array[j++];
        }
    }

    // 将左数组剩余部分复制到临时数组
    while (i <= mid) {
        temp[k++] = array[i++];
    }

    // 将右数组剩余部分复制到临时数组
    while (j <= right) {
        temp[k++] = array[j++];
    }

    // 将临时数组的元素复制回原数组
    for (i = left; i <= right; i++) {
        array[i] = temp[i];
    }
}

这个优化逻辑在判断左右两个子数组已经有序时，可以避免不必要的比较和赋值操作，提升归并排序的性能。

归并排序核心就是 递归，分治，记住这两个词就能大致理解这个算法，递归思想真的很重要，不容易完全理解，还得继续练习-_-

相关概念
• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
• 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。