我来为你写一个Python版本的快速排序，使用分治策略，当子数组大小小于等于 n/16 时不再递归：
importrandomimportsysfromtypingimportList,Tuplefromcollectionsimportdequedefquick_sort_recursive(arr:List[int])->List[int]:""" 递归版本的快速排序，当子数组大小 <= len(arr)//16 时停止递归 """iflen(arr)<=1:returnarr# 当子数组大小 <= n/16 时，不再继续分割min_partition_size=max(1,len(arr)//16)def_quick_sort_recursive(arr:List[int],left:int,right:int)->None:"""内部递归函数"""ifleft>=right:return# 如果当前区间大小 <= min_partition_size，不继续分割ifright-left+1<=min_partition_size:return# 选择枢纽元素（三数取中法）mid=left+(right-left)//2# 找到左、中、右三个元素的中值作为枢纽ifarr[left]>arr[mid]:arr[left],arr[mid]=arr[mid],arr[left]ifarr[left]>arr[right]:arr[left],arr[right]=arr[right],arr[left]ifarr[mid]>arr[right]:arr[mid],arr[right]=arr[right],arr[mid]# 将中值交换到right-1位置arr[mid],arr[right-1]=arr[right-1],arr[mid]pivot=arr[right-1]# 分区操作i,j=left,right-1whileTrue:i+=1whilearr[i]<pivot:i+=1j-=1whilearr[j]>pivot:j-=1ifi<j:arr[i],arr[j]=arr[j],arr[i]else:break# 恢复枢纽位置arr[i],arr[right-1]=arr[right-1],arr[i]# 递归排序左右子数组_quick_sort_recursive(arr,left,i-1)_quick_sort_recursive(arr,i+1,right)# 创建数组副本进行排序arr_copy=arr.copy()_quick_sort_recursive(arr_copy,0,len(arr_copy)-1)# 对小分区进行插入排序（因为递归停止了，所以需要排序小分区）returninsertion_sort(arr_copy)defquick_sort_iterative(arr:List[int])->List[int]:""" 迭代版本的快速排序，使用栈代替递归 当子数组大小 <= len(arr)//16 时停止分割 """iflen(arr)<=1:returnarr arr_copy=arr.copy()n=len(arr_copy)min_partition_size=max(1,n//16)# 使用栈存储需要排序的区间stack=[(0,n-1)]whilestack:left,right=stack.pop()# 如果区间大小 <= min_partition_size，跳过ifright-left+1<=min_partition_size:continue# 选择枢纽元素（三数取中法）mid=left+(right-left)//2# 找到左、中、右三个元素的中值ifarr_copy[left]>arr_copy[mid]:arr_copy[left],arr_copy[mid]=arr_copy[mid],arr_copy[left]ifarr_copy[left]>arr_copy[right]:arr_copy[left],arr_copy[right]=arr_copy[right],arr_copy[left]ifarr_copy[mid]>arr_copy[right]:arr_copy[mid],arr_copy[right]=arr_copy[right],arr_copy[mid]# 将中值交换到right-1位置ifright-left>2:arr_copy[mid],arr_copy[right-1]=arr_copy[right-1],arr_copy[mid]pivot=arr_copy[right-1]else:pivot=arr_copy[mid]# 分区操作ifright-left>2:i,j=left,right-1whileTrue:i+=1whilearr_copy[i]<pivot:i+=1j-=1whilearr_copy[j]>pivot:j-=1ifi<j:arr_copy[i],arr_copy[j]=arr_copy[j],arr_copy[i]else:break# 恢复枢纽位置arr_copy[i],arr_copy[right-1]=arr_copy[right-1],arr_copy[i]else:# 对于小数组直接排序ifarr_copy[left]>arr_copy[right]:arr_copy[left],arr_copy[right]=arr_copy[right],arr_copy[left]i=left# 将较大的子区间先入栈，较小的后入栈（减少栈深度）left_size=i-left right_size=right-iifleft_size>right_size:ifright-(i+1)+1>min_partition_size:stack.append((i+1,right))if(i-1)-left+1>min_partition_size:stack.append((left,i-1))else:if(i-1)-left+1>min_partition_size:stack.append((left,i-1))ifright-(i+1)+1>min_partition_size:stack.append((i+1,right))# 对小分区进行插入排序returninsertion_sort(arr_copy)defquick_sort_hybrid(arr:List[int])->List[int]:""" 混合排序：快速排序 + 插入排序 当子数组大小 <= len(arr)//16 时使用插入排序 """iflen(arr)<=1:returnarr arr_copy=arr.copy()n=len(arr_copy)insertion_threshold=max(1,n//16)def_quick_sort_hybrid(arr:List[int],left:int,right:int)->None:"""内部递归函数，混合排序"""# 如果区间大小 <= 阈值，使用插入排序ifright-left+1<=insertion_threshold:# 对小区间使用插入排序foriinrange(left+1,right+1):key=arr[i]j=i-1whilej>=leftandarr[j]>key:arr[j+1]=arr[j]j-=1arr[j+1]=keyreturn# 快速排序分区# 选择枢纽（随机选择）pivot_idx=random.randint(left,right)arr[pivot_idx],arr[right]=arr[right],arr[pivot_idx]pivot=arr[right]# 分区操作i=left-1forjinrange(left,right):ifarr[j]<=pivot:i+=1arr[i],arr[j]=arr[j],arr[i]arr[i+1],arr[right]=arr[right],arr[i+1]partition_idx=i+1# 递归排序左右子数组_quick_sort_hybrid(arr,left,partition_idx-1)_quick_sort_hybrid(arr,partition_idx+1,right)_quick_sort_hybrid(arr_copy,0,n-1)returnarr_copydefinsertion_sort(arr:List[int])->List[int]:"""插入排序，用于处理小数组"""iflen(arr)<=1:returnarr arr_copy=arr.copy()n=len(arr_copy)foriinrange(1,n):key=arr_copy[i]j=i-1# 将比key大的元素向右移动whilej>=0andarr_copy[j]>key:arr_copy[j+1]=arr_copy[j]j-=1arr_copy[j+1]=keyreturnarr_copydefquick_sort_simple(arr:List[int],threshold_ratio:float=1/16)->List[int]:""" 简单版本的快速排序，易于理解 当子数组大小 <= len(arr)*threshold_ratio 时停止分割 """iflen(arr)<=1:returnarr# 计算停止递归的阈值threshold=max(1,int(len(arr)*threshold_ratio))def_sort(arr:List[int])->List[int]:iflen(arr)<=threshold:# 对小数组使用插入排序returninsertion_sort(arr)# 选择枢纽元素pivot=arr[len(arr)//2]# 分区left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]# 递归排序并合并return_sort(left)+middle+_sort(right)return_sort(arr.copy())deftest_quick_sort():"""测试函数"""print("测试快速排序算法...")# 测试用例test_cases=[[],[1],[5,2,8,1,9],[9,8,7,6,5,4,3,2,1],[1,2,3,4,5],[3,1,4,1,5,9,2,6,5,3,5],random.sample(range(1000),100),# 随机数组]algorithms=[("递归快速排序",quick_sort_recursive),("迭代快速排序",quick_sort_iterative),("混合快速排序",quick_sort_hybrid),("简单快速排序",quick_sort_simple),]forname,sort_funcinalgorithms:print(f"\n{name}:")fori,test_arrinenumerate(test_cases):try:sorted_arr=sort_func(test_arr)expected=sorted(test_arr)assertsorted_arr==expected,f"测试用例{i}失败"print(f" 测试用例{i}: ✓")exceptAssertionErrorase:print(f" 测试用例{i}: ✗{e}")# 性能测试print("\n性能测试（排序10000个随机数）:")large_array=random.sample(range(100000),10000)forname,sort_funcinalgorithms:importtime start_time=time.time()sorted_arr=sort_func(large_array)end_time=time.time()# 验证排序结果assertsorted_arr==sorted(large_array),f"{name}排序结果错误"print(f"{name}:{end_time-start_time:.4f}秒")defvisualize_partitions():"""可视化分区过程"""print("\n可视化分区过程:")arr=[random.randint(1,100)for_inrange(64)]print(f"原始数组 ({len(arr)}个元素):")print(arr)n=len(arr)threshold=max(1,n//16)# 4print(f"\n停止递归的阈值:{threshold}个元素")print("\n分区过程:")def_visualize(arr,depth=0):iflen(arr)<=threshold:print(" "*depth+f"小分区[{len(arr)}]:{arr[:10]}{'...'iflen(arr)>10else''}")return# 选择枢纽pivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]print(" "*depth+f"分区[{len(arr)}], 枢纽={pivot}:")print(" "*depth+f" 左子数组:{len(left)}个元素")print(" "*depth+f" 中（枢纽）:{len(middle)}个元素")print(" "*depth+f" 右子数组:{len(right)}个元素")# 递归可视化_visualize(left,depth+1)_visualize(right,depth+1)_visualize(arr)if__name__=="__main__":# 设置递归深度限制sys.setrecursionlimit(10000)# 运行测试test_quick_sort()# 可视化分区过程visualize_partitions()print("\n使用说明:")print("1. quick_sort_recursive: 递归版本，当子数组 <= n/16 时停止递归")print("2. quick_sort_iterative: 迭代版本，使用栈避免递归深度问题")print("3. quick_sort_hybrid: 混合版本，小数组用插入排序")print("4. quick_sort_simple: 简单版本，易于理解")print("\n推荐使用 quick_sort_hybrid 或 quick_sort_iterative")算法特点
- 分治策略
· 当子数组大小 ≤ n/16 时停止进一步分割
· 避免对小数组进行不必要的递归调用
- 优化技巧
· 三数取中法：选择更好的枢纽元素，避免最坏情况
· 插入排序：对小数组使用插入排序（时间复杂度 O(n²)但在小规模数据上更快）
· 尾递归优化：较小的子数组先处理，减少递归深度
- 不同实现版本
· 递归版本：代码简洁，但可能栈溢出
· 迭代版本：使用栈代替递归，避免栈溢出
· 混合版本：结合快速排序和插入排序的优点
· 简单版本：易于理解的教学版本
- 性能分析
· 平均时间复杂度：O(n log n)
· 最坏情况：O(n²)（但通过三数取中法大大降低了概率）
· 空间复杂度：O(log n)（递归栈深度）
使用示例
# 最简单的方式arr=[5,2,8,1,9,3,7,4,6]sorted_arr=quick_sort_simple(arr)print(sorted_arr)# [1, 2, 3, 4, 5, 6, 7, 8, 9]# 推荐使用混合版本（性能最好）sorted_arr=quick_sort_hybrid(arr)# 或者使用迭代版本（避免递归深度问题）sorted_arr=quick_sort_iterative(arr)参数调整
你可以调整停止递归的阈值：
# 当子数组大小 <= n/8 时停止递归sorted_arr=quick_sort_simple(arr,threshold_ratio=1/8)# 当子数组大小 <= n/32 时停止递归sorted_arr=quick_sort_simple(arr,threshold_ratio=1/32)这种分治策略在数据量较大时特别有效，因为它减少了递归调用的开销，同时利用插入排序在小数据集上的优势。
