您当前的位置:首页 > 电脑百科 > 程序开发 > 程序员

用Python实现十大经典排序算法-插入、选择、快速、冒泡、归并等

时间:2020-06-21 22:43:11  来源:  作者:

本文来用图文的方式详细讲解了Python十大经典排序算法 —— 插入排序、选择排序、快速排序、冒泡排序、归并排序、希尔排序、插入排序、桶排序、基数排序、计数排序算法,想要学习的你们,继续阅读下去吧,如果觉得不错的话,推荐给身边的朋友吧。

插入排序

思路

  1. 从第一个元素开始,该元素可以认为已经被排序;
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置;
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
  5. 将新元素插入到该位置;
  6. 重复步骤2~5。

代码

用Python实现十大经典排序算法-插入、选择、快速、冒泡、归并等

 

图示

用Python实现十大经典排序算法-插入、选择、快速、冒泡、归并等

 

平均时间复杂度

O(n^2)

希尔排序

前言

希尔排序是插排的升级,先将待排序的元素进行分组,在分组的基础上进行插排,从而降低整体上的时间复杂度。

这里面设计到一个增量的概念,我们依据增量来决定分组的跨度。常用的增量有三种:

  • 希尔增量 [1,2,4,8,…,2^(k-1)]
  • 海巴德增量 [1,3,7,15,…,2^k-1]
  • 塞基维克增量 [1,5,19,41,…,4k-3*2k+1]

一般情况下希尔增量带来的时间复杂度小于O(n2),但在极坏情况下可能效果不明显甚至超过这个值。海巴德增量可以将时间复杂控制在O(n(3/2))以下,而塞基维克增量该项参数为O(n^(4/3))。

思路

  1. 择定增量
  2. 分组
  3. 组内比较
  4. 重复步骤2,3直到跨度为1

图示

用Python实现十大经典排序算法-插入、选择、快速、冒泡、归并等

 

代码

用Python实现十大经典排序算法-插入、选择、快速、冒泡、归并等

 

选择排序

思路

  1. 选出数组中最大(最小)的元素放到开头
  2. 在剩下的元素中选中最大(最小)元素放到上个被选元素之后
  3. 重复2步骤

图示

用Python实现十大经典排序算法-插入、选择、快速、冒泡、归并等

 

代码

用Python实现十大经典排序算法-插入、选择、快速、冒泡、归并等

 

平均时间复杂度

O(n^2)

堆排序

前言

堆排序,顾名思义,就是基于堆。因此先来介绍一下堆的概念。

堆分为最大堆和最小堆,其实就是完全二叉树。最大堆要求节点的元素都要大于其孩子,最小堆要求节点元素都小于其左右孩子,两者对左右孩子的大小关系不做任何要求,其实很好理解。有了上面的定义,我们可以得知,处于最大堆的根节点的元素一定是这个堆中的最大值。其实我们的堆排序算法就是抓住了堆的这一特点,每次都取堆顶的元素,将其放在序列最后面,然后将剩余的元素重新调整为最大堆,依次类推,最终得到排序的序列。

思路

  1. 把堆顶的最大数取出
  2. 将剩余的堆继续调整为最大堆
  3. 重复步骤1,2

图示

用Python实现十大经典排序算法-插入、选择、快速、冒泡、归并等

 

代码

用Python实现十大经典排序算法-插入、选择、快速、冒泡、归并等

 


用Python实现十大经典排序算法-插入、选择、快速、冒泡、归并等

 

平均时间复杂度

O(nlogn)

冒泡排序

思路

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

图示

用Python实现十大经典排序算法-插入、选择、快速、冒泡、归并等

 

代码

用Python实现十大经典排序算法-插入、选择、快速、冒泡、归并等

 

平均时间复杂度

O(n^2)

快速排序

思路

  1. 先从集合中取出一个数作为“哨兵”
  2. 将集合中比哨兵大的元素和比哨兵小的元素分列两侧
  3. 再对左右区间重复第二步,直到各区间只有一个数

图示

用Python实现十大经典排序算法-插入、选择、快速、冒泡、归并等

 

代码

用Python实现十大经典排序算法-插入、选择、快速、冒泡、归并等

 

平均时间复杂度

O(nlogn)

归并排序

思路

  1. 将列表拆分成两个有序子模块
  2. 递归拆分
  3. 子模块内部进行排序并合并成大的模块
  4. 递归合并

图示

用Python实现十大经典排序算法-插入、选择、快速、冒泡、归并等

 

代码

用Python实现十大经典排序算法-插入、选择、快速、冒泡、归并等

 

平均时间复杂度

O(nlogn)

计数排序

思路

  1. 找出集合中最小数m和最大数n
  2. 建一个长为(m-n+1)的列表count_list,所有元素初始化为0
  3. 遍历集合,元素减去n得到的结果作为index,将count_list该位上的元素加1。
  4. 初始化空列表result。
  5. 将count_list序列化,用索引值减去n,得到的结果追加到result中,索引值对应的位元素值减1,直到它为0。
  6. 重复步骤5。

图示

用Python实现十大经典排序算法-插入、选择、快速、冒泡、归并等

 

代码

用Python实现十大经典排序算法-插入、选择、快速、冒泡、归并等

 

平均时间复杂度

O(n)

桶排序

前言

桶排序是将待排序集合中处于同一个值域的元素存入同一个桶中,也就是根据元素值特性将集合拆分为多个区域,则拆分后形成的多个桶,从值域上看是处于有序状态的。对每个桶中元素进行排序,则所有桶中元素构成的集合是已排序的。

思路

  1. 根据待排序集合中最大元素和最小元素的差值范围和映射规则,确定申请的桶个数;
  2. 遍历待排序集合,将每一个元素移动到对应的桶中;
  3. 对每一个桶中元素进行排序,并移动到已排序集合中。

图示

用Python实现十大经典排序算法-插入、选择、快速、冒泡、归并等

 

代码

用Python实现十大经典排序算法-插入、选择、快速、冒泡、归并等

 

平均时间复杂度

O(n^2)

基数排序

思路

  1. 首先根据个位数的数值,在走访数值时将它们分配至编号0到9的桶中;
  2. 接下来将这些桶中的数值重新串接起来,成为以下的数列。接着再进行一次分配,这次是根据十位数来分配;
  3. 接下来将这些桶中的数值重新串接起来,持续进行以上的动作直至最高位数为止。

图示

用Python实现十大经典排序算法-插入、选择、快速、冒泡、归并等

 

代码

用Python实现十大经典排序算法-插入、选择、快速、冒泡、归并等

 

平均时间复杂度

O(d*2*n), 这里的d是数值位数

本文来自热心好友原味吐司的投稿,点赞!

更多有关python、深度学习和计算机编程的精彩内容,可以关注微信公众号:哆啦A梦爱学习

用Python实现十大经典排序算法-插入、选择、快速、冒泡、归并等

 


用Python实现十大经典排序算法-插入、选择、快速、冒泡、归并等

 



Tags:Python   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
大家好,我是菜鸟哥,今天跟大家一起聊一下Python4的话题! 从2020年的1月1号开始,Python官方正式的停止了对于Python2的维护。Python也正式的进入了Python3的时代。而随着时间的...【详细内容】
2021-12-28  Tags: Python  点击:(1)  评论:(0)  加入收藏
学习Python的初衷是因为它的实践的便捷性,几乎计算机上能完成的各种操作都能在Python上找到解决途径。平时工作需要在线学习。而在线学习的复杂性经常让人抓狂。费时费力且效...【详细内容】
2021-12-28  Tags: Python  点击:(1)  评论:(0)  加入收藏
Python 是一个很棒的语言。它是世界上发展最快的编程语言之一。它一次又一次地证明了在开发人员职位中和跨行业的数据科学职位中的实用性。整个 Python 及其库的生态系统使...【详细内容】
2021-12-27  Tags: Python  点击:(2)  评论:(0)  加入收藏
菜单驱动程序简介菜单驱动程序是通过显示选项列表从用户那里获取输入并允许用户从选项列表中选择输入的程序。菜单驱动程序的一个简单示例是 ATM(自动取款机)。在交易的情况下...【详细内容】
2021-12-27  Tags: Python  点击:(4)  评论:(0)  加入收藏
近日只是为了想尽办法为 Flask 实现 Swagger UI 文档功能,基本上要让 Flask 配合 Flasgger, 所以写了篇 Flask 应用集成 Swagger UI 。然而不断的 Google 过程中偶然间发现了...【详细内容】
2021-12-23  Tags: Python  点击:(6)  评论:(0)  加入收藏
有不少同学学完Python后仍然很难将其灵活运用。我整理15个Python入门的小程序。在实践中应用Python会有事半功倍的效果。01 实现二元二次函数实现数学里的二元二次函数:f(x,...【详细内容】
2021-12-22  Tags: Python  点击:(32)  评论:(0)  加入收藏
Verilog是由一个个module组成的,下面是其中一个module在网表中的样子,我只需要提取module名字、实例化关系。module rst_filter ( ...); 端口声明... wire定义......【详细内容】
2021-12-22  Tags: Python  点击:(8)  评论:(0)  加入收藏
运行环境 如何从 MP4 视频中提取帧 将帧变成 GIF 创建 MP4 到 GIF GUI ...【详细内容】
2021-12-22  Tags: Python  点击:(6)  评论:(0)  加入收藏
面向对象:Object Oriented Programming,简称OOP,即面向对象程序设计。类(Class)和对象(Object)类是用来描述具有相同属性和方法对象的集合。对象是类的具体实例。比如,学生都有...【详细内容】
2021-12-22  Tags: Python  点击:(9)  评论:(0)  加入收藏
所谓内置函数,就是Python提供的, 可以直接拿来直接用的函数,比如大家熟悉的print,range、input等,也有不是很熟,但是很重要的,如enumerate、zip、join等,Python内置的这些函数非常...【详细内容】
2021-12-21  Tags: Python  点击:(5)  评论:(0)  加入收藏
▌简易百科推荐
我 2010 年开始在 Github 上开源自己的代码。在 push 代码之前我根本没想过为什么。只是因为我当时学了 git,而且我又觉得 Github 很方便,可以用来备份自己的代码。而后我就参...【详细内容】
2021-12-28  程序员的喵    Tags:Github   点击:(2)  评论:(0)  加入收藏
JAVA开发工程师(北京)本科 3-5年经验 面议 (招1人)岗位职责:1.负责我行应用系统的设计,完成软件编码工作,负责管理代码设计规范等工作;2.根据应用需求分析说明书,评估需求研发的可行...【详细内容】
2021-12-27  just do丶IT公众号    Tags:国企   点击:(2)  评论:(0)  加入收藏
今天聊聊编程的本质。程序就是数据结构+控制+逻辑,程序员编程工作的本质是翻译,翻译机要来了,程序员怎么办?黑客帝国中的程序黑客帝国4就要上映了,不知道前三部你看懂了么?值得多...【详细内容】
2021-12-17  博士聊IT    Tags:程序员   点击:(9)  评论:(0)  加入收藏
梦醒之后,每个人对于这份职业的未来、互联网行业的未来,以及更重要的,自己的未来都有了更现实的判断 文 | 祝颖丽编辑 | 黄俊杰一个生于 1986 年的人,他所走过的前半生:从出生起,...【详细内容】
2021-12-03    财经杂志  Tags:程序员   点击:(16)  评论:(0)  加入收藏
前些天在头条看到一个八二年的哥们,述说自己找工作屡次被拒的问题,在网上引起了广泛的讨论,这件事给我留下了很深的印象,因为这哥们和我同是程序员,都人到中年,上有老下有小。唯一...【详细内容】
2021-12-01  云南贤哥在深圳    Tags:程序员   点击:(20)  评论:(0)  加入收藏
很多读者都问过一个问题:程序员如何实现高速成长?之前也写过相关的文章,强调的主要是夯实计算机体系基础知识。 再说另一个诀窍:多看经典开源项目,这些项目大多是众多顶尖程序员...【详细内容】
2021-11-30  findyi    Tags:程序员   点击:(15)  评论:(0)  加入收藏
近日,一位45岁的网民在中国政府网留言求职,引发关注。该网民自称是一名软件开发人员,今年45岁,精通各种技术体系,“而我辞职回家半年后再回来寻找工作机会的时候,却发现连个面试...【详细内容】
2021-11-17  郭主任    Tags:程序员   点击:(42)  评论:(0)  加入收藏
即使在安全技术取得进步之后,网络犯罪仍在不断增加。据统计,网络犯罪每分钟给企业造成约 290 万美元的损失。主要是因为新技术不断涌现,难以维护安全。随着网络威胁的增加,网络...【详细内容】
2021-11-04  章大千    Tags:编程语言   点击:(40)  评论:(0)  加入收藏
北漂小伙李强(化名),在北京互联网大厂工作7年,月薪3万,离职回老家开摄影店,亏了200万。李强出生于山西一座名不经传的小城市,互联网专业大学毕业的他,没有听父母的劝言回到家乡考公...【详细内容】
2021-10-29  霸王课  今日头条  Tags:程序员   点击:(53)  评论:(0)  加入收藏
程序员是青春饭,这在国内似乎是公认的。所以很多公司不愿招大龄程序员,很多程序员也“知趣”地及早转型。有的做管理,有的做架构,我还见过改行卖保险的。总之,年龄大了不想敲代码...【详细内容】
2021-10-27  编程的艺术    Tags:   点击:(30)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条