第5章_归并排序法

授课语音

归并排序（Merge Sort）算法思想与实现

1. 归并排序概述

归并排序（Merge Sort）是一种典型的分治法（Divide and Conquer）算法，它通过将数组不断地分割成子数组，直到每个子数组仅包含一个元素，然后将这些子数组按顺序合并成一个有序的数组，从而实现排序。

1.1 归并排序的核心思想

归并排序的基本思想是分治法，具体步骤如下：

分解：将待排序的数组从中间位置分成两部分。
解决：递归地对这两部分进行归并排序，直到每个子数组只有一个元素。
合并：合并两个已排序的子数组，得到一个有序的数组。

归并排序的时间复杂度为 O(n log n)，空间复杂度为 O(n)，其中 n 是数组的元素个数。

1.2 归并排序的特点

稳定性：归并排序是稳定的排序算法，即如果两个元素相等，它们在排序后的数组中相对位置不变。
时间复杂度：归并排序的时间复杂度是 O(n log n)，无论输入数据如何，性能表现稳定。
空间复杂度：归并排序的空间复杂度是 O(n)，需要额外的空间来存储合并过程中的临时数组。

2. 归并排序的工作原理

归并排序的基本过程可以分为三个部分：分解、排序和合并。

2.1 分解

首先，将待排序的数组分成两半。递归地将每一半再分成两半，直到每个子数组只包含一个元素。这时，所有的子数组都是有序的（因为一个元素自然是有序的）。

2.2 排序

然后，递归地对每个子数组进行排序。在排序的过程中，每个子数组都是独立的，递归结束后，所有的子数组都将是有序的。

2.3 合并

最后，归并排序的关键操作是合并两个已排序的子数组。合并操作通过比较两个子数组的元素，将较小的元素放入一个新数组中，直到所有元素都被放入新数组。此时，新数组就是合并后的有序数组。

3. 归并排序的Java代码实现

3.1 归并排序的Java代码

以下是归并排序的Java代码实现，带有详细的中文注释。

public class MergeSort {

    // 主方法：输入数组并调用归并排序方法
    public static void main(String[] args) {
        int[] array = {38, 27, 43, 3, 9, 82, 10};  // 待排序的数组
        System.out.println("原始数组：");
        printArray(array);  // 打印原始数组

        mergeSort(array);  // 调用归并排序方法

        System.out.println("\n排序后的数组：");
        printArray(array);  // 打印排序后的数组
    }

    // 归并排序方法
    public static void mergeSort(int[] array) {
        if (array.length < 2) {
            return;  // 如果数组长度小于2，直接返回，不需要排序
        }

        int mid = array.length / 2;  // 计算中间点，分割数组
        int[] left = new int[mid];  // 左子数组
        int[] right = new int[array.length - mid];  // 右子数组

        // 将原数组拆分为左子数组和右子数组
        System.arraycopy(array, 0, left, 0, mid);
        System.arraycopy(array, mid, right, 0, array.length - mid);

        mergeSort(left);  // 递归排序左子数组
        mergeSort(right);  // 递归排序右子数组

        merge(array, left, right);  // 合并已排序的左子数组和右子数组
    }

    // 合并方法：将两个已排序的数组合并成一个有序数组
    public static void merge(int[] array, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;

        // 比较并将较小的元素依次放入原数组中
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                array[k++] = left[i++];  // 将左子数组的元素放入原数组
            } else {
                array[k++] = right[j++];  // 将右子数组的元素放入原数组
            }
        }

        // 如果左子数组还有剩余元素，直接将它们放入原数组
        while (i < left.length) {
            array[k++] = left[i++];
        }

        // 如果右子数组还有剩余元素，直接将它们放入原数组
        while (j < right.length) {
            array[k++] = right[j++];
        }
    }

    // 打印数组的方法
    public static void printArray(int[] array) {
        for (int num : array) {
            System.out.print(num + " ");
        }
        System.out.println();  // 输出换行
    }
}

3.2 代码解析

mergeSort方法：
- mergeSort方法是归并排序的核心。首先检查数组长度是否小于2，如果小于2，则不需要排序，直接返回。
- 如果数组长度大于或等于2，首先计算中间点并将数组拆分为左右两个子数组。
- 通过递归调用mergeSort分别对左右子数组进行排序。
- 最后调用merge方法将排好序的左右子数组合并成一个有序的数组。
merge方法：
- merge方法是归并排序的关键操作，负责将两个已排序的子数组合并成一个有序的数组。
- 使用三个指针：i指向左子数组，j指向右子数组，k指向原数组。
- 比较左右子数组中的元素，将较小的元素放入原数组，并更新指针。
- 最后检查左子数组和右子数组是否还有剩余元素，如果有，将它们直接放入原数组中。
printArray方法：
- 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. 归并排序的复杂度分析

4.1 时间复杂度

归并排序的时间复杂度主要由两个部分组成：分解过程和合并过程。

分解过程：每次将数组分成两半，直到每个子数组只有一个元素。递归的深度是 log n（每次分半），即递归树的高度是 log n。
合并过程：每一层的合并操作需要遍历所有的元素，合并两个数组的时间复杂度是 O(n)。

因此，归并排序的总时间复杂度是 O(n log n)。

最佳情况：O(n log n)
最差情况：O(n log n)
平均情况：O(n log n)

4.2 空间复杂度

归并排序需要额外的空间来存储临时数组（用于存放左右子数组）。在每次合并操作时，都会创建新的数组来存放合并后的结果。
因此，归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的大小。

4.3 总结

时间复杂度：归并排序的时间复杂度始终是 O(n log n)，无论在最佳、最差还是平均情况下，都保持一致。
空间复杂度：归并排序的空间复杂度为 O(n)，需要额外的空间来存储合并过程中的临时数组。
稳定性：归并排序是一种稳定的排序算法，不会改变相同元素的相对顺序。

归并排序适合用于大规模数据的排序，尤其是在数据量非常大的情况下，它的时间复杂度 O(n log n) 可以提供稳定的性能。然而，空间复杂度较高，因此在空间有限的情况下需要考虑其他排序算法。

去1:1私密咨询

系列课程：

免费

VIP会员

第1课_归并排序的算法思想