位置: 编程技术 - 正文

快速排序的算法思想及Python版快速排序的实现示例(快速排序的算法流程图)

编辑:rootadmin

推荐整理分享快速排序的算法思想及Python版快速排序的实现示例(快速排序的算法流程图),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:快速排序的算法和性能,快速排序的算法复杂度,快速排序的算法和性能,快速排序的算法原理,快速排序的算法设计,快速排序的算法原理,快速排序的算法原理,快速排序的算法思想,内容如对您有帮助,希望把文章链接给更多的朋友!

快速排序是C.R.A.Hoare于年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。

1.分治法的基本思想

分治法的基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。

2.快速排序的基本思想

设当前待排序的无序区为R[low..high],利用分治法可将快速排序的基本思想描述为:

(1)分解:

在R[low..high]中任选一个记录作为基准(Pivot),以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high],并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key,右边的子区间中所有记录的关键字均大于等于pivot.key,而基准记录pivot则位于正确的位置(pivotpos)上,它无须参加后续的排序。

注意:

快速排序的算法思想及Python版快速排序的实现示例(快速排序的算法流程图)

划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(注意pivot=R[pivotpos]):

R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys

其中low≤pivotpos≤high。

(2)求解:

通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。

(3)组合:

因为当"求解"步骤中的两个递归调用结束时,其左、右两个子区间已有序。对快速排序而言,"组合"步骤无须做什么,可看作是空操作。

Python实现

原理: 先用初始数据, 然后对这个数据进行排序使左边的数据小于该数据,右边的大于该数据,然后用递归的方法对两边的数据进行依次排序。

Python中的复制操作及copy模块中的浅拷贝与深拷贝方法 程序中常常需要复制一个对象,按思路应该是这样的a=[1,2,3]b=a#[1,2,3]printb已经复制好了,但是现在得改变一下第一个元素的值把它改成5b[0]=5#[5,2,3]printb#[5,2

Python编程中对super函数的正确理解和用法解析 当在子类需要调用父类的方法时,在python2.2之前,直接用类名调用类的方法,即非绑定的类方法,并把自身对象self作参数传进去。classA(object):defsay(self):

Python使用ntplib库同步校准当地时间的方法 NTP(NetworkTimeProtocol)是由美国德拉瓦大学的DavidL.Mills教授于年提出,设计用来在Internet上使不同的机器能维持相同时间的一种通讯协定。NTP估算封包

标签: 快速排序的算法流程图

本文链接地址:https://www.jiuchutong.com/biancheng/387022.html 转载请保留说明!

上一篇:Python使用functools模块中的partial函数生成偏函数(python中fun函数怎么用)

下一篇:Python中的复制操作及copy模块中的浅拷贝与深拷贝方法(python复制sheet)

  • 一般纳税人服务费税率
  • 增值税如何进行税收筹划
  • 税金及附加属于营业成本吗
  • 制作费开票属于什么科目
  • 发票上的收款人负法律责任吗
  • 向银行办理托收手续记什么科目
  • 附加税费申报没有怎么填
  • 出口退税逾期申报,需申报出口货物收汇情况表
  • 贷款买车需要到银行去吗
  • 收到员工归还借款属于现金流量表
  • 公司代扣代缴的个人所得税怎么做账
  • 现金长短款的一般处理
  • 冲减以前年度多计的管理费用分录
  • 生产车间维修费
  • 咨询服务费记到什么科目
  • 分公司可以合伙吗
  • 增值税减除后附加税计算方法
  • 物业公司收取水费如何开具发票
  • 增值税普通发票需要交税吗
  • 汽车用品包含
  • 三证合一怎么查询
  • 财务报表中应收账款包括什么
  • 股利分配政策的研究背景
  • 土地平整费计入什么科目
  • 暂估成本后第二年收到发票怎么做账
  • 公司购买自用房产税如何征收
  • 苹果手机上显示
  • 在windows7提供了一种什么技术
  • rds selected
  • 广告行业物料
  • 前端大屏适配几寸显示器
  • 自营 代理
  • 特殊性税务处理弥补亏损限额
  • php文件上传用什么请求方法
  • 明细分类账余额借贷怎么填
  • 委托证券公司发行股票的手续费计入什么科目
  • 大西洋,一望无际的海面
  • 企业期末结转本期实现的各项收入
  • 增值税专票跨月怎么冲红
  • php注释有几种?如何表示?
  • 应交税费应交增值税销项税额
  • 跨域问题是什么
  • 个人以不动产投资入股土地增值税
  • 其他应收款个人挂账很大该怎么处理
  • mongodb 日志
  • 待报解预算收入扣款是什么意思
  • 增值税进项税额转出的情况有哪些
  • sql使用cast进行数据类型转换示例
  • 资产减值损失影响企业利润总额吗
  • 服务费发票的税率
  • 一般纳税人工程劳务发票税率是多少
  • 怎么才能获得音乐
  • 老板怎么从公户拿钱
  • 车船税收费标准
  • 购车融资是什么意思
  • 费用报销单和费用核销单一样吗
  • 公账钱怎么取出
  • mysql(master/slave)主从复制原理及配置图文详解
  • mysql与sqlyog
  • 清空mysql数据库
  • mysql批量执行sql文件
  • Mysql 5.6.37 winx64安装双版本mysql笔记记录
  • sql 查询优化
  • windows2003怎么样
  • win2008 R2 与SP1 PS2无法安装操作系统补丁的解决办法
  • win10 oem key
  • reader_sl.exe - reader_sl进程有什么用.
  • win7更新8007000e
  • cocos2dx官方教程
  • android属性大全
  • 浅析中国式现代化的理论价值与现实意义
  • javascript简明教程
  • vuex的理解
  • js间隔执行的代码
  • javascript面向对象精要pdf
  • jquery设置滚动条高度
  • 生育津贴是分期的吗
  • 云南省新农合网上缴费app
  • 企业所得税地方留存比例2023
  • 我们是在郑州科技市场的一家公司,想找一个代
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设