当前位置: 首页 > news >正文

【第七天】零基础入门刷题Python-算法篇-数据结构与算法的介绍-一种常见的分治算法(持续更新)

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

文章目录

  • 前言
  • 一、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)

总结

提示:这里对文章进行总结:
例如:以上就是今天要讲的内容,本文简单介绍一种常见的分治算法。

http://www.lryc.cn/news/526496.html

相关文章:

  • Spring Data JPA 实战:构建高性能数据访问层
  • Python JSON:深入解析与高效应用
  • 【C语言进阶(四)】指针进阶详解(上)
  • DDD架构实战第五讲总结:将领域模型转化为代码
  • FPGA实现任意角度视频旋转(完结)视频任意角度旋转实现
  • CPU 缓存基础知识
  • 微信小程序date picker的一些说明
  • Vue3 + TS 实现批量拖拽 文件夹和文件 组件封装
  • 【Kubernetes】Pod生命周期、初始化容器、主容器
  • 2025牛客寒假训练营1-M题
  • css3 svg制作404页面动画效果HTML源码
  • 序列标注:从传统到现代,NLP中的标签预测技术全解析
  • 软件测试 —— 性能测试(jmeter)
  • python介绍ransac算法拟合圆
  • WPS计算机二级•表格保护与打印
  • Vue组件开发-使用xlsx库导出Excel文件
  • 使用 Pipeline 提高 Redis 批量操作性能
  • 「 机器人 」利用冲程对称性调节实现仿生飞行器姿态与方向控制
  • 第十五届蓝桥杯大赛软件赛省赛C/C++ 大学 B 组
  • 本地大模型编程实战(02)语义检索(1)
  • 自定义命令执行器:C++中命令封装的深度探索(C/C++实现)
  • C语言程序设计十大排序—选择排序
  • C语言初阶牛客网刷题——HJ73 计算日期到天数转换【难度:简单】
  • MATLAB中alphanumericsPattern函数用法
  • 人工智能在教育领域的创新应用与前景展望
  • 约束布局 ConstraintLayout
  • 校园商铺管理系统设计与实现(代码+数据库+LW)
  • react native在windows环境搭建并使用脚手架新建工程
  • vulnhub DC-1靶机 walkthrough
  • 计算机网络 (58)无线局域网WLAN