Python实现归并排序

Python实现归并排序defmerge_sort_recursive(arr): 归并排序 - 递归实现最经典版本 时间: O(n log n) 空间: O(n) - 需要额外数组存储合并结果 iflen(arr)1:returnarr# 1. 分割找到中间点midlen(arr)//2# 2. 递归排序左右两半leftmerge_sort_recursive(arr[:mid])rightmerge_sort_recursive(arr[mid:])# 3. 合并两个有序数组returnmerge(left,right)defmerge(left,right):合并两个有序数组result[]ij0# 比较两个数组的元素依次放入结果whileilen(left)andjlen(right):ifleft[i]right[j]:result.append(left[i])i1else:result.append(right[j])j1# 添加剩余元素result.extend(left[i:])result.extend(right[j:])returnresultdefmerge_sort_inplace(arr,left0,rightNone): 归并排序 - 原地版本不创建新数组切片 更节省内存但实现稍复杂 ifrightisNone:rightlen(arr)-1ifleftright:mid(leftright)//2# 递归排序左右两半merge_sort_inplace(arr,left,mid)merge_sort_inplace(arr,mid1,right)# 合并两个有序部分merge_inplace(arr,left,mid,right)defmerge_inplace(arr,left,mid,right):原地合并两个有序部分# 创建临时数组存储左右部分left_partarr[left:mid1]right_partarr[mid1:right1]ij0kleft# 合并whileilen(left_part)andjlen(right_part):ifleft_part[i]right_part[j]:arr[k]left_part[i]i1else:arr[k]right_part[j]j1k1# 复制剩余元素whileilen(left_part):arr[k]left_part[i]i1k1whilejlen(right_part):arr[k]right_part[j]j1k1defmerge_sort_iterative(arr): 归并排序 - 迭代版本自底向上 避免递归调用适合超大数据 nlen(arr)# 当前子数组大小从1开始每次翻倍size1whilesizen:# 合并相邻的大小为size的子数组forleftinrange(0,n,size*2):midmin(leftsize-1,n-1)rightmin(leftsize*2-1,n-1)ifmidright:merge_inplace(arr,left,mid,right)size*2returnarrdefmerge_sort_with_steps(arr): 带步骤输出的归并排序 - 用于理解和调试 print(f初始数组:{arr})print(*50)defmerge_with_log(left,right,depth0):indent *depthprint(f{indent}分割:{left}|{right})iflen(left)1andlen(right)1:resultsorted(leftright)print(f{indent}合并:{left}{right}{result})returnresult# 继续分割iflen(left)1:mid_leftlen(left)//2leftmerge_with_log(left[:mid_left],left[mid_left:],depth1)iflen(right)1:mid_rightlen(right)//2rightmerge_with_log(right[:mid_right],right[mid_right:],depth1)# 合并result[]ij0whileilen(left)andjlen(right):ifleft[i]right[j]:result.append(left[i])i1else:result.append(right[j])j1result.extend(left[i:])result.extend(right[j:])print(f{indent}合并:{left}{right}{result})returnresult resultmerge_with_log(arr[:len(arr)//2],arr[len(arr)//2:])print(*50)print(f排序结果:{result})returnresultdefmerge_sort_generator(arr): 生成器版本 - 可以逐步获取排序过程中的状态 适合可视化 iflen(arr)1:yieldarrreturnmidlen(arr)//2left_genmerge_sort_generator(arr[:mid])right_genmerge_sort_generator(arr[mid:])leftnext(left_gen)rightnext(right_gen)# 逐步合并result[]ij0whileilen(left)andjlen(right):ifleft[i]right[j]:result.append(left[i])i1else:result.append(right[j])j1yieldresultleft[i:]right[j:]result.extend(left[i:])result.extend(right[j:])yieldresult# # 测试代码# deftest_merge_sort():测试各种归并排序实现test_cases[[64,34,25,12,22,11,90],[5,2,4,6,1,3],[1,2,3,4,5],# 已排序[5,4,3,2,1],# 逆序[1],# 单元素[],# 空数组[3,3,3,3],# 重复元素]print(*60)print(测试归并排序实现)print(*60)fori,testinenumerate(test_cases,1):print(f\n测试用例{i}:{test})# 递归版本arr1test.copy()result1merge_sort_recursive(arr1)print(f 递归版本:{result1})# 原地版本arr2test.copy()merge_sort_inplace(arr2)print(f 原地版本:{arr2})# 迭代版本arr3test.copy()merge_sort_iterative(arr3)print(f 迭代版本:{arr3})# 验证正确性expectedsorted(test)assertresult1expected,f递归版本错误:{result1}!{expected}assertarr2expected,f原地版本错误:{arr2}!{expected}assertarr3expected,f迭代版本错误:{arr3}!{expected}print(\n*60)print(✓ 所有测试通过)print(*60)defdemo_step_by_step():演示逐步执行的归并排序print(\n*60)print(逐步演示归并排序)print(*60)arr[38,27,43,3,9,82,10]print(f\n原始数组:{arr}\n)# 使用带步骤输出的版本merge_sort_with_steps(arr)defdemo_generator():演示生成器版本 - 逐步获取排序状态print(\n*60)print(生成器版本 - 逐步获取排序状态)print(*60)arr[38,27,43,3,9,82,10]print(f原始数组:{arr}\n)genmerge_sort_generator(arr)step1forstateingen:print(f步骤{step}:{state})step1# # 性能对比# defperformance_comparison():比较不同实现的性能importtimeimportrandom sizes[100,1000,5000,10000]print(\n*60)print(性能对比 (秒))print(*60)print(f{大小:8}{递归版本:12}{原地版本:12}{迭代版本:12})print(-*50)forsizeinsizes:arr[random.randint(1,10000)for_inrange(size)]# 递归版本arr1arr.copy()starttime.time()merge_sort_recursive(arr1)time_recursivetime.time()-start# 原地版本arr2arr.copy()starttime.time()merge_sort_inplace(arr2)time_inplacetime.time()-start# 迭代版本arr3arr.copy()starttime.time()merge_sort_iterative(arr3)time_iterativetime.time()-startprint(f{size:8}{time_recursive:12.4f}{time_inplace:12.4f}{time_iterative:12.4f})# # 实用工具函数# defis_sorted(arr):检查数组是否已排序returnall(arr[i]arr[i1]foriinrange(len(arr)-1))defget_operation_count(arr): 统计归并排序的操作次数 用于演示 O(n log n) 复杂度 operations{comparisons:0,merges:0}defcount_merge(left,right):operations[merges]1result[]ij0whileilen(left)andjlen(right):operations[comparisons]1ifleft[i]right[j]:result.append(left[i])i1else:result.append(right[j])j1result.extend(left[i:])result.extend(right[j:])returnresultdefcount_sort(arr):iflen(arr)1:returnarr midlen(arr)//2leftcount_sort(arr[:mid])rightcount_sort(arr[mid:])returncount_merge(left,right)count_sort(arr.copy())returnoperations# # 主程序# if__name____main__:# 运行测试test_merge_sort()# 演示逐步执行demo_step_by_step()# 演示生成器demo_generator()# 性能对比performance_comparison()# 统计操作次数演示 O(n log n)print(\n*60)print(验证 O(n log n) 复杂度)print(*60)sizes[10,100,1000,5000]forsizeinsizes:arrlist(range(size,0,-1))# 逆序数组最坏情况opsget_operation_count(arr)n_log_nsize*(size.bit_length()-1)# 近似 n * log2(n)print(fn{size:5}: 比较次数{ops[comparisons]:6}f合并次数{ops[merges]:4}fn*log2(n)≈{n_log_n})主要特点1.四种实现方式merge_sort_recursive: 递归版本最直观merge_sort_inplace: 原地版本省内存merge_sort_iterative: 迭代版本无递归merge_sort_generator: 生成器版本逐步输出2.辅助功能逐步执行演示性能对比测试操作次数统计验证 O(n log n)完整的测试用例3.核心要点分治思想分割 → 排序 → 合并稳定性相等元素保持原顺序空间复杂度O(n) 需要额外空间时间复杂度O(n log n) 始终如一