Auto-generated at 2025-09-22 15:44
我们的任务是分析每日交通流量的变化数组（正数代表流量增加，负数代表减少），并找到哪一个连续时段的流量总增量最大。这在算法上被称为“最大子数组问题” 。
例如，对于流量变化数组[13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]，总增量最大的连续时段是从第8天到第11天，总增量为 18 + 20 - 7 + 12 = 43 。
虽然这个问题可以通过O(n2) 的暴力法求解，但我们将使用更高效的分治策略。
你需要实现一个分治算法来解决最大子数组问题。 同时，为了对比，你也会实现一个暴力求解算法。
在下方代码编辑区，完成 find_maximum_subarray（分治法）和 find_max_crossing_subarray 以及 find_maximum_subarray_brute（暴力法）三个函数。
import time
import random
def find_maximum_subarray_brute(arr):
"""
使用暴力法求解最大子数组问题
返回: (最大和, 开始索引, 结束索引)
"""
#--- 本周任务：请在下方实现分治算法 ---
def find_max_crossing_subarray(arr, low, mid, high):
"""
找到跨越中点的最大子数组
返回: (最大和, 开始索引, 结束索引)
"""
# TODO: 实现寻找跨越中点的最大子数组的逻辑
# 提示: 从mid向左和向右分别扫描，找到各自的最大和
def find_maximum_subarray(arr, low, high):
"""
使用分治法求解最大子数组问题
返回: (最大和, 开始索引, 结束索引)
"""
# TODO: 实现分治递归逻辑
# 提示: 递归基是当数组只有一个元素时
#--- 测试与对比部分 --- 以下内容无需修改
traffic_changes = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
print(f"交通流量变化数据: {traffic_changes}")
#使用分治法
max_sum_dc, start_dc, end_dc = find_maximum_subarray(traffic_changes, 0, len(traffic_changes) - 1)
print(f"分治法结果: 最大增量 = {max_sum_dc}, 时段 = Day {start_dc} to Day {end_dc}")
#使用暴力法验证
max_sum_brute, start_brute, end_brute = find_maximum_subarray_brute(traffic_changes)
print(f"暴力法结果: 最大增量 = {max_sum_brute}, 时段 = Day {start_brute} to Day {end_brute}")
#性能测试
large_data = [random.randint(-50, 50) for _ in range(2000)]
start_time = time.perf_counter()
find_maximum_subarray(large_data, 0, len(large_data) - 1)
dc_time = (time.perf_counter() - start_time) * 1000
print(f"\n在 n=2000 的数据集上，分治法耗时: {dc_time:.2f} ms")
start_time = time.perf_counter()
find_maximum_subarray_brute(large_data)
brute_time = (time.perf_counter() - start_time) * 1000
print(f"在 n=2000 的数据集上，暴力法耗时: {brute_time:.2f} ms")
快速排序（Quick Sort）是分治法的经典应用之一。与归并排序不同的是，快速排序通过原地划分数组来完成排序，无需额外的同规模辅助存储空间。它在平均情况下表现极为高效，是实际应用中常用的排序算法之一。
快速排序的分治核心思路非常好理解，对于一个未排序的数组，希望分解为左区间和一个“枢轴（pivot）”元素和右区间，其中左区间的数都小于等于枢轴，右区间的都大于等于枢轴。 我们这里用一种固定枢轴法来将序列变成上述的区间情况： ”选取数组第一个元素作为枢轴，用一个移动变量指向数组末尾元素并不断向前移动，直到找到第一个小于枢轴的元素，将该元素与枢轴位置交换，然后从枢轴原位置的下一位个元素开始往后找第一大于的交替，重复上述过程，最终实现以枢轴为界划分出左小右大的区间，再对左右区间递归执行此操作完成排序“
现在你需要亲手实现快速排序算法，并通过实验验证其在不同输入情况下的性能差异。
实现 quick_sort(arr) 函数，使用分治策略对传入的数组进行排序。为简单起见，可选择每次固定使用数组的第一个元素作为枢轴，将比枢轴小的元素放在左侧，比枢轴大的放在右侧，然后递归地排序左右子数组。完成实现后，我们将利用性能测试函数对比有序输入（近似最坏情况）和随机输入（平均情况）下算法的运行时间。 代码框架 请在下方代码编辑区完成 quick_sort(arr) 的实现。
import random
import time
def quick_sort(arr):
"""
实现快速排序算法（固定枢轴策略）
参数arr: 待排序的数组
返回: 排序后的数组
"""
# TODO: 实现快速排序的分治逻辑
# 提示：选取第一个元素为枢轴，递归排序左右子数组
def measure_performance(sort_func, data):
start_time = time.perf_counter_ns()
sort_func(data.copy()) # 对数据副本排序，避免影响原数据
end_time = time.perf_counter_ns()
return (end_time - start_time) / 10**6 # 转换为毫秒
#性能测试：对比有序输入和随机输入
sizes = [1000, 5000, 10000]
print("快速排序性能测试（固定枢轴）:")
for n in sizes:
sorted_data = list(range(n))
random_data = [random.randint(0, 10**6) for _ in range(n)]
time_sorted = measure_performance(quick_sort, sorted_data)
time_random = measure_performance(quick_sort, random_data)
print(f"数据规模 n={n}: 有序输入 {time_sorted:.2f} ms, 随机输入 {time_random:.2f} ms")
完成编码并运行测试，报告时间差异。
基于 “划分 - 递归” 核心逻辑，时间复杂度由划分效率（枢轴选择）和递归深度共同决定 三种典型场景：最坏情况、平均情况、最佳情况
最坏情况：每次划分得规模 n-1 和 0 的子数组 平均情况：输入随机 / 等概率选枢轴 最佳情况：每次划分平分数组
快速排序比归并排序更常用的一点在于，快排是“原地的”。
为了避免固定枢轴选择导致的最坏情况，我们可以引入随机化策略优化快速排序。
随机快排在每次划分时随机选择枢轴，从概率上保证划分均衡，从而将最坏情况表现转化为极低概率事件。
理论上可以证明，随机快排对任何输入的期望时间复杂度为
import random
import time
def random_quick_sort(arr):
"""
实现随机快速排序算法（随机选择枢轴）
参数arr: 待排序的数组
返回: 排序后的数组
"""
def quick_sort(arr):
"""
你在上一章实现的快排内容
"""
#验证随机快排在极端有序输入下的性能
n = 10000
sorted_data = list(range(n))
time_fixed = measure_performance(quick_sort, sorted_data)
time_random = measure_performance(random_quick_sort, sorted_data)
print(f"数据规模 n={n}: 固定枢轴快排 {time_fixed:.2f} ms, 随机枢轴快排 {time_random:.2f} ms")