搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 达内Python人工智能 > 史上最简单!冒泡、选择排序的Python实现及算法优化详解

史上最简单!冒泡、选择排序的Python实现及算法优化详解

达内Python人工智能 2017-10-30

 Tips:Python免费课程报名中,点击文末“阅读原文”快速抢!


1、排序概念

内部排序和外部排序

根据排序过程中,待排序的数据是否全部被放在内存中,分为两大类:

内部排序:指的是待排序的数据存放在计算机内存中进行的排序过程;

外部排序:指的是排序中要对外存储器进行访问的排序过程。

内部排序是排序的基础,在内部排序中,根据排序过程中所依据的原则可以将它们分为5类:插入排序、交换排序、选择排序、归并排序;根据排序过程的时间复杂度来分,可以分为简单排序、先进排序。冒泡排序、简单选择排序、直接插入排序就是简单排序算法。

评价排序算法优劣的标准主要是两条:一是算法的运算量,这主要是通过记录的比较次数和移动次数来反应;另一个是执行算法所需要的附加存储单元的的多少。

史上最简单!冒泡、选择排序的Python实现及算法优化详解

2、简单排序之冒泡法Python实现及优化

原理图

史上最简单!冒泡、选择排序的Python实现及算法优化详解

史上最简单!冒泡、选择排序的Python实现及算法优化详解

2.1、基本实现

史上最简单!冒泡、选择排序的Python实现及算法优化详解

2.2、优化实现

思路:如果本轮有交互,就说明顺序不对;如果本轮无交换,说明是目标顺序,直接结束排序。

史上最简单!冒泡、选择排序的Python实现及算法优化详解

总结

冒泡法需要数据一轮轮比较。

优化,则可设定一个标记判断此轮是否有数据交换发生,如果没有发生交换,可以结束排序,如果发生交换,继续下一轮排序

最差的排序情况是,初始顺序与目标顺序完全相反,遍历次数1,...,n-1之和n(n-1)/2

最好的排序情况是,初始顺序与目标顺序完全相同,遍历次数n-1

时间复杂度O(n^2)

3、简单排序之选择排序Python实现及优化

选择排序的核心:每一轮比较找到一个极值(最大值或最小值)放到某一端,对剩下的数再找极值,直至比较结束。

原理图

史上最简单!冒泡、选择排序的Python实现及算法优化详解

3.1、基本实现

史上最简单!冒泡、选择排序的Python实现及算法优化详解

3.2、优化实现——二元选择排序

思路:减少迭代次数,一轮确定2个数,即最大数和最小数。

史上最简单!冒泡、选择排序的Python实现及算法优化详解

3.3、等值情况优化

思路:二元选择排序的时候,每一轮可以知道最大值和最小值,如果某一轮最大最小值都一样了,说明剩下的数字都是相等的,直接结束排序。

史上最简单!冒泡、选择排序的Python实现及算法优化详解

3.4、等值情况优化进阶

思路:

[1, 1, 1, 1, 1, 1, 1, 1, 2]  这种情况,找到的最小值索引是-2,最大值索引8,上面的代码会交换2次,最小值两个1交换是无用功,所以,增加一个判断。

史上最简单!冒泡、选择排序的Python实现及算法优化详解

还可能存在一些特殊情况可以优化,但是都属于特例的优化了,对整个算法的提升有限。

总结

简单选择排序需要数据一轮轮比较,并在每一轮中发现极值

没有办法知道当前轮是否已经达到排序要求,但是可以知道极值是否在目标索引位置上

遍历次数1,...,n-1之和n(n-1)/2

时间复杂度O(n^2)

减少了交换次数,提高了效率,性能略好于冒泡法

来源:http://me2xp.blog.51cto.com/6716920/1968672

相关推荐


- 福利 -

现在人工智能爆发,Python是一门脚本语言,它更适合去做人工智能这个领域,在人工智能上使用Python比其他编程语言有更大的优势。

学习一门python语言的前景越来越好,如果想在IT领域发展的话,可以报名达内Python+人工智能课程,点击页面底部“阅读原文”预约免费课程。

回复「课程」查看Python课程详情

回复「教程」下载《Python从入门到精通》60集视频

回复「干货」下载《Python编程入门》电子书

回复「入门」下载《简明Python教程》电子书

版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《史上最简单!冒泡、选择排序的Python实现及算法优化详解》的版权归原作者「Python人工智能」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注Python人工智能微信公众号

Python人工智能微信公众号:python009

Python人工智能

手机扫描上方二维码即可关注Python人工智能微信公众号

Python人工智能最新文章

精品公众号随机推荐