跟着AI学算法-排序算法-归并排序，剖析排序过程

欢迎大家来到IT世界,在知识的湖畔探索吧!

归并排序是一种分治算法，它将待排序数组分成两个子数组，分别对子数组进行排序，然后将两个已排序的子数组合并成一个有序的数组。这个过程不断地递归执行，直到子数组长度为1，即可视为已经排好序的。

直白点将就是对数组一直拆分成左右两个数组，直到子数组长度为1，然后左右两边元素合并排序，并返回递归上层继续排序，直至数组排序完成。

具体步骤如下：

1. 将待排序的数组分成两个子数组，可以使用数组下标来实现。
2. 对每个子数组进行递归拆分，直到子数组长度为1。
3. 将两个已排序的子数组合并成一个有序的数组。合并过程中，创建一个临时数组，依次比较两个子数组的首个元素，将较小的元素放入临时数组中，直到其中一个子数组为空。然后将剩余的另一个子数组中的元素全部复制到临时数组的末尾。
4. 返回合并后的有序数组。

执行过程请移步文章末尾：排序执行过程。

归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)，是一种稳定的排序算法。

AI编码实现：

本地测试：

为了能够打印排序过程，代码稍作修改。

package com.algorithm.sort;

import java.util.Arrays;

/**
 * @author LuoFei
 * @className: MergeSort
 * @projectName algorithm
 * @description: TODO
 * @date 2023/2/21 15:45
 */
public class MergeSort{

    public static void mergeSort(int[] arr, int left, int right, int deep) {
        deep ++;
        System.out.print("递归深度："+deep +"; left="+left+", right="+right);
        if (left < right) {
            int mid = (left + right) / 2;
            System.out.println(", mid="+mid+"; 排序左侧数组;");
            // 对左侧子数组进行排序
            mergeSort(arr, left, mid, deep);
            // 对右侧子数组进行排序
            System.out.println("递归深度："+deep +"; 排序右侧数组; ");
            mergeSort(arr, mid + 1, right, deep);
            // 合并两个已排序的子数组
            System.out.println("递归深度："+deep +"; 开始合并数组; ");
            System.out.println("---------------------------------------");
            merge(arr, left, mid, right);
            System.out.println("---------------------------------------");
            System.out.print("递归深度："+deep +"; 合并后数组; "+Arrays.toString(arr) );
        }
        System.out.println();
        System.out.println("****************递归返回*****************");
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left +1];
        System.out.println("比较前临时数组："+Arrays.toString(temp));
        int i = left, j = mid + 1, k = 0;
        //比较左右两个子数组的元素，将较小的元素放入临时数组中
        while (i <= mid && j <= right) {
            System.out.println("比较["+i+", "+j+"]号位数字["+arr[i]+", "+arr[j]+"]");
            if (arr[i] < arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        System.out.println("比较后临时数组："+Arrays.toString(temp));
        //将左侧子数组中剩余的元素复制到临时数组中
        System.out.print("复制左侧剩余元素：");
        while (i <= mid) {
            System.out.print(arr[i]);
            temp[k++] = arr[i++];
        }
        System.out.println();
        System.out.println("复制左侧剩余元素后，临时数组："+Arrays.toString(temp));
        //将右侧子数组中剩余的元素复制到临时数组中
        System.out.print("复制右侧剩余元素：");
        while (j <= right) {
            System.out.print(arr[j]);
            temp[k++] = arr[j++];
        }
        System.out.println();
        System.out.println("复制右侧剩余元素后，临时数组："+Arrays.toString(temp));
        //将临时数组中的元素复制回原数组
        for (i = left, k = 0; i <= right; i++, k++) {
            arr[i] = temp[k];
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 3, 9, 1};
        System.out.println("初始数组："+Arrays.toString(arr));
        System.out.println("=======================================");
        mergeSort(arr, 0, arr.length - 1, 0);
        System.out.println("=======================================");
        System.out.println("最终数组"+Arrays.toString(arr));
    }
}

欢迎大家来到IT世界,在知识的湖畔探索吧!

排序执行过程：

欢迎大家来到IT世界,在知识的湖畔探索吧!初始数组：[5, 2, 8, 3, 9, 1]
=======================================
递归深度：1; left=0, right=5, mid=2; 排序左侧数组;
递归深度：2; left=0, right=2, mid=1; 排序左侧数组;
递归深度：3; left=0, right=1, mid=0; 排序左侧数组;
递归深度：4; left=0, right=0
****************递归返回*****************
递归深度：3; 排序右侧数组; 
递归深度：4; left=1, right=1
****************递归返回*****************
递归深度：3; 开始合并数组; 
---------------------------------------
比较前临时数组：[0, 0]
比较[0, 1]号位数字[5, 2]
比较后临时数组：[2, 0]
复制左侧剩余元素：5
复制左侧剩余元素后，临时数组：[2, 5]
复制右侧剩余元素：
复制右侧剩余元素后，临时数组：[2, 5]
---------------------------------------
递归深度：3; 合并后数组; [2, 5, 8, 3, 9, 1]
****************递归返回*****************
递归深度：2; 排序右侧数组; 
递归深度：3; left=2, right=2
****************递归返回*****************
递归深度：2; 开始合并数组; 
---------------------------------------
比较前临时数组：[0, 0, 0]
比较[0, 2]号位数字[2, 8]
比较[1, 2]号位数字[5, 8]
比较后临时数组：[2, 5, 0]
复制左侧剩余元素：
复制左侧剩余元素后，临时数组：[2, 5, 0]
复制右侧剩余元素：8
复制右侧剩余元素后，临时数组：[2, 5, 8]
---------------------------------------
递归深度：2; 合并后数组; [2, 5, 8, 3, 9, 1]
****************递归返回*****************
递归深度：1; 排序右侧数组; 
递归深度：2; left=3, right=5, mid=4; 排序左侧数组;
递归深度：3; left=3, right=4, mid=3; 排序左侧数组;
递归深度：4; left=3, right=3
****************递归返回*****************
递归深度：3; 排序右侧数组; 
递归深度：4; left=4, right=4
****************递归返回*****************
递归深度：3; 开始合并数组; 
---------------------------------------
比较前临时数组：[0, 0]
比较[3, 4]号位数字[3, 9]
比较后临时数组：[3, 0]
复制左侧剩余元素：
复制左侧剩余元素后，临时数组：[3, 0]
复制右侧剩余元素：9
复制右侧剩余元素后，临时数组：[3, 9]
---------------------------------------
递归深度：3; 合并后数组; [2, 5, 8, 3, 9, 1]
****************递归返回*****************
递归深度：2; 排序右侧数组; 
递归深度：3; left=5, right=5
****************递归返回*****************
递归深度：2; 开始合并数组; 
---------------------------------------
比较前临时数组：[0, 0, 0]
比较[3, 5]号位数字[3, 1]
比较后临时数组：[1, 0, 0]
复制左侧剩余元素：39
复制左侧剩余元素后，临时数组：[1, 3, 9]
复制右侧剩余元素：
复制右侧剩余元素后，临时数组：[1, 3, 9]
---------------------------------------
递归深度：2; 合并后数组; [2, 5, 8, 1, 3, 9]
****************递归返回*****************
递归深度：1; 开始合并数组; 
---------------------------------------
比较前临时数组：[0, 0, 0, 0, 0, 0]
比较[0, 3]号位数字[2, 1]
比较[0, 4]号位数字[2, 3]
比较[1, 4]号位数字[5, 3]
比较[1, 5]号位数字[5, 9]
比较[2, 5]号位数字[8, 9]
比较后临时数组：[1, 2, 3, 5, 8, 0]
复制左侧剩余元素：
复制左侧剩余元素后，临时数组：[1, 2, 3, 5, 8, 0]
复制右侧剩余元素：9
复制右侧剩余元素后，临时数组：[1, 2, 3, 5, 8, 9]
---------------------------------------
递归深度：1; 合并后数组; [1, 2, 3, 5, 8, 9]
****************递归返回*****************
=======================================
最终数组[1, 2, 3, 5, 8, 9]

第一层拆分： [5, 2, 8] | [3, 9, 1]

第二层拆分： [5, 2] | [8] || [3, 9] | [1]

第三层拆分： [5] | [2] || [8] ||| [3] | [9] || [1]

第四层： 递归返回

第三层合并： [2, 5] | [8] || [3, 9] | [1]

第二层合并： [2, 5, 8] | [1, 3, 9]

第一层合并： [1, 2, 3, 5, 8, 9]