算法思想 - 分治算法

1. 分治算法理论

分治算法（Divide and Conquer）是一种将问题分解并逐步求解的算法范式。它的核心思路是：

1. 分（Divide）：将原问题分割为若干个规模更小的子问题。
2. 治（Conquer）：针对每个子问题，递归地解决。当子问题规模足够小（或简单），则直接解决。
3. 合（Combine）：将子问题的解合并，形成原问题的最终解。

分治算法在大量算法（如排序、搜索、矩阵运算、图算法等）中都有广泛应用，一般能将原问题的时间复杂度降到比朴素算法更优的程度。

适用场景：

• 问题可以被「自然地」分割为规模更小的多个相似子问题；
• 子问题之间相对独立，彼此结果可组合成完整解；
• 分解、合并的逻辑清晰，并且能带来更优的平均或最坏时间复杂度。

典型例子：

• 归并排序（Merge Sort）
• 快速排序（Quick Sort）
• 矩阵乘法分治算法（如 Strassen 矩阵乘法）

2. 分治算法的核心思想

分治算法的「Divide - Conquer - Combine」三步骤可归纳为以下要点：

1. 划分子问题
   • 如何拆分原问题？是拆分成两个子问题，还是更多个？
   • 是否各个子问题规模大体相当？（如归并排序把数组对半分）
   • 这一步要确保「拆分后的问题」和原问题在结构或性质上相同或相似，从而可以继续应用同样的分治思路。
2. 递归解决子问题
   • 对拆分后的每个子问题，若仍然不够简单，则继续分治；否则直接求解。
   • 这一步往往通过递归实现，直到子问题规模足够小（常常是规模为 1 或 0）时，问题变得简单，直接求解。
3. 合并子问题结果
   • 在所有子问题都解决后，需要整合它们的解，得到原问题最终答案。
   • 在归并排序中，这一步是把有序的左右子数组归并成完整的有序数组；在快速排序中，这一步是拼接左侧已排好的子序列、枢纽值（pivot）和右侧已排好的子序列，形成完整有序序列。

3. 典型案例

3.1 归并排序

问题描述

给定一个无序数组 nums，需要将其排序（从小到大或从大到小）。请使用归并排序的分治思想进行实现。

思路解析

1. 分：将数组对半分为两个子数组 leftPart 和 rightPart；
2. 治：递归地对 leftPart、rightPart 进行排序；
3. 合：将排序完的 leftPart 与 rightPart 合并（归并）成一个有序的完整数组。

归并排序的核心在于归并（Merge）步骤：

• 双指针分别指向左子数组和右子数组的开头；
• 比较指针所指元素，小的那个先放到结果数组，然后指针后移；
• 直到有一方数组先遍历完，再将另一方剩余元素全部放入结果数组中。

时间复杂度

归并排序每次将数组对半拆分，树形递归深度约为 O(log n)，每一层递归需要 O(n) 时间进行归并操作，故整体时间复杂度为 O(n log n)。

public class MergeSort {
    public void mergeSort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        mergeSortRecursive(nums, 0, nums.length - 1);
    }

    // 递归进行分治
    private void mergeSortRecursive(int[] nums, int left, int right) {
        if (left >= right) {
            return; // 单个元素或无元素时，已是有序
        }
        int mid = left + (right - left) / 2;
        // 1. 分 - 左右子区间分别递归排序
        mergeSortRecursive(nums, left, mid);
        mergeSortRecursive(nums, mid + 1, right);
        // 2. 合 - 归并两个有序子区间
        merge(nums, left, mid, right);
    }

    // 将 [left..mid] 和 [mid+1..right] 两个有序段合并
    private void merge(int[] nums, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left;    // 左指针
        int j = mid + 1; // 右指针
        int k = 0;       // 临时数组索引

        // 比较左右子数组的元素，依次放入 temp
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }

        // 若左子数组还有剩余
        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        // 若右子数组还有剩余
        while (j <= right) {
            temp[k++] = nums[j++];
        }

        // 将 temp 中合并好的结果复制回原数组
        for (int p = 0; p < temp.length; p++) {
            nums[left + p] = temp[p];
        }
    }
}

3.2 快速排序

问题描述

给定一个无序数组 nums，使用快速排序对其从小到大排序。

思路解析

1. 分：随机或按某种方式选取枢轴（pivot），将数组分为 小于等于 pivot 和 大于 pivot 两部分。
2. 治：递归对两部分再进行快排。
3. 合：快速排序在分区完成后，左右两边的结果自然有序，不需要像归并那样显式合并，只需最后组合结果即可。

核心 - 分区操作（Partition）

• 从数组中选择一个元素作为 pivot；
• 使用双指针或单指针方法将小于等于 pivot 的值放左侧，大于 pivot 的值放右侧；
• 最终返回 pivot 的正确位置索引。

时间复杂度

• 平均情况下：快排可达到 O(n log n)；
• 最坏情况：若每次分区都极不平衡（如有序数组中总是选最右元素做 pivot），时间复杂度可退化到 O(n^2)。
• 通过随机选取 pivot 或其他优化（如三数取中），能尽量减小最坏情况出现的概率。

public class QuickSort {
    public void quickSort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        quickSortRecursive(nums, 0, nums.length - 1);
    }

    private void quickSortRecursive(int[] nums, int left, int right) {
        if (left < right) {
            // 分区，返回 pivot 的正确位置
            int pivotIndex = partition(nums, left, right);
            // 继续对 pivot 左侧、右侧进行快排
            quickSortRecursive(nums, left, pivotIndex - 1);
            quickSortRecursive(nums, pivotIndex + 1, right);
        }
    }

    private int partition(int[] nums, int left, int right) {
        int pivot = nums[right]; // 选取最右元素为枢轴
        int i = left;            // i 指向小于等于 pivot 区的尾部

        for (int j = left; j < right; j++) {
            if (nums[j] <= pivot) {
                // 交换，使得小于等于 pivot 的值都移动到 i 之前
                swap(nums, i, j);
                i++;
            }
        }
        // 最后将 pivot 换到正确的位置 i
        swap(nums, i, right);
        return i;
    }

    private void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}

4. 分治算法的核心要点

1. 分解（Divide）
   • 找到合理的方式把问题拆分成子问题；
   • 保证子问题的规模显著缩小，通常是对半或类似方式。
2. 递归（Conquer）
   • 如果子问题还足够大，继续进行分治；
   • 如果子问题很小，直接计算解决。
3. 合并（Combine）
   • 将子问题的解组合成整个问题的解；
   • 合并过程往往是分治算法的关键难点（如归并排序中的归并、Strassen 中的矩阵块拼合等）。
4. 复杂度与适用性
   • 分治算法多数能将时间复杂度从朴素的 O(n2)O(n^2) 或 O(n3)O(n^3) 降到 O(nlog⁡n)O(n \log n) 或更优；
   • 但若拆分或合并的过程本身消耗过大（如频繁拷贝大规模数据），也会影响整体性能。

5. 典型应用对比

应用场景	分割方式	合并过程	时间复杂度
归并排序（Merge Sort）	数组对半拆分	归并有序子数组	O(nlog⁡n)
快速排序（Quick Sort）	选枢轴，将数组分为左右两段	左右子序列排好后直接拼接	平均 O(nlog⁡n)
Strassen 矩阵乘法	将矩阵分为 4 个子块	通过 7 次子块乘法及加减法拼合矩阵	O(n2.807…)
二叉树相关的递归问题	拆分为左右子树	将左右子树结果合并	视问题而定
二分查找（特殊的分治）	选中间元素划分左右	无需显式合并（只需判断）	O(log⁡n)

分治算法可以应用于许多递归式问题中，每当子问题结构与原问题相同，并且能通过子问题的解合并出整体解时，都可以考虑「Divide and Conquer」的范式。

总结

1. 分治算法是递归思想的典型：
   • 不断将问题对半或多半地拆分；
   • 直到能直接解决；
   • 最后逐层向上返回，合并出整体解。
2. 适用性：
   • 问题可以被自然地拆分为小规模子问题；
   • 子问题之间在逻辑上相对独立，彼此结果可以无缝合并。
3. 优势与劣势：
   • 优势：计算复杂度通常降低，容易实现多线程并行等；
   • 劣势：需要额外的空间（如归并排序需要额外的临时数组）或导致额外的拆分/合并开销。