Python实现归并排序-平芜编程栈

Python实现归并排序

defmerge_sort_recursive(arr):""" 归并排序 - 递归实现（最经典版本） 时间: O(n log n) 空间: O(n) - 需要额外数组存储合并结果 """iflen(arr)<=1:returnarr# 1. 分割：找到中间点mid=len(arr)//2# 2. 递归排序左右两半left=merge_sort_recursive(arr[:mid])right=merge_sort_recursive(arr[mid:])# 3. 合并两个有序数组returnmerge(left,right)defmerge(left,right):"""合并两个有序数组"""result=[]i=j=0# 比较两个数组的元素，依次放入结果whilei<len(left)andj<len(right):ifleft[i]<=right[j]:result.append(left[i])i+=1else:result.append(right[j])j+=1# 添加剩余元素result.extend(left[i:])result.extend(right[j:])returnresultdefmerge_sort_inplace(arr,left=0,right=None):""" 归并排序 - 原地版本（不创建新数组切片） 更节省内存，但实现稍复杂 """ifrightisNone:right=len(arr)-1ifleft<right:mid=(left+right)//2# 递归排序左右两半merge_sort_inplace(arr,left,mid)merge_sort_inplace(arr,mid+1,right)# 合并两个有序部分merge_inplace(arr,left,mid,right)defmerge_inplace(arr,left,mid,right):"""原地合并两个有序部分"""# 创建临时数组存储左右部分left_part=arr[left:mid+1]right_part=arr[mid+1:right+1]i=j=0k=left# 合并whilei<len(left_part)andj<len(right_part):ifleft_part[i]<=right_part[j]:arr[k]=left_part[i]i+=1else:arr[k]=right_part[j]j+=1k+=1# 复制剩余元素whilei<len(left_part):arr[k]=left_part[i]i+=1k+=1whilej<len(right_part):arr[k]=right_part[j]j+=1k+=1defmerge_sort_iterative(arr):""" 归并排序 - 迭代版本（自底向上） 避免递归调用，适合超大数据 """n=len(arr)# 当前子数组大小，从1开始，每次翻倍size=1whilesize<n:# 合并相邻的大小为size的子数组forleftinrange(0,n,size*2):mid=min(left+size-1,n-1)right=min(left+size*2-1,n-1)ifmid<right:merge_inplace(arr,left,mid,right)size*=2returnarrdefmerge_sort_with_steps(arr):""" 带步骤输出的归并排序 - 用于理解和调试 """print(f"初始数组:{arr}")print("="*50)defmerge_with_log(left,right,depth=0):indent=" "*depthprint(f"{indent}分割:{left}|{right}")iflen(left)<=1andlen(right)<=1:result=sorted(left+right)print(f"{indent}合并:{left}+{right}={result}")returnresult# 继续分割iflen(left)>1:mid_left=len(left)//2left=merge_with_log(left[:mid_left],left[mid_left:],depth+1)iflen(right)>1:mid_right=len(right)//2right=merge_with_log(right[:mid_right],right[mid_right:],depth+1)# 合并result=[]i=j=0whilei<len(left)andj<len(right):ifleft[i]<=right[j]:result.append(left[i])i+=1else:result.append(right[j])j+=1result.extend(left[i:])result.extend(right[j:])print(f"{indent}合并:{left}+{right}={result}")returnresult result=merge_with_log(arr[:len(arr)//2],arr[len(arr)//2:])print("="*50)print(f"排序结果:{result}")returnresultdefmerge_sort_generator(arr):""" 生成器版本 - 可以逐步获取排序过程中的状态 适合可视化 """iflen(arr)<=1:yieldarrreturnmid=len(arr)//2left_gen=merge_sort_generator(arr[:mid])right_gen=merge_sort_generator(arr[mid:])left=next(left_gen)right=next(right_gen)# 逐步合并result=[]i=j=0whilei<len(left)andj<len(right):ifleft[i]<=right[j]:result.append(left[i])i+=1else:result.append(right[j])j+=1yieldresult+left[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}")# 递归版本arr1=test.copy()result1=merge_sort_recursive(arr1)print(f" 递归版本:{result1}")# 原地版本arr2=test.copy()merge_sort_inplace(arr2)print(f" 原地版本:{arr2}")# 迭代版本arr3=test.copy()merge_sort_iterative(arr3)print(f" 迭代版本:{arr3}")# 验证正确性expected=sorted(test)assertresult1==expected,f"递归版本错误:{result1}!={expected}"assertarr2==expected,f"原地版本错误:{arr2}!={expected}"assertarr3==expected,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")gen=merge_sort_generator(arr)step=1forstateingen:print(f"步骤{step}:{state}")step+=1# ============================================# 性能对比# ============================================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)]# 递归版本arr1=arr.copy()start=time.time()merge_sort_recursive(arr1)time_recursive=time.time()-start# 原地版本arr2=arr.copy()start=time.time()merge_sort_inplace(arr2)time_inplace=time.time()-start# 迭代版本arr3=arr.copy()start=time.time()merge_sort_iterative(arr3)time_iterative=time.time()-startprint(f"{size:<8}{time_recursive:<12.4f}{time_inplace:<12.4f}{time_iterative:<12.4f}")# ============================================# 实用工具函数# ============================================defis_sorted(arr):"""检查数组是否已排序"""returnall(arr[i]<=arr[i+1]foriinrange(len(arr)-1))defget_operation_count(arr):""" 统计归并排序的操作次数 用于演示 O(n log n) 复杂度 """operations={'comparisons':0,'merges':0}defcount_merge(left,right):operations['merges']+=1result=[]i=j=0whilei<len(left)andj<len(right):operations['comparisons']+=1ifleft[i]<=right[j]:result.append(left[i])i+=1else:result.append(right[j])j+=1result.extend(left[i:])result.extend(right[j:])returnresultdefcount_sort(arr):iflen(arr)<=1:returnarr mid=len(arr)//2left=count_sort(arr[:mid])right=count_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:arr=list(range(size,0,-1))# 逆序数组（最坏情况）ops=get_operation_count(arr)n_log_n=size*(size.bit_length()-1)# 近似 n * log2(n)print(f"n={size:<5}: 比较次数={ops['comparisons']:<6}"f"合并次数={ops['merges']:<4}"f"n*log2(n)≈{n_log_n}")