算法——归并排序（基本思想、java实现、实现图解）

我是一个计算机专业研0的学生卡蒙Camel🐫🐫🐫（刚保研）
记录每天学习过程（主要学习Java、python、人工智能），总结知识点（内容来自：自我总结+网上借鉴）
希望大家能一起发现问题和补充，也欢迎讨论👏👏👏

归并排序

介绍

归并排序（Merge Sort）是一种基于分治法的排序算法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

1. ⭐基本思想：它的工作原理是将数组递归地分成两个子数组，对每个子数组分别进行排序，然后将已排序的子数组合并成一个完整的有序数组。归并排序的时间复杂度为 $O(nlogn)$ ，这使得它对于大型数据集非常有效。

2. ⏩步骤：归并排序是一个递归算法

3. 分解：将未排序的数组以中点为中心分为两个子数组。

4. 解决：递归地对这两个子数组进行归并排序。

5. 合并：将两个已经排序好的子数组合并成一个单一的有序数组。

Java代码实现

import java.util.Arrays;

public class MergeSort {
    // 主函数，用于启动归并排序
    public static void mergeSort(int[] array) {
        if (array.length < 2) {
            return;
        }
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);

        mergeSort(left); // 递归排序左半部分
        mergeSort(right); // 递归排序右半部分
        // 排序完后，左右两边都是有序的
        merge(array, left, right); // 合并左右两部分
    }

    // 合并两个已排序的子数组
    private static void merge(int[] result, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        // 1. 比较两个数组的大小，将小的放入合并数组肿
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }
        // 2. 比较完后，将其中一边剩余的数组全部添加到合并数组中
        while (i < left.length) {
            result[k++] = left[i++];
        }

        while (j < right.length) {
            result[k++] = right[j++];
        }
    }

    // 测试方法
    public static void main(String[] args) {
        int[] array = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("原始数组: " + Arrays.toString(array));
        mergeSort(array);
        System.out.println("排序后的数组: " + Arrays.toString(array));
    }
}

算法分析

• 稳定性：稳定

• 时间复杂度：

• 最佳：$O(nlogn)$

• 最差：$O(nlogn)$

• 平均：$O(nlogn)$

• 空间复杂度：$O(n)$

实现图解🖌️

1. 根据上图可知，使用递归方法（递归出口是当数组长度为1的时候），然后逐渐左右两个数组合并，直到合并完成（先排序再合并）。

2. 合并过程：将两个已经有序的数组合并成一个有序数组

   2.1 初始化指针：

   • i：指向left数组的起始位置。

   • j：指向right数组的起始位置。

   • k：指向result数组的起始位置。

   2.2 比较与合并：

   • 比较left[i]和right[j]，将较小的那个复制到result[k]中，并向前移动相应数组的指针（i++或j++），同时更新k++以指向下一个待填充的位置。

   • 重复上述步骤直到其中一个子数组被完全遍历。

   2.3 处理剩余元素：

   • 如果left或right中的任意一个还有剩余元素，则直接将这些元素复制到result数组中，因为它们已经是有序的。

   • 注意，由于我们总是从两个子数组中选择较小的元素，所以当一个子数组被耗尽时，另一个子数组剩下的所有元素都比之前放入result的所有元素要大，因此可以直接添加到result的末尾。

   2.4 完成合并：

   • 当所有元素都被正确放置到result数组后，合并过程结束。

和快速排序对比(面试)