位置: 编程技术 - 正文

快速排序的算法思想及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)

  • 对方给我开的增值税专票丢失
  • 公司申报个税流程
  • 扣缴义务人和纳税人举例
  • 为什么增值税不计入营业税金及附加
  • 研发费用加计扣除是什么意思啊
  • 劳务报酬怎么申报记账凭证
  • 长期待摊费用摊销年限规定
  • 房产租金收入房产税
  • 现金流量表年报期末现金余额
  • 外币账户间互转流程
  • 出口样品收汇不报关会计分录
  • 税前所得税怎么算
  • 进项税是在抵扣吗
  • 发票查询显示无数据怎么回事
  • 管理费用属于什么现金流量项目
  • 销售房地产要交培训费是传销行为吗
  • 团队建设费用怎么入账
  • 研究开发费用扣除标准
  • 营业外支出怎么冲减
  • 印花税零申报怎么申报不了
  • 出票人账号是付款号吗
  • 股权质押权如何实现
  • 用人单位在职职工年平均工资怎么算
  • 印花税本月计提本月缴纳
  • 付款给对方怎么做分录
  • 累计专项扣除比别人的多
  • 多计提的房产税怎么做分录
  • 补申报以前年度税款
  • hypertrm.exe系统错误
  • 如何选购餐桌椅
  • 微博怎么变成大v
  • 转让专利权的会计处理结果
  • 企业的生产成本等于
  • jar启动指定启动类
  • 库存商品出库怎么计算
  • 应交税费会计分录例题
  • php格式的图片
  • 开关电源pcb布线规则
  • 仓库盘点单模板
  • javascript中文手册
  • CSDN接入AIGC辅助创作,对此你怎么看?
  • 职工教育经费能结转几年
  • 当天的电子发票怎么开
  • 个人提供翻译服务
  • 个人所得税银行卡未实名认证是什么意思
  • 生活办公用品清单
  • 织梦标签理解
  • 代收的运输费用怎么入账
  • 新成品油发票开具的模块解密是?
  • 营业执照注销要钱吗
  • 建筑业跨区域预缴税款的计算
  • 顶账资产入账依据
  • 收到的承兑怎么转给别人
  • 员工报销固定资产怎么算
  • 原材料转固定资产账务处理
  • 退多收的费用计入什么科目
  • 营业外支出会影响所有者权益吗
  • 篮球俱乐部归什么部门管理
  • 其他应收款如何计提坏账准备
  • 股东之间转让股权有优先购买权吗
  • 损益表格式 最新
  • 为什么我们需要政府
  • mysql 5.7.22安装教程
  • solaris ip配置
  • solaris版本查询
  • winsvc是什么进程
  • ubuntu拨号上网设置
  • mac怎么切换输入法
  • 图片缩略图是什么意思
  • SMax4.exe - SMax4是什么进程
  • windows移动中心英文怎么写
  • flash是什么文件夹
  • win8.1锁屏壁纸设置
  • ms-dos7.10如何安装
  • HTML:scrollLeft,scrollWidth,clientWidth,offsetWidth完全详解
  • python流数据
  • python爬虫抓取数据的步骤
  • android的r
  • 河南省人民医院和郑大一附院哪个好
  • 黄石市地方税务局人工客服电话
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

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

    友情链接: 武汉网站建设