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

4.2使用「快速排序」实现排序数组

「归并排序」在「拆分子问题」环节是「无脑地」进行拆分，然后我们需要在「合」的环节进行一些操作。而「快速排序」在「分」这件事情上做出了文章，因此在「合」的环节什么都不用做。

「快速排序」大家可以阅读经典的算法教程《算法导论》《算法（第 4 版）》进行学习，也可以阅读 LeetBook 之排序算法全解析。我们在这里就不对「快速排序」算法进行具体讲解，而直接给出代码，相关的知识点通过注释给出。

这一版快速排序的代码，我们

引入了随机化选择切分元素 pivot，以避免递归树倾斜；
并且使用了双指针技巧，将与 pivot 相等的元素平均地分散到待排序区间的开头和末尾。

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

Java

import java.util.Random;

public class Solution {

    /**
     * 随机化是为了防止递归树偏斜的操作，此处不展开叙述
     */
    private static final Random RANDOM = new Random();

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

    /**
     * 对数组的子区间 nums[left..right] 排序
     *
     * @param nums
     * @param left
     * @param right
     */
    private void quickSort(int[] nums, int left, int right) {
        // 1. 递归终止条件
        if (left >= right) {
            return;
        }

        int pIndex = partition(nums, left, right);

        // 2. 拆分，对应「分而治之」算法的「分」
        quickSort(nums, left, pIndex - 1);
        quickSort(nums, pIndex + 1, right);

        // 3. 递归完成以后没有「合」的操作，这是由「快速排序」partition 的逻辑决定的
    }


    /**
     * 将数组 nums[left..right] 分区，返回下标 pivot，
     * 且满足 [left + 1..lt) <= pivot，(gt, right] >= pivot
     *
     * @param nums
     * @param left
     * @param right
     * @return
     */
    private int partition(int[] nums, int left, int right) {
        int randomIndex = left + RANDOM.nextInt(right - left + 1);
        swap(nums, randomIndex, left);

        int pivot = nums[left];
        int lt = left + 1;
        int gt = right;

        while (true) {
            while (lt <= right && nums[lt] < pivot) {
                lt++;
            }

            while (gt > left && nums[gt] > pivot) {
                gt--;
            }

            if (lt >= gt) {
                break;
            }

            // 细节：相等的元素通过交换，等概率分到数组的两边
            swap(nums, lt, gt);
            lt++;
            gt--;
        }
        swap(nums, left, gt);
        return gt;
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

我们依然可以为「快速排序」增加打印输出语句：

参考代码 4：

Java

import java.util.Arrays;
import java.util.Random;

public class Solution {

    /**
     * 随机化是为了防止递归树偏斜的操作，此处不展开叙述
     */
    private static final Random RANDOM = new Random();

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

    /**
     * 对数组的子区间 nums[left..right] 排序
     *
     * @param nums
     * @param left
     * @param right
     */
    private void quickSort(int[] nums, int left, int right, int recursionLevel) {
        log("拆分子问题", left, right, recursionLevel);
        // 1. 递归终止条件
        if (left >= right) {
            log("递归到底", left, right, recursionLevel);
            return;
        }

        int pIndex = partition(nums, left, right);
        // 2. 拆分，对应「分而治之」算法的「分」
        quickSort(nums, left, pIndex - 1, recursionLevel + 1);
        quickSort(nums, pIndex + 1, right, recursionLevel + 1);
        // 3. 递归完成以后没有「合」的操作，这是由「快速排序」partition 的逻辑决定的
    }


    /**
     * 将数组 nums[left..right] 分区，返回下标 pivot，
     * 且满足 [left + 1..lt) <= pivot，(gt, right] >= pivot
     *
     * @param nums
     * @param left
     * @param right
     * @return
     */
    private int partition(int[] nums, int left, int right) {
        int randomIndex = left + RANDOM.nextInt(right - left + 1);
        swap(nums, randomIndex, left);

        int pivot = nums[left];
        int lt = left + 1;
        int gt = right;

        while (true) {
            while (lt <= right && nums[lt] < pivot) {
                lt++;
            }

            while (gt > left && nums[gt] > pivot) {
                gt--;
            }

            if (lt >= gt) {
                break;
            }

            // 细节：相等的元素通过交换，等概率分到数组的两边
            swap(nums, lt, gt);
            lt++;
            gt--;
        }
        swap(nums, left, gt);
        return gt;
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }

    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[]{7, 7, 7, 1, 7, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9};
        int[] res = solution.sortArray(nums);
        System.out.println(Arrays.toString(res));
    }
}

控制台输出：

拆分子问题 => [0, 15]
  拆分子问题 => [0, 9]
    拆分子问题 => [0, 3]
      拆分子问题 => [0, -1]
      递归到底 => [0, -1]
      拆分子问题 => [1, 3]
        拆分子问题 => [1, 2]
          拆分子问题 => [1, 0]
          递归到底 => [1, 0]
          拆分子问题 => [2, 2]
          递归到底 => [2, 2]
        拆分子问题 => [4, 3]
        递归到底 => [4, 3]
    拆分子问题 => [5, 9]
      拆分子问题 => [5, 5]
      递归到底 => [5, 5]
      拆分子问题 => [7, 9]
        拆分子问题 => [7, 8]
          拆分子问题 => [7, 6]
          递归到底 => [7, 6]
          拆分子问题 => [8, 8]
          递归到底 => [8, 8]
        拆分子问题 => [10, 9]
        递归到底 => [10, 9]
  拆分子问题 => [11, 15]
    拆分子问题 => [11, 14]
      拆分子问题 => [11, 11]
      递归到底 => [11, 11]
      拆分子问题 => [13, 14]
        拆分子问题 => [13, 13]
        递归到底 => [13, 13]
        拆分子问题 => [15, 14]
        递归到底 => [15, 14]
    拆分子问题 => [16, 15]
    递归到底 => [16, 15]
[1, 2, 3, 4, 4, 5, 5, 6, 7, 7, 7, 7, 7, 7, 8, 9]

说明：

由于加入了随机化，每一次运行的结果很可能不同；
遇到拆分子问题 [15, 14] ，这个时候区间里没有元素，所以马上接下来输出的语句就是「递归到底」，然后程序将结果一层一层向上返回。

4.3总结

在程序中添加打印输出，是我们理解程序的重要方法。它虽然很粗暴，但很实用。