综合算法 II | 分治与贪心

综合算法 II | 分治与贪心

分治算法

分治（Divide and Conquer）将大问题分解为小问题，分别求解后合并结果。

归并排序

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) 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

快速排序

def quick_sort(arr): if len(arr) <= 1: return arr pivot = arr[len(arr) // 2] left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] return quick_sort(left) + middle + quick_sort(right)

贪心算法

贪心（Greedy）在每一步选择当前最优解，期望得到全局最优。

活动选择问题

def activity_selection(activities): activities.sort(key=lambda x: x[1]) count = 1 end = activities[0][1] for i in range(1, len(activities)): if activities[i][0] >= end: count += 1 end = activities[i][1] return count

哈夫曼编码

哈夫曼编码使用贪心构建最优前缀码。

分治与贪心对比

总结

分治和贪心是两种重要的算法策略。分治保证最优，贪心效率高但需验证。