递归与分治算法（一）：归并排序-CSDN博客

在算法和数据结构的世界里，排序算法扮演着至关重要的角色。它是许多计算机程序和系统的基础。排序不仅仅是对数据进行简单的排列，更是优化程序执行效率、增强数据处理能力的重要手段。在众多排序算法中，**归并排序（Merge Sort）**是一种典型的分治法（Divide and Conquer）算法，它通过递归地将数组拆分并最终合并排好序的子数组来实现排序。

本文将深入剖析归并排序的原理、性能、优缺点，结合Java代码示例详细讲解如何实现归并排序，同时通过表格对比其他排序算法的特性，帮助读者更好地理解和掌握该算法。

2. 归并排序的基本概念

2.1 算法思想

归并排序的基本思想是采用分治法，通过递归地将一个大的数组拆分为较小的数组，直到数组中只剩下一个元素。接着，合并这些小数组，并通过合并过程将数据排序。具体过程如下：

分解（Divide）：将原始数组分割成两半，递归地对每个子数组进行排序，直到每个子数组只包含一个元素。
合并（Merge）：将已排序的子数组合并成一个有序的数组。在合并过程中，通过比较子数组中的元素，确保合并后的数组仍然是有序的。

归并排序采用的是自上而下的递归方式，也可以通过迭代的方式进行优化。

2.2 时间复杂度和空间复杂度

时间复杂度：归并排序的时间复杂度是 O(n log n)，其中 n 是数组的长度。由于每次分割都将数组分成两半，而合并操作需要遍历整个数组，因此归并排序的时间复杂度在最坏、最好和平均情况下都是 O(n log n)。
空间复杂度：归并排序的空间复杂度是 O(n)，因为在合并时需要额外的空间来存储中间数组。

归并排序是一种稳定的排序算法，这意味着如果有多个相同的元素，它们的相对顺序在排序后不会改变。

2.3 归并排序的稳定性

归并排序的稳定性源于合并过程中比较元素的顺序。如果两个元素相等，归并排序会保留它们在原数组中的相对顺序。这对于一些特定场景，如对对象数组进行排序时，尤其重要。

3. 归并排序的Java实现

3.1 递归实现

递归实现是归并排序最常见的实现方式，下面是一个基本的递归版归并排序的Java代码：

public class MergeSort {

    // 主方法
    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("排序前：");
        printArray(arr);
        
        mergeSort(arr, 0, arr.length - 1);
        
        System.out.println("\n排序后：");
        printArray(arr);
    }

    // 递归实现归并排序
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            // 找到中点
            int mid = (left + right) / 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[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;

        // 合并两个子数组
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }

        // 复制剩余元素
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= right) {
            temp[k++] = arr[j++];
        }

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

    // 打印数组
    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

3.2 代码解释

mergeSort 方法是递归的核心，它会不断地将数组拆分成两半，直到每个子数组只有一个元素。
merge 方法将两个已排序的子数组合并成一个有序的数组。它使用了一个临时数组 temp 来存储合并后的结果。
printArray 方法用于打印数组。

3.3 运行效果

在上面的代码中，输入数组 {38, 27, 43, 3, 9, 82, 10}，排序前后的结果如下：

排序前：
38 27 43 3 9 82 10 

排序后：
3 9 10 27 38 43 82

4. 归并排序与其他排序算法对比

为了更好地理解归并排序的优缺点，下面将其与其他常见的排序算法进行对比，主要对比快速排序（Quick Sort）、插入排序（Insertion Sort）和冒泡排序（Bubble Sort）。

排序算法	时间复杂度（最好）	时间复杂度（最坏）	空间复杂度	稳定性	适用场景
归并排序	O(n log n)	O(n log n)	O(n)	稳定	大规模数据排序
快速排序	O(n log n)	O(n^2)	O(log n)	不稳定	小到中规模数据
插入排序	O(n)	O(n^2)	O(1)	稳定	小规模数据
冒泡排序	O(n)	O(n^2)	O(1)	稳定	小规模数据