分治算法完全指南

def merge_sort(arr):
    """
    归并排序 - 分治算法
    :param arr: 待排序数组
    :return: 排序后的数组
    """
    # 基本情况：数组长度为 0 或 1
    if len(arr) <= 1:
        return arr
    
    # 分解：找到中点，分成两半
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    
    # 解决：递归排序两半
    left_sorted = merge_sort(left)
    right_sorted = merge_sort(right)
    
    # 合并：合并两个有序数组
    return merge(left_sorted, right_sorted)

def merge(left, right):
    """合并两个有序数组"""
    result = []
    i = j = 0
    
    # 比较两个数组的元素，按顺序放入结果
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    # 处理剩余元素
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result

# 测试
arr = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(arr))  # [3, 9, 10, 27, 38, 43, 82]

def quick_sort(arr, low=0, high=None):
    """
    快速排序 - 分治算法
    :param arr: 待排序数组
    :param low: 起始索引
    :param high: 结束索引
    :return: 排序后的数组
    """
    if high is None:
        high = len(arr) - 1
    
    if low < high:
        # 分解：分区操作
        pivot_index = partition(arr, low, high)
        
        # 解决：递归排序左右两部分
        quick_sort(arr, low, pivot_index - 1)
        quick_sort(arr, pivot_index + 1, high)
    
    return arr

def partition(arr, low, high):
    """分区操作：将小于基准的放左边，大于基准的放右边"""
    pivot = arr[high]  # 选择最后一个元素作为基准
    i = low - 1
    
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    # 将基准放到正确位置
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

# 测试
arr = [10, 7, 8, 9, 1, 5]
print(quick_sort(arr))  # [1, 5, 7, 8, 9, 10]

def binary_search(arr, target, low=0, high=None):
    """
    二分搜索 - 分治算法
    :param arr: 有序数组
    :param target: 目标值
    :param low: 左边界
    :param high: 右边界
    :return: 目标值的索引，未找到返回 -1
    """
    if high is None:
        high = len(arr) - 1
    
    # 基本情况：搜索范围为空
    if low > high:
        return -1
    
    # 分解：计算中间位置
    mid = low + (high - low) // 2
    
    # 解决：根据比较结果决定搜索哪一半
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        # 搜索右半部分
        return binary_search(arr, target, mid + 1, high)
    else:
        # 搜索左半部分
        return binary_search(arr, target, low, mid - 1)

# 测试
arr = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(arr, 7))   # 3
print(binary_search(arr, 6))   # -1

def karatsuba(x, y):
    """
    Karatsuba 大整数乘法
    :param x, y: 两个大整数
    :return: 乘积
    """
    # 基本情况：数字足够小，直接相乘
    if x < 10 or y < 10:
        return x * y
    
    # 计算数字位数
    n = max(len(str(x)), len(str(y)))
    m = n // 2
    
    # 分解：将数字分成高位和低位
    high_x, low_x = divmod(x, 10**m)
    high_y, low_y = divmod(y, 10**m)
    
    # 解决：递归计算三个乘积
    z0 = karatsuba(low_x, low_y)
    z1 = karatsuba(high_x + low_x, high_y + low_y)
    z2 = karatsuba(high_x, high_y)
    
    # 合并：组合结果
    return z2 * 10**(2*m) + (z1 - z2 - z0) * 10**m + z0

# 测试
print(karatsuba(1234, 5678))  # 7006652
print(1234 * 5678)             # 7006652（验证）

def fft_basic(concept_only):
    """
    快速傅里叶变换（概念示例）
    将 DFT 分解为偶数和奇数部分
    
    X[k] = E[k] + W_N^k * O[k]
    X[k+N/2] = E[k] - W_N^k * O[k]
    
    其中：
    - E[k] 是偶数部分的 DFT
    - O[k] 是奇数部分的 DFT
    - W_N^k 是旋转因子
    """
    pass  # 实际实现较复杂，此处仅展示思路

import math

def closest_pair(points):
    """
    最近点对问题 - 分治算法
    :param points: 点列表 [(x, y), ...]
    :return: 最近距离
    """
    # 按 x 坐标排序
    points.sort()
    
    def divide_and_conquer(pts):
        n = len(pts)
        
        # 基本情况：点数少，暴力计算
        if n <= 3:
            min_dist = float('inf')
            for i in range(n):
                for j in range(i+1, n):
                    dist = math.sqrt((pts[i][0]-pts[j][0])**2 + 
                                   (pts[i][1]-pts[j][1])**2)
                    min_dist = min(min_dist, dist)
            return min_dist
        
        # 分解：按 x 坐标分成两半
        mid = n // 2
        mid_point = pts[mid]
        
        # 解决：递归求解左右两部分
        left_min = divide_and_conquer(pts[:mid])
        right_min = divide_and_conquer(pts[mid:])
        
        # 合并：检查跨越中线的点对
        min_dist = min(left_min, right_min)
        
        # 只考虑中线附近 strip 区域内的点
        strip = [p for p in pts if abs(p[0] - mid_point[0]) < min_dist]
        strip.sort(key=lambda p: p[1])  # 按 y 排序
        
        # 检查 strip 中的点对（最多检查 7 个后续点）
        for i in range(len(strip)):
            for j in range(i+1, min(i+8, len(strip))):
                if strip[j][1] - strip[i][1] >= min_dist:
                    break
                dist = math.sqrt((strip[i][0]-strip[j][0])**2 + 
                               (strip[i][1]-strip[j][1])**2)
                min_dist = min(min_dist, dist)
        
        return min_dist
    
    return divide_and_conquer(points)

# 测试
points = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
print(f"最近距离: {closest_pair(points):.2f}")