当前位置：首页 > article >正文

【算法系列】归并排序详解

article 2025/2/27 14:37:35

文章目录

归并排序详解
- 1. 基本原理
- - 1.1 分治法策略
  - 1.2 归并排序步骤
  - 1.3 图解示例
- 2. 时间复杂度与空间复杂度
- - 2.1 时间复杂度
  - 2.2 空间复杂度
- 3. 稳定性
- 4. Java 实现示例
- 5. 归并排序的优点与缺点
- - 5.1 优点
  - 5.2 缺点
- 6. 总结

归并排序详解

归并排序（Merge Sort）是一种基于分治法的经典排序算法。它通过递归地将数组分成较小的子数组，分别对这些子数组进行排序，然后将它们合并以产生最终的有序数组。归并排序以其稳定性和在最坏情况下的高效性能而著称。

1. 基本原理

1.1 分治法策略

归并排序的核心思想是分治法，即将一个问题分解成若干个规模更小但类似的子问题，递归地解决这些子问题，然后将结果合并以得到原问题的解。

1.2 归并排序步骤

分割：将数组不断分割成两个大致相等的部分，直到每个部分只有一个元素。
排序：对每个单独的元素视为已排序的部分。
合并：将两个已排序的子数组合并成一个更大的已排序数组，直到整个数组排序完成。

1.3 图解示例

假设我们有一个数组 [8, 4, 5, 7, 1, 3, 6, 2]，以下是归并排序的过程：
在这里插入图片描述

2. 时间复杂度与空间复杂度

2.1 时间复杂度

最好、平均和最坏情况：O(n log n)
每次分割操作的时间复杂度为 O(log n)，每次合并操作的时间复杂度为 O(n)。

2.2 空间复杂度

空间复杂度：O(n)
需要额外的空间来存储临时数组，在合并过程中使用。

3. 稳定性

归并排序是稳定的排序算法，即相同值的相对位置不会改变。

4. Java 实现示例

public static void mergeSort(int[] arr) {
    int[] temp = new int[arr.length];
    mergeSort(arr, 0, arr.length - 1, temp);
}

private static void mergeSort(int[] arr, int l, int r, int[] temp) {
    if(l < r) {
        int m = (l + r) / 2;
        mergeSort(arr, l, m, temp);
        mergeSort(arr, m + 1, r, temp);
        merge(arr, l, m, r, temp);
    }
}

private static void merge(int[] arr, int l, int m, int r, int[] temp) {
    int i = l; // 左序列指针
    int j = m + 1; // 右序列指针
    int k = l;
    while(i <= m && j <= r) {
        if(arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    // 左序列剩余元素填充至临时数组
    while(i <= m) {
        temp[k++] = arr[i++];
    }

    // 右序列剩余元素填充至临时数组
    while(j <= r) {
        temp[k++] = arr[j++];
    }

    // 将临时数组的数据拷贝至原数组
    k = l;
    while(k <= r) {
        arr[k] = temp[k++];
    }
}