归并排序（Merge Sort）

归并排序（Merge Sort）是一种分治法（Divide and Conquer）设计思想的经典体现，广泛用于排序问题。它以稳定性强和时间复杂度较低的优点，在处理大规模数据时非常高效。本文将详细介绍归并排序的原理、实现、时间复杂度及其应用。

一、归并排序的基本思想

归并排序的核心思想是“分而治之”：

1. 分解：将原数组递归地分成两个子数组，直到子数组的大小为1。
2. 合并：将两个有序子数组合并为一个有序数组。
3. 递归：不断递归地执行分解和合并操作，直到整个数组有序。

二、归并排序的执行流程

以排序数组 [38, 27, 43, 3, 9, 82, 10] 为例，归并排序的流程如下：

分解阶段

将数组分成两部分：

[38, 27, 43, 3] 和 [9, 82, 10]

继续对每部分递归分解，直到每部分只包含一个元素：

[38], [27], [43], [3], [9], [82], [10]

合并阶段

按照排序规则，将最小单位的数组两两合并为有序数组：

[38] 和 [27] 合并为 [27, 38]
[43] 和 [3] 合并为 [3, 43]
[9] 和 [82] 合并为 [9, 82]

再次合并：

[27, 38] 和 [3, 43] 合并为 [3, 27, 38, 43]
[9, 82] 和 [10] 合并为 [9, 10, 82]

最后合并得到完整的有序数组：

[3, 27, 38, 43] 和 [9, 10, 82] 合并为 [3, 9, 10, 27, 38, 43, 82]

最终结果为 [3, 9, 10, 27, 38, 43, 82]。

三、归并排序的实现

1. 递归实现（Top-Down Approach）

递归实现是归并排序的经典方式，代码如下：

public class MergeSort {

    public static void mergeSort(int[] array, int left, int right) {
        if (left >= right) {
            return; // 数组长度为1时结束递归
        }

        int mid = left + (right - left) / 2;
        // 分解
        mergeSort(array, left, mid);      // 左半部分
        mergeSort(array, mid + 1, right); // 右半部分

        // 合并
        merge(array, left, mid, right);
    }

    private static void merge(int[] array, int left, int mid, int right) {
        int[] temp = new int[right - left + 1]; // 临时数组
        int i = left, j = mid + 1, k = 0;

        // 将两个子数组按顺序合并
        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++];
        }

        // 将排序结果复制回原数组
        System.arraycopy(temp, 0, array, left, temp.length);
    }

    public static void main(String[] args) {
        int[] array = {38, 27, 43, 3, 9, 82, 10};
        mergeSort(array, 0, array.length - 1);

        System.out.println("排序结果: " + java.util.Arrays.toString(array));
    }
}

2. 非递归实现（Bottom-Up Approach）

非递归实现从最小的子数组开始合并，逐步扩展合并范围：

public class MergeSortIterative {

    public static void mergeSort(int[] array) {
        int n = array.length;
        int[] temp = new int[n];

        for (int size = 1; size < n; size *= 2) {
            for (int left = 0; left < n - size; left += 2 * size) {
                int mid = left + size - 1;
                int right = Math.min(left + 2 * size - 1, n - 1);
                merge(array, temp, left, mid, right);
            }
        }
    }

    private static void merge(int[] array, int[] temp, int left, int mid, int right) {
        int i = left, j = mid + 1, k = left;

        while (i <= mid && j <= right) {
            temp[k++] = (array[i] <= array[j]) ? array[i++] : 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];
        }
    }

    public static void main(String[] args) {
        int[] array = {38, 27, 43, 3, 9, 82, 10};
        mergeSort(array);

        System.out.println("排序结果: " + java.util.Arrays.toString(array));
    }
}

四、归并排序的时间复杂度和空间复杂度

• 时间复杂度
  归并排序的时间复杂度为 O(nlog⁡n)，其中：
  • 分解阶段：每次将数组分成两部分，最多分解 log⁡n 次。
  • 合并阶段：每次合并的操作需要 O(n) 的时间。
• 空间复杂度
  • 递归实现：需要额外的空间存储中间结果，空间复杂度为 O(n+log⁡n)（包含递归栈空间）。
  • 非递归实现：仅需要 O(n) 的临时数组空间。

五、归并排序的优缺点

优点

1. 稳定性：归并排序在合并时不会改变相同元素的相对顺序。
2. 性能优越：在大规模数据或链表排序中表现优异。
3. 适用性强：特别适用于外部排序（磁盘或大数据处理）。

缺点

1. 空间开销较大：需要额外的临时数组存储数据。
2. 对小规模数据效率较低：与插入排序相比，归并排序在小数组上不够高效。

六、归并排序的应用场景

• 大数据处理：归并排序在外部排序中被广泛使用，例如对超大文件排序。
• 链表排序：由于链表分割容易，归并排序是链表排序的优选算法。
• 稳定性要求高的场景：如对数据库中的记录按字段排序。

七、总结

归并排序是经典的排序算法，尤其适合需要稳定性和处理大规模数据的场景。尽管在小规模数据上稍显不足，但其优雅的分治思想和强大的适应性，始终使其成为算法学习和工程实践的重要工具。希望通过本文，您对归并排序有了深入的理解，并能将其应用到实际项目中！

PS：可以点击打开“归并排序算法演示”页面亲自体验一下 😊