python|冒泡排序及优化（python冒泡法排序代码）
off999 2024-10-27 11:51 25 浏览 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)
相关推荐
- pip的使用及配置_pip怎么配置
-
要使用python必须要学会使用pip，pip的全称：packageinstallerforpython，也就是Python包管理工具，主要是对python的第三方库进行安装、更新、卸载等操作，...
- Anaconda下安装pytorch_anaconda下安装tensorflow
-
之前的文章介绍了tensorflow-gpu的安装方法，也介绍了许多基本的工具与使用方法，具体可以看Ubuntu快速安装tensorflow2.4的gpu版本。pytorch也是一个十分流行的机器学...
- Centos 7 64位安装 python3的教程
-
wgethttps://www.python.org/ftp/python/3.10.13/Python-3.10.13.tgz#下载指定版本软件安装包tar-xzfPython-3.10.1...
- 如何安装 pip 管理工具_pip安装详细步骤
-
如何安装pip管理工具方法一:yum方式安装Centos安装python3和python3-devel开发包>#yuminstallgcclibffi-develpy...
- Python入门——从开发环境搭建到hello world
-
一、Python解释器安装1、在windows下步骤1、下载安装包https://www.python.org/downloads/打开后选择【Downloads】->【Windows】小编是一...
- 生产环境中使用的十大 Python 设计模式
-
在软件开发的浩瀚世界中，设计模式如同指引方向的灯塔，为我们构建稳定、高效且易于维护的系统提供了经过验证的解决方案。对于Python开发者而言，理解和掌握这些模式，更是提升代码质量、加速开发进程的关...
- 如何创建和管理Python虚拟环境_python怎么创建虚拟环境
-
在Python开发中，虚拟环境是隔离项目依赖的关键工具。下面介绍创建和管理Python虚拟环境的主流方法。一、内置工具：venv（Python3.3+推荐）venv是Python标准...
- 初学者入门Python的第一步——环境搭建
-
Python如今成为零基础编程爱好者的首选学习语言，这和Python语言自身的强大功能和简单易学是分不开的。今天千锋武汉Python培训小编将带领Python零基础的初学者完成入门的第一步——环境搭建...
- 全网最简我的世界Minecraft搭建Python编程环境
-
这篇文章将给大家介绍一种在我的世界minecraft里搭建Python编程开发环境的操作方法。目前看起来应该是全网最简单的方法。搭建完成后，马上就可以利用python代码在我的世界自动创建很多有意思的...
- Python开发中的虚拟环境管理_python3虚拟环境
-
Python开发中，虚拟环境管理帮助隔离项目依赖，避免不同项目之间的依赖冲突。虚拟环境的作用隔离依赖：不同项目可能需要不同版本的库，虚拟环境可以为每个项目创建独立的环境。避免全局污染：全局安装的库可...
- Python内置zipfile模块:操作 ZIP 归档文件详解
-
一、知识导图二、知识讲解（一）zipfile模块概述zipfile模块是Python内置的用于操作ZIP归档文件的模块。它提供了创建、读取、写入、添加及列出ZIP文件的功能。（二）ZipFile类1....
- Python内置模块pydoc :文档生成器和在线帮助系统详解
-
一、引言在Python开发中，良好的文档是提高代码可读性和可维护性的关键。pydoc是Python自带的一个强大的文档生成器和在线帮助系统，它可以根据Python模块自动生成文档，并支持多种输出格式...
- Python sys模块使用教程_python system模块
-
1.知识导图2.sys模块概述2.1模块定义与作用sys模块是Python标准库中的一个内置模块，提供了与Python解释器及其环境交互的接口。它包含了许多与系统相关的变量和函数，可以用来控制P...
- Python Logging 模块完全解读_python logging详解
-
私信我，回复：学习，获取免费学习资源包。Python中的logging模块可以让你跟踪代码运行时的事件，当程序崩溃时可以查看日志并且发现是什么引发了错误。Log信息有内置的层级——调试（deb...
- 软件测试|Python logging模块怎么使用，你会了吗?
-
Pythonlogging模块使用在开发和维护Python应用程序时，日志记录是一项非常重要的任务。Python提供了内置的logging模块，它可以帮助我们方便地记录应用程序的运行时信息、错误和调...
欢迎 你 发表评论:
- 一周热门
- 最近发表
- 标签列表
-
- python计时 (73)
- python安装路径 (56)
- python类型转换 (93)
- python进度条 (67)
- python吧 (67)
- python的for循环 (65)
- python格式化字符串 (61)
- python静态方法 (57)
- python列表切片 (59)
- python面向对象编程 (60)
- python 代码加密 (65)
- python串口编程 (77)
- python封装 (57)
- python写入txt (66)
- python读取文件夹下所有文件 (59)
- python操作mysql数据库 (66)
- python获取列表的长度 (64)
- python接口 (63)
- python调用函数 (57)
- python多态 (60)
- python匿名函数 (59)
- python打印九九乘法表 (65)
- python赋值 (62)
- python异常 (69)
- python元祖 (57)