python|冒泡排序及优化（python冒泡法排序代码）
off999 2024-10-27 11:51 15 浏览 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计算每天进步一点点）
-
离别了学生时代，步入了职场，你还记得你离上一次打开书本是在什么时候吗？认真上课，看学习视频，静下心来，虽唾手可得，却似乎离我们越来越远。每天忙着忙着，不知道自己忙什么，只是连坐下来停下思考5分钟的时间...
- Python高级特性揭秘:14个鲜为人知的编程秘籍
-
引言：Python的隐藏宝藏Python作为全球最受欢迎的编程语言之一，以其简洁和易用性著称。然而，许多开发者在日常工作中只触及了Python的表面，错过了许多强大而高效的高级特性。这些特性不仅能让代...
- Python自动化脚本指南（pythonui自动化脚本）
-
以下是一个实用的Python自动化脚本指南，包含常见场景示例和分步说明：一、环境准备安装Python(推荐3.6+版本)安装常用库：bashpipinstallrequestsbea...
- python面向对象四大支柱——多态（python面向对象总结）
-
Python面向对象多态(Polymorphism)详解多态是面向对象编程的四大支柱之一，它允许不同类的对象对同一消息（方法调用）做出不同的响应。下面我将全面详细地讲解Python中的多态概念及其实现...
- 主编推荐 | Gurobi 并行计算的设置和操作(附代码)
-
『运筹OR帷幄』原创作者：运筹OR帷幄编者按实际应用问题往往具有较高的计算复杂度，而优化算法难以在实际中落地的主要瓶颈就在于无法满足实际问题对计算时间的苛刻要求。然而近年来随着计算力的蓬勃发展，并行计...
- Python 空值(None)详解（python 给空值赋值）
-
在Python中，空值是一个非常重要的概念，表示"没有值"或"空"的状态。让我们来详细了解一下。什么是空值？在Python中，空值用None表示。它是一个特殊的数据类型...
- python学习——032关于函数接收的参数和返回值
-
在Python里，函数的参数和返回值都能是字符（字符串）、列表、字典等多种类型的数据，这大大提升了函数的灵活性和复用性。下面为举例说明：1.参数和返回值为字符串defgreet(name):...
- 一文理解 Python 中的类型提示（python 类的作用）
-
Python的流行源于其简洁性和可读性。然而，作为一种动态类型语言，其灵活性有时会导致运行时错误和由于数据类型不正确而出现意外行为。这是类型提示和静态类型检查发挥作用的地方，为Python代码...
- 新手学Python避坑，学习效率狂飙! 二十三、Python 闭包问题
-
感谢大家对《新手学Python避坑，学习效率狂飙！》系列的点赞、关注和收藏，今天这编是这个系列的第二十三个分享，前面还有二十二个，大家可以关注下之前发布的文章。下面是我们今天的分享：闭包的定义与原理在...
- 一个用 Rust 开发的极快、易用的 Python 包和项目管理利器
-
uv是一个全新的、由Astral团队（就是那个开发了Ruff的团队）采用Rust开发的高性能的Python包和项目管理工具。它的目标是取代传统的pip和pip-tools，提供...
- 脱颖而出的Python xlwings模块，一个更强大的操作Excel的模块
-
如下，在Python中存在很多支持Excel操作的第三方库，那么本文介绍的xlwings模块有其它模块有何区别呢？xrldxlwtopenpyxlxlswriterpandaswin32comxl...
- 一小时学会用Python开发微信AI机器人:从零到企业级应用实战
-
一、企业微信API接入流程：打造合法合规的机器人通道1.1企业微信与个人微信的区别企业微信三大优势：1.官方API支持（合规性保障）2.支持多终端消息同步3.可扩展企业级功能（审批/打卡...
- Python 进阶-day24: API 开发（python的api）
-
学习目标理解RESTfulAPI的核心概念和设计原则。使用Flask创建模块化的RESTfulAPI，包含优雅的数据库访问代码。为博客应用实现API接口，支持CRUD操作（创建、...
- PyQt5 库:强大的 Python GUI 开发利器
-
一、引言在Python的众多应用领域中，图形用户界面（GUI）开发是一个重要的方面。PyQt5库作为一个功能强大且广泛应用的GUI框架，为开发者提供了丰富的工具和组件，使得创建交互式、美观的...
- 探秘:Python 类为何继承 object（python中的类都继承于object）
-
在Python的编程世界里，我们常常会看到这样的代码：classMyClass(object):，这里的类继承了object。那么，Python类为什么要继承object呢？今天咱们...
欢迎 你 发表评论:
- 一周热门
- 最近发表
-
- Python写每天进步1%的力量（python计算每天进步一点点）
- Python高级特性揭秘:14个鲜为人知的编程秘籍
- Python自动化脚本指南（pythonui自动化脚本）
- python面向对象四大支柱——多态（python面向对象总结）
- 主编推荐 | Gurobi 并行计算的设置和操作(附代码)
- Python 空值(None)详解（python 给空值赋值）
- python学习——032关于函数接收的参数和返回值
- 一文理解 Python 中的类型提示（python 类的作用）
- 新手学Python避坑，学习效率狂飙! 二十三、Python 闭包问题
- 一个用 Rust 开发的极快、易用的 Python 包和项目管理利器
- 标签列表
-
- python计时 (54)
- python安装路径 (54)
- python类型转换 (75)
- python进度条 (54)
- python的for循环 (56)
- python串口编程 (60)
- python写入txt (51)
- python读取文件夹下所有文件 (59)
- java调用python脚本 (56)
- python操作mysql数据库 (66)
- python字典增加键值对 (53)
- python获取列表的长度 (64)
- python接口 (63)
- python调用函数 (57)
- python qt (52)
- python人脸识别 (54)
- python斐波那契数列 (51)
- python多态 (60)
- python命令行参数 (53)
- python匿名函数 (59)
- python打印九九乘法表 (65)
- centos7安装python (53)
- python赋值 (62)
- python异常 (69)
- python元祖 (57)