【 python 学习笔记 -- 数据结构与算法 】冒泡排序 Bubble sort

栏目: Python · 发布时间: 6年前

内容简介:【 python 学习笔记 -- 数据结构与算法 】冒泡排序 Bubble sort

推荐一个可视化的网站 【 Visual Algo 】: URL= 'https://visualgo.net/en/sorting'

这个网站给出了各种 排序 算法的原理和过程,通过动态形式直观得展现出来。另外还给出了相关的pseudo-code,以及具体执行到code的哪一步。

【冒泡排序】

需要重复地走访需要排序的数列。走访过程中比较相邻两个items的大小,如果顺序不对,则交换两个items。 因此,每完成一次走访(pass),需要排序的部分的最大值就会移动到合适的位置。

这个过程看起来就像每一个item冒泡到最终的位置一样,因而成为冒泡排序。

这里给出完成一次走访的过程,最终这个列表的最大值93移动到了列表最右端。

【 python 学习笔记 -- 数据结构与算法 】冒泡排序 Bubble sort

【 implementation of a bubble sort 】

【 python 学习笔记 -- 数据结构与算法 】冒泡排序 Bubble sort

可以通过print n 和 k 查看具体执行过程。

【performance analysis】

上述的实现中,不论输入的是什么样的列表,时间复杂度都是O(n 2 ),因为需要比较的次数为(n-1)+(n-2)+...+1; 空间复杂度是O(1)。

但是通过记录不需要交换的位置,可以把best-case performance降到O(n),方法如下:

【 python 学习笔记 -- 数据结构与算法 】冒泡排序 Bubble sort

当然我们可以用 python 的内建函数 【 sort() 】来实现排序,例如:

【 python 学习笔记 -- 数据结构与算法 】冒泡排序 Bubble sort


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

八年级数学(华东师大版)-解题升级-解题快速反应一本通(新课标)

八年级数学(华东师大版)-解题升级-解题快速反应一本通(新课标)

孙丽敏等编 / 吉林教育出版社 / 2004-6 / 10.0

本书将与知识点、重点、难点和考点有关的典型题做全析全解,是具有解题题典性质的助学读物。但本书又优于解题题典,不仅展示解题过程,更详细地提供了解题思考过程和切入点的选择方法,教方法导引思路的功能更强。 学生要提高解题能力,必须具备两个条件:一是打好基础,二是能够运动所学知识分析问题和解决问题。本书用例题解析解说知识点、重点、难点和考点,同时提供解题思考过程,在打基础中激活能力,在解题实......一起来看看 《八年级数学(华东师大版)-解题升级-解题快速反应一本通(新课标)》 这本书的介绍吧!

MD5 加密
MD5 加密

MD5 加密工具

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具