山东网站备案号,自助网站建设公司电话,加强网站人才建设,绿茶直播提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、Python数据结构与算法的详细介绍1.Python中的常用的分治算法2. 分治算法3.详细的分治代码1#xff09;一种常见的分治算法 总结 前言
提示#xff1a;这… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言一、Python数据结构与算法的详细介绍1.Python中的常用的分治算法2. 分治算法3.详细的分治代码1一种常见的分治算法 总结 前言
提示这里可以添加本文要记录的大概内容
第一天Python数据结构与算法的详细介绍 第二天五种常见的排序算法 第三天两种常见的搜索算法 第四天两种常见的递归算法 第五天一种常见的动态规划算法 第六天一种常见的贪心算法 第七天一种常见的分治算法
提示以下是本篇文章正文内容下面案例可供参考
一、Python数据结构与算法的详细介绍
1.Python中的常用的分治算法
以下是Python中的一些常用算法
2. 分治算法 分治算法 将问题划分为几个规模较小的子问题分别解决然后将子问题的解合并得到原问题的解。快速排序和归并排序是分治算法的典型例子。 3.详细的分治代码
1一种常见的分治算法
def quick_sort(arr):# 快速排序的主函数def partition(low, high):# 选择最右边的元素作为基准pivot arr[high]i low - 1 # 较小元素的索引for j in range(low, high):# 如果当前元素小于或等于基准if arr[j] pivot:i 1# 交换arr[i]和arr[j]arr[i], arr[j] arr[j], arr[i]# 交换arr[i 1]和arr[high] (或基准)arr[i 1], arr[high] arr[high], arr[i 1]return i 1# 基本情况如果数组为空或只有一个元素则直接返回if len(arr) 1:return arrelse:# 递归地对数组进行排序pivot_index partition(0, len(arr) - 1)left_arr quick_sort(arr[:pivot_index])right_arr quick_sort(arr[pivot_index 1:])# 合并排序后的数组这里实际上没有真正的合并操作因为数组是就地排序的# 但为了保持函数调用的完整性我们仍然返回合并后的结果即原数组return left_arr [arr[pivot_index]] right_arr# 注意在实际应用中为了效率我们通常不会真的将数组拆分再合并
# 因为Python的列表切片操作是O(n)时间复杂度的。这里的返回语句只是为了演示分治的思想。
# 在实际实现中我们会在原地对数组进行排序避免额外的空间开销。# 归并排序的实现
def merge_sort(arr):# 归并排序的主函数def merge(left, right):sorted_array []i j 0# 合并两个已排序的数组while i len(left) and j len(right):if left[i] right[j]:sorted_array.append(left[i])i 1else:sorted_array.append(right[j])j 1# 添加剩余的元素如果有sorted_array.extend(left[i:])sorted_array.extend(right[j:])return sorted_array# 基本情况如果数组为空或只有一个元素则直接返回if len(arr) 1:return arrelse:# 找到数组的中间点将数组分为两部分mid len(arr) // 2left_half merge_sort(arr[:mid])right_half merge_sort(arr[mid:])# 合并两个已排序的部分return merge(left_half, right_half)# 测试代码
if __name__ __main__:test_array [38, 27, 43, 3, 9, 82, 10]print(Original array:, test_array)# 使用快速排序quick_sorted_array quick_sort(test_array[:]) # 使用切片创建数组的副本以避免修改原数组print(Quick sorted array:, quick_sorted_array)# 使用归并排序merge_sorted_array merge_sort(test_array[:]) # 同样使用切片print(Merge sorted array:, merge_sorted_array)总结
提示这里对文章进行总结 例如以上就是今天要讲的内容本文简单介绍一种常见的分治算法。
