05-分治算法

💡 核心结论

分治本质

  • 定义：分解→递归解决→合并结果

  • 三步骤：Divide（分解）→ Conquer（解决）→ Combine（合并）

  • 关键：子问题独立、可递归、能合并

  • 时间：T(n) = aT(n/b) + f(n)，主定理分析

  • 应用：归并排序、快排、二分查找、大整数乘法

分治 vs 其他

策略

特点

典型算法

分治

子问题独立

归并、快排

动态规划

子问题重叠

斐波那契、背包

贪心

局部最优

Dijkstra、哈夫曼

经典分治问题

  • 排序：归并O(n log n)、快排O(n log n)

  • 搜索：二分O(log n)

  • 矩阵：Strassen矩阵乘法O(n^2.81)

  • 大整数：Karatsuba乘法O(n^1.58)

  • 几何：最近点对O(n log n)

🎯 归并排序（分治典范）

def merge_sort(arr):
    # 分解
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])   # 递归左半
    right = merge_sort(arr[mid:])  # 递归右半
    
    # 合并
    return merge(left, right)

🔍 快速选择（第K大）

def quick_select(nums, k):
    """平均O(n)找第k大元素"""
    if not nums:
        return None
    
    pivot = nums[len(nums) // 2]
    left = [x for x in nums if x > pivot]
    mid = [x for x in nums if x == pivot]
    right = [x for x in nums if x < pivot]
    
    if k <= len(left):
        return quick_select(left, k)
    elif k <= len(left) + len(mid):
        return mid[0]
    else:
        return quick_select(right, k - len(left) - len(mid))

📚 LeetCode练习

💻 完整代码实现

Python 实现

  1"""
  2分治算法实现
  3"""
  4
  5# ========== 快速选择（第K大元素） ==========
  6
  7def quick_select(nums, k):
  8    """找第k大元素（平均O(n)）"""
  9    if not nums:
 10        return None
 11    
 12    pivot = nums[len(nums) // 2]
 13    left = [x for x in nums if x > pivot]
 14    mid = [x for x in nums if x == pivot]
 15    right = [x for x in nums if x < pivot]
 16    
 17    if k <= len(left):
 18        return quick_select(left, k)
 19    elif k <= len(left) + len(mid):
 20        return mid[0]
 21    else:
 22        return quick_select(right, k - len(left) - len(mid))
 23
 24
 25# ========== 归并排序 ==========
 26
 27def merge_sort(arr):
 28    """归并排序"""
 29    if len(arr) <= 1:
 30        return arr
 31    
 32    mid = len(arr) // 2
 33    left = merge_sort(arr[:mid])
 34    right = merge_sort(arr[mid:])
 35    
 36    return merge(left, right)
 37
 38
 39def merge(left, right):
 40    """合并两个有序数组"""
 41    result = []
 42    i = j = 0
 43    
 44    while i < len(left) and j < len(right):
 45        if left[i] <= right[j]:
 46            result.append(left[i])
 47            i += 1
 48        else:
 49            result.append(right[j])
 50            j += 1
 51    
 52    result.extend(left[i:])
 53    result.extend(right[j:])
 54    return result
 55
 56
 57# ========== 计算逆序对 ==========
 58
 59def merge_count(arr):
 60    """归并排序同时计算逆序对"""
 61    if len(arr) <= 1:
 62        return arr, 0
 63    
 64    mid = len(arr) // 2
 65    left, left_count = merge_count(arr[:mid])
 66    right, right_count = merge_count(arr[mid:])
 67    
 68    merged, merge_count_val = merge_and_count(left, right)
 69    
 70    return merged, left_count + right_count + merge_count_val
 71
 72
 73def merge_and_count(left, right):
 74    """合并并计算跨越两部分的逆序对"""
 75    result = []
 76    count = 0
 77    i = j = 0
 78    
 79    while i < len(left) and j < len(right):
 80        if left[i] <= right[j]:
 81            result.append(left[i])
 82            i += 1
 83        else:
 84            result.append(right[j])
 85            count += len(left) - i  # 逆序对数
 86            j += 1
 87    
 88    result.extend(left[i:])
 89    result.extend(right[j:])
 90    
 91    return result, count
 92
 93
 94def count_inversions(arr):
 95    """计算逆序对数量"""
 96    _, count = merge_count(arr)
 97    return count
 98
 99
100# ========== 最大子数组和（分治） ==========
101
102def max_subarray_divide_conquer(nums, left, right):
103    """分治法求最大子数组和"""
104    if left == right:
105        return nums[left]
106    
107    mid = (left + right) // 2
108    
109    # 左半部分最大
110    left_max = max_subarray_divide_conquer(nums, left, mid)
111    # 右半部分最大
112    right_max = max_subarray_divide_conquer(nums, mid + 1, right)
113    # 跨中点最大
114    cross_max = max_crossing_sum(nums, left, mid, right)
115    
116    return max(left_max, right_max, cross_max)
117
118
119def max_crossing_sum(nums, left, mid, right):
120    """计算跨越中点的最大子数组和"""
121    # 左边最大
122    left_sum = float('-inf')
123    curr_sum = 0
124    for i in range(mid, left - 1, -1):
125        curr_sum += nums[i]
126        left_sum = max(left_sum, curr_sum)
127    
128    # 右边最大
129    right_sum = float('-inf')
130    curr_sum = 0
131    for i in range(mid + 1, right + 1):
132        curr_sum += nums[i]
133        right_sum = max(right_sum, curr_sum)
134    
135    return left_sum + right_sum
136
137
138def demo():
139    """演示分治算法"""
140    print("=== 分治算法演示 ===\n")
141    
142    # 快速选择
143    nums = [3, 2, 1, 5, 6, 4]
144    k = 2
145    print(f"第{k}大元素 {nums}:")
146    print(f"  结果: {quick_select(nums, k)}\n")
147    
148    # 归并排序
149    arr = [5, 2, 8, 1, 9, 3]
150    print(f"归并排序 {arr}:")
151    print(f"  结果: {merge_sort(arr)}\n")
152    
153    # 逆序对
154    arr = [8, 4, 2, 1]
155    print(f"逆序对 {arr}:")
156    print(f"  数量: {count_inversions(arr)}\n")
157    
158    # 最大子数组和（分治）
159    nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
160    print(f"最大子数组和 {nums}:")
161    result = max_subarray_divide_conquer(nums, 0, len(nums) - 1)
162    print(f"  结果: {result}")
163
164
165if __name__ == '__main__':
166    demo()
167

C++ 实现

  1/**
  2 * 分治算法实现
  3 */
  4
  5#include <iostream>
  6#include <vector>
  7#include <algorithm>
  8#include <climits>
  9
 10using namespace std;
 11
 12// 归并排序
 13void merge(vector<int>& arr, int left, int mid, int right) {
 14    vector<int> L(arr.begin() + left, arr.begin() + mid + 1);
 15    vector<int> R(arr.begin() + mid + 1, arr.begin() + right + 1);
 16    
 17    int i = 0, j = 0, k = left;
 18    
 19    while (i < L.size() && j < R.size()) {
 20        if (L[i] <= R[j]) {
 21            arr[k++] = L[i++];
 22        } else {
 23            arr[k++] = R[j++];
 24        }
 25    }
 26    
 27    while (i < L.size()) arr[k++] = L[i++];
 28    while (j < R.size()) arr[k++] = R[j++];
 29}
 30
 31void mergeSortHelper(vector<int>& arr, int left, int right) {
 32    if (left < right) {
 33        int mid = left + (right - left) / 2;
 34        mergeSortHelper(arr, left, mid);
 35        mergeSortHelper(arr, mid + 1, right);
 36        merge(arr, left, mid, right);
 37    }
 38}
 39
 40vector<int> mergeSort(vector<int> arr) {
 41    mergeSortHelper(arr, 0, arr.size() - 1);
 42    return arr;
 43}
 44
 45// 快速选择（第K大元素）
 46int partition(vector<int>& nums, int left, int right) {
 47    int pivot = nums[right];
 48    int i = left;
 49    
 50    for (int j = left; j < right; j++) {
 51        if (nums[j] >= pivot) {  // 降序，找第k大
 52            swap(nums[i], nums[j]);
 53            i++;
 54        }
 55    }
 56    swap(nums[i], nums[right]);
 57    return i;
 58}
 59
 60int quickSelect(vector<int>& nums, int left, int right, int k) {
 61    if (left == right) return nums[left];
 62    
 63    int pivotIndex = partition(nums, left, right);
 64    
 65    if (pivotIndex == k) {
 66        return nums[k];
 67    } else if (pivotIndex < k) {
 68        return quickSelect(nums, pivotIndex + 1, right, k);
 69    } else {
 70        return quickSelect(nums, left, pivotIndex - 1, k);
 71    }
 72}
 73
 74int findKthLargest(vector<int> nums, int k) {
 75    return quickSelect(nums, 0, nums.size() - 1, k - 1);
 76}
 77
 78// 最大子数组和（分治）
 79int maxCrossingSum(const vector<int>& nums, int left, int mid, int right) {
 80    int leftSum = INT_MIN;
 81    int sum = 0;
 82    for (int i = mid; i >= left; i--) {
 83        sum += nums[i];
 84        leftSum = max(leftSum, sum);
 85    }
 86    
 87    int rightSum = INT_MIN;
 88    sum = 0;
 89    for (int i = mid + 1; i <= right; i++) {
 90        sum += nums[i];
 91        rightSum = max(rightSum, sum);
 92    }
 93    
 94    return leftSum + rightSum;
 95}
 96
 97int maxSubArrayDC(const vector<int>& nums, int left, int right) {
 98    if (left == right) {
 99        return nums[left];
100    }
101    
102    int mid = (left + right) / 2;
103    
104    int leftMax = maxSubArrayDC(nums, left, mid);
105    int rightMax = maxSubArrayDC(nums, mid + 1, right);
106    int crossMax = maxCrossingSum(nums, left, mid, right);
107    
108    return max({leftMax, rightMax, crossMax});
109}
110
111int maxSubArray(const vector<int>& nums) {
112    return maxSubArrayDC(nums, 0, nums.size() - 1);
113}
114
115// 计算逆序对
116long long mergeAndCount(vector<int>& arr, int left, int mid, int right) {
117    vector<int> L(arr.begin() + left, arr.begin() + mid + 1);
118    vector<int> R(arr.begin() + mid + 1, arr.begin() + right + 1);
119    
120    int i = 0, j = 0, k = left;
121    long long invCount = 0;
122    
123    while (i < L.size() && j < R.size()) {
124        if (L[i] <= R[j]) {
125            arr[k++] = L[i++];
126        } else {
127            arr[k++] = R[j++];
128            invCount += L.size() - i;  // 逆序对数
129        }
130    }
131    
132    while (i < L.size()) arr[k++] = L[i++];
133    while (j < R.size()) arr[k++] = R[j++];
134    
135    return invCount;
136}
137
138long long mergeSortCount(vector<int>& arr, int left, int right) {
139    long long invCount = 0;
140    
141    if (left < right) {
142        int mid = left + (right - left) / 2;
143        invCount += mergeSortCount(arr, left, mid);
144        invCount += mergeSortCount(arr, mid + 1, right);
145        invCount += mergeAndCount(arr, left, mid, right);
146    }
147    
148    return invCount;
149}
150
151long long countInversions(vector<int> arr) {
152    return mergeSortCount(arr, 0, arr.size() - 1);
153}
154
155int main() {
156    cout << "=== 分治算法演示 ===" << endl << endl;
157    
158    // 快速选择
159    vector<int> nums = {3, 2, 1, 5, 6, 4};
160    int k = 2;
161    cout << "第" << k << "大元素 [3,2,1,5,6,4]:" << endl;
162    cout << "  结果: " << findKthLargest(nums, k) << endl << endl;
163    
164    // 归并排序
165    vector<int> arr = {5, 2, 8, 1, 9, 3};
166    cout << "归并排序 [5,2,8,1,9,3]:" << endl;
167    vector<int> sorted = mergeSort(arr);
168    cout << "  结果: [";
169    for (size_t i = 0; i < sorted.size(); i++) {
170        cout << sorted[i];
171        if (i < sorted.size() - 1) cout << ", ";
172    }
173    cout << "]" << endl << endl;
174    
175    // 逆序对
176    vector<int> arr2 = {8, 4, 2, 1};
177    cout << "逆序对 [8,4,2,1]:" << endl;
178    cout << "  数量: " << countInversions(arr2) << endl << endl;
179    
180    // 最大子数组和
181    vector<int> nums2 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
182    cout << "最大子数组和 [-2,1,-3,4,-1,2,1,-5,4]:" << endl;
183    cout << "  结果: " << maxSubArray(nums2) << endl;
184    
185    return 0;
186}