python|冒泡排序及优化（python冒泡法排序代码）
off999 2024-10-27 11:51 21 浏览 0 评论
一、冒泡排序简介
冒泡排序(Bubble Sort)是一种常见的排序算法，相对来说比较简单。
冒泡排序重复地走访需要排序的元素列表，依次比较两个相邻的元素，如果顺序(如从大到小或从小到大)错误就交换它们的位置。重复地进行直到没有相邻的元素需要交换，则元素列表排序完成。
在冒泡排序中，值最大(或最小)的元素会通过交换慢慢“浮”到元素列表的“顶端”。就像“冒泡”一样，所以被称为冒泡排序。
二、冒泡排序原理
冒泡排序的原理如下：
1. 比较相邻的两个元素。如果第一个比第二个大则交换他们的位置(升序排列，降序则反过来)。
2. 从列表的开始一直到结尾，依次对每一对相邻元素都进行比较。这样，值最大的元素就通过交换“冒泡”到了列表的结尾，完成第一轮“冒泡”。
3. 重复上一步，继续从列表开头依次对相邻元素进行比较。已经“冒泡”出来的元素不用比较(一直比较到结尾也可以，已经“冒泡”到后面的元素即使比较也不需要交换，不比较可以减少步骤)。
4. 继续从列表开始进行比较，每轮比较会有一个元素“冒泡”成功。每轮需要比较的元素个数会递减，一直到只剩一个元素没有“冒泡”时(没有任何一对元素需要比较)，则列表排序完成。
以列表 [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21] 进行升序排列为例。列表的初始状态如下图。
要进行升序排列，则大的元素要依次“冒泡”到列表的结尾。
1. 从列表的开头，比较相邻的两个元素，如果第一个值比第二个值大则交换。10小于17，不需要交换。
2. 向列表的结尾方向“走访”，比较第二组相邻的元素(第二个和第三个)，如果不是从小到大则交换。17小于50，不需要交换。
3. 继续“走访”，比较第三组相邻的元素，如果不是从小到大则交换。50大于7，所以需要交换。
4. 对顺序错误的元素进行位置交换。交换50和7的位置。
5. 一直“走访”到结尾，第一轮“冒泡”结束后，值最大的元素“冒泡”到了列表的结尾。50“冒泡”到了列表结尾。
在下一轮“冒泡”中，不需要再将50进行比较，需要比较的元素个数减1。
6. 从列表开头，重复下一轮“冒泡”，每进行一轮“冒泡”，需要比较的元素都少一个，直到没有元素对需要比较时，整个列表排序完成。排序结果如下图。
三、Python实现冒泡排序
四、冒泡排序的时间复杂度和稳定性
1. 时间复杂度
在没有特殊说明时，一般都是计算最坏时间复杂度。
在冒泡排序中，最坏的情况是元素列表的初始状态是完全逆序排列的，需要进行 n-1 轮“冒泡”，每一轮“冒泡”需要进行 n-i 次比较和交换操作。i 的平均值为 n/2 ，时间复杂度为 T(n)=n(n-1)/2 ，再乘每次操作的步骤数(常数，不影响大O记法)，所以冒泡排序的时间复杂度为 O(n^2) 。
2. 稳定性
排序算法的稳定性指，当元素列表中有相等的元素时，相等元素的相对次序是否固定不变，如果相对次序固定不变，则排序算法是稳定的，反之。
在冒泡排序中，每次比较两个元素，当元素的大小顺序错误时才会进行交换，如果元素列表中有两个相等的元素，它们最终肯定会相邻在一起，但对它们比较时不会进行交换，相对次序是保持不变的。所以冒泡排序是一种稳定的排序算法。
冒泡排序优化：将时间复杂度降为O(n)
相关推荐
- Python四种常用的高阶函数，你会用了吗
-
每天进步一点点，关注我们哦，每天分享测试技术文章本文章出自【码同学软件测试】码同学公众号：自动化软件测试码同学抖音号：小码哥聊软件测试1、什么是高阶函数把函数作为参数传入，这样的函数称为高阶函数例如：...
- Python之函数进阶-函数加强(上)（python函数的作用增强代码的可读性）
-
一.递归函数递归是一种编程技术，其中函数调用自身以解决问题。递归函数需要有一个或多个终止条件，以防止无限递归。递归可以用于解决许多问题，例如排序、搜索、解析语法等。递归的优点是代码简洁、易于理解，并...
- 数据分析-一元线性回归分析Python
-
前面几篇介绍了数据的相关性分析，通过相关性分析可以看出变量之间的相关性程度。如果我们已经发现变量之间存在明显的相关性了，接下来就可以通过回归分析，计算出具体的相关值，然后可以用于对其他数据的预测。本篇...
- python基础函数（python函数总结）
-
Python函数是代码复用的核心工具，掌握基础函数的使用是编程的关键。以下是Python函数的系统总结，包含内置函数和自定义函数的详细用法，以及实际应用场景。一、Python内置函数（...
- python进阶100集(9)int数据类型深入分析
-
一、基本概念int数据类型基本上来说这里指的都是整形，下一届我们会讲解整形和浮点型的转化，以及精度问题！a=100b=a这里a是变量名，100就是int数据对象，b指向的是a指向的对象，...
- Python学不会来打我(73)python常用的高阶函数汇总
-
python最常用的高阶函数有counter()，sorted()，map()，reduce()，filter()。很多高阶函数都是将一个基础函数作为第一个参数，将另外一个容器集合作为第二个参数，然...
- python中有哪些内置函数可用于编写数值表达式?
-
在Python中，用于编写数值表达式的内置函数很多，它们可以帮助你处理数学运算、类型转换、数值判断等。以下是常用的内置函数（不需要导入模块）按类别归类说明：一、基础数值处理函数函数作用示例ab...
- 如何在Python中获取数字的绝对值?
-
Python有两种获取数字绝对值的方法：内置abs()函数返回绝对值。math.fabs()函数还返回浮点绝对值。abs()函数获取绝对值内置abs()函数返回绝对值，要使用该函数，只需直接调用：a...
- 【Python大语言模型系列】使用dify云版本开发一个智能客服机器人
-
这是我的第359篇原创文章。一、引言上篇文章我们介绍了如何使用dify云版本开发一个简单的工作流：【Python大语言模型系列】一文教你使用dify云版本开发一个AI工作流（完整教程）这篇文章我们将引...
- Python3.11版本使用thriftpy2的问题
-
Python3.11于2022年10月24日发布，但目前thriftpy2在Python3.11版本下无法安装，如果有使用thriftpy2的童鞋，建议晚点再升级到最新版本。...
- uwsgi的python2+3多版本共存（python多版本兼容）
-
一、第一种方式（virtualenv）1、首先，机器需要有python2和python3的可执行环境。确保pip和pip3命令可用。原理就是在哪个环境下安装uwsgi。uwsgi启动的时候，就用的哪个...
- 解释一下Python脚本中版本号声明的作用
-
在Python脚本中声明版本号（如__version__变量）是一种常见的元数据管理实践，在IronPython的兼容性验证机制中具有重要作用。以下是版本号声明的核心作用及实现原理：一、版本号...
- 除了版本号声明，还有哪些元数据可以用于Python脚本的兼容性管理
-
在Python脚本的兼容性管理中，除了版本号声明外，还有多种元数据可以用于增强脚本与宿主环境的交互和验证。以下是一些关键的元数据类型及其应用场景：一、环境依赖声明1.Python版本要求pyth...
- 今年回家没票了?不，我有高科技抢票
-
零基础使用抢票开源软件Py12306一年一度的抢票季就要到了，今天给大家科普一下一款软件的使用方法。软件目前是开源的，禁止用于商用。首先需要在电脑上安装python3.7，首先从官网下载对应的安装包，...
- 生猛!春运抢票神器成GitHub热榜第一，过年回家全靠它了
-
作者：车栗子发自：凹非寺量子位报道春节抢票正在如火如荼的进行，过年回家那肯定需要抢票，每年的抢票大战，都是一场硬战，没有一个好工具，怎么能上战场死锁呢。今天小编推荐一个Python抢票工具，送到...
欢迎 你 发表评论:
- 一周热门
- 最近发表
- 标签列表
-
- python计时 (73)
- python安装路径 (56)
- python类型转换 (93)
- python进度条 (67)
- python吧 (67)
- python字典遍历 (54)
- python的for循环 (65)
- python格式化字符串 (61)
- python静态方法 (57)
- python列表切片 (59)
- python面向对象编程 (60)
- python 代码加密 (65)
- python串口编程 (60)
- python读取文件夹下所有文件 (59)
- java调用python脚本 (56)
- python操作mysql数据库 (66)
- python获取列表的长度 (64)
- python接口 (63)
- python调用函数 (57)
- python多态 (60)
- python匿名函数 (59)
- python打印九九乘法表 (65)
- python赋值 (62)
- python异常 (69)
- python元祖 (57)