4.深入理解递归-1—上-灵析社区

4.1使用「归并排序」实现排序数组

「归并排序」将数组不断拆分，直到拆到不能再拆分为止（即数组只有 1 个元素的时候）。由于 1 个元素的数组肯定是有序数组，然后我们「逐层向上」依次合并两个有序组。通过这样的方式，我们实现了排序的功能。

「拆分」与「合并」就通过递归的方式，方便地实现了它们的逻辑。请大家结合下面的动画和下面参考代码，理解「递归返回以后进行合并两个有序数组」的时机。

参考代码 1：第 912 题：排序数组

Java

public class Solution {

    public int[] sortArray(int[] nums) {
        int len = nums.length;
        int[] temp = new int[len];
        mergeSort(nums, 0, len - 1, temp);
        return nums;
    }

    /**
     * 递归函数语义：对数组 nums 的子区间 [left.. right] 进行归并排序
     *
     * @param nums
     * @param left
     * @param right
     * @param temp  用于合并两个有序数组的辅助数组，全局使用一份，避免多次创建和销毁
     */
    private void mergeSort(int[] nums, int left, int right, int[] temp) {
        // 1. 递归终止条件
        if (left == right) {
            return;
        }

        // 2. 拆分，对应「分而治之」算法的「分」
        int mid = (left + right) / 2;

        mergeSort(nums, left, mid, temp);
        mergeSort(nums, mid + 1, right, temp);

        // 3. 在递归函数调用完成以后还可以做点事情

        // 合并两个有序数组，对应「分而治之」的「合」
        mergeOfTwoSortedArray(nums, left, mid, right, temp);
    }


    /**
     * 合并两个有序数组：先把值复制到临时数组，再合并回去
     *
     * @param nums
     * @param left
     * @param mid   mid 是第一个有序数组的最后一个元素的下标，即：[left..mid] 有序，[mid + 1..right] 有序
     * @param right
     * @param temp  全局使用的临时数组
     */
    private void mergeOfTwoSortedArray(int[] nums, int left, int mid, int right, int[] temp) {
        for (int i = left; i <= right; i++) {
            temp[i] = nums[i];
        }

        int i = left;
        int j = mid + 1;

        int k = left;
        while (i <= mid && j <= right) {
            if (temp[i] <= temp[j]) {
                // 注意写成 < 就丢失了稳定性（相同元素原来靠前的排序以后依然靠前）
                nums[k] = temp[i];
                k++;
                i++;
            } else {
                nums[k] = temp[j];
                k++;
                j++;
            }
        }

        while (i <= mid) {
            nums[k] = temp[i];
            k++;
            i++;
        }
        while (j <= right) {
            nums[k] = temp[j];
            k++;
            j++;
        }
    }
}

说明：

mergeSort(nums, left, mid, temp); 与 mergeSort(nums, mid + 1, right, temp); 是在递归地解决子问题。在它们之后我们编写的 mergeOfTwoSortedArray(nums, left, mid, right, temp); 是根据之前递归调用返回的结果（两个子数组 nums[left..mid] 和 nums[mid + 1.. right] 分别有序）进行「合并两个有序数组」的操作，以得到一个长度更长的有序数组 nums[left..right] 。如果我们使用迭代会变得非常麻烦，感兴趣的朋友可以阅读《算法（第 4 版）》「自底向上的归并排序」进行对比；
从这个例子我们可以知道，虽然「递归」在理论上执行效率没有「递推」效率高，但正确地编写「递归」函数可以帮助我们简化逻辑，而且现代编程语言的编译器还会对递归函数进行优化。因此我们的建议是：如果「递归」函数可以清晰地表达我们想要实现的业务逻辑，不建议为了追求性能极致而改用非递归的写法。

代码编写完成以后，我们可以给程序添加打印输出，方便我们更好地理解「归并排序」。

参考代码 2：

Java

import java.util.Arrays;

public class Solution {

    public int[] sortArray(int[] nums) {
        int len = nums.length;
        int[] temp = new int[len];
        mergeSort(nums, 0, len - 1, temp, 0);
        return nums;
    }

    private void mergeSort(int[] nums, int left, int right, int[] temp, int recursionLevel) {
        log("拆分子问题", left, right, recursionLevel);
        if (left == right) {
            log("解决子问题", left, right, recursionLevel);
            return;
        }

        int mid = (left + right) / 2;
        mergeSort(nums, left, mid, temp, recursionLevel + 1);
        mergeSort(nums, mid + 1, right, temp, recursionLevel + 1);
        mergeOfTwoSortedArray(nums, left, mid, right, temp);
        log("解决子问题", left, right, recursionLevel);
    }

    private void mergeOfTwoSortedArray(int[] nums, int left, int mid, int right, int[] temp) {
        for (int i = left; i <= right; i++) {
            temp[i] = nums[i];
        }

        int i = left;
        int j = mid + 1;

        int k = left;
        while (i <= mid && j <= right) {
            if (temp[i] <= temp[j]) {
                // 注意写成 < 就丢失了稳定性（相同元素原来靠前的排序以后依然靠前）
                nums[k] = temp[i];
                k++;
                i++;
            } else {
                nums[k] = temp[j];
                k++;
                j++;
            }
        }

        while (i <= mid) {
            nums[k] = temp[i];
            k++;
            i++;
        }
        while (j <= right) {
            nums[k] = temp[j];
            k++;
            j++;
        }
    }

    private void log(String log, int left, int right, int recursionLevel) {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("  ".repeat(Math.max(0, recursionLevel)));
        stringBuilder.append(log);
        stringBuilder.append(" ");
        stringBuilder.append("=>");
        stringBuilder.append(" ");
        stringBuilder.append("[");
        stringBuilder.append(left);
        stringBuilder.append(", ");
        stringBuilder.append(right);
        stringBuilder.append("]");
        System.out.println(stringBuilder.toString());
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = new int[]{8, 6, 7, 2, 3, 5, 4, 1};
        int[] res = solution.sortArray(nums);
        System.out.println(Arrays.toString(res));
    }
}

控制台输出：

拆分子问题 => [0, 7]
  拆分子问题 => [0, 3]
    拆分子问题 => [0, 1]
      拆分子问题 => [0, 0]
      解决子问题 => [0, 0]
      拆分子问题 => [1, 1]
      解决子问题 => [1, 1]
    解决子问题 => [0, 1]
    拆分子问题 => [2, 3]
      拆分子问题 => [2, 2]
      解决子问题 => [2, 2]
      拆分子问题 => [3, 3]
      解决子问题 => [3, 3]
    解决子问题 => [2, 3]
  解决子问题 => [0, 3]
  拆分子问题 => [4, 7]
    拆分子问题 => [4, 5]
      拆分子问题 => [4, 4]
      解决子问题 => [4, 4]
      拆分子问题 => [5, 5]
      解决子问题 => [5, 5]
    解决子问题 => [4, 5]
    拆分子问题 => [6, 7]
      拆分子问题 => [6, 6]
      解决子问题 => [6, 6]
      拆分子问题 => [7, 7]
      解决子问题 => [7, 7]
    解决子问题 => [6, 7]
  解决子问题 => [4, 7]
解决子问题 => [0, 7]
[1, 2, 3, 4, 5, 6, 7, 8]

根据控制台的打印输出，我们可以发现：归并排序的流程是按照「深度优先搜索」的方式进行的。事实上，所有的递归函数的调用过程，都是按照「深度优先搜索」的方式进行的。