Python冒泡排序算法详解
想要掌握Python排序算法的基础吗?本文将带你深入理解**Python冒泡排序**的实现方法。冒泡排序作为最基础的排序算法之一,其核心思想在于通过不断遍历列表,比较相邻元素并交换位置,使较大的元素像气泡一样逐步“浮”到列表末尾。文章详细讲解了冒泡排序的基础实现,并通过Python代码示例展示了如何通过外层循环控制遍历趟数,内层循环实现相邻元素的比较与交换。此外,本文还深入探讨了冒泡排序的优化策略,例如引入标志位以提前终止循环,以及记录最后一次交换位置来缩小后续比较范围,提升排序效率。尽管冒泡排序的时间复杂度为O(n²),更适合教学或小规模数据排序,但通过本文的学习,你将能够透彻理解冒泡排序的原理和优化技巧,为学习更高级的排序算法打下坚实基础。
冒泡排序的核心思路是通过重复遍历列表,比较相邻元素并交换位置以达到有序,其名称源于大元素像气泡一样逐渐移动到末尾。1. 它通过外层循环控制遍历趟数,内层循环进行相邻元素的比较与交换;2. 每一趟遍历会将当前未排序部分的最大元素“冒泡”到正确位置;3. 可通过引入标志位优化,在列表已有序时提前终止循环;4. 进一步优化可记录最后一次交换位置,缩小后续比较范围;5. 时间复杂度为O(n²),适用于教学或小规模数据,不适用于大型或性能敏感的数据集。

在Python中实现冒泡排序,核心思路就是通过重复遍历列表,比较相邻元素并按需交换它们的位置,直到整个列表有序。这听起来有点笨拙,但它确实是理解排序算法基础逻辑的绝佳起点。本质上,我们就是在列表里“推”着那些“大”的元素慢慢浮到它们该去的位置,像水里的气泡一样。

解决方案
实现冒泡排序,我们需要一个外层循环来控制总的遍历趟数,以及一个内层循环来完成每趟的比较和交换。
最基础的冒泡排序实现大致是这样:

def bubble_sort_basic(arr):
n = len(arr)
# 外层循环控制趟数,每一趟会将一个最大的元素“冒泡”到末尾
for i in range(n - 1):
# 内层循环进行比较和交换
# 每次内层循环结束后,最大的未排序元素会到达正确位置
# 因此,后面的元素就不需要再比较了,所以是 n - 1 - i
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
# 交换元素
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
# 示例
my_list = [64, 34, 25, 12, 22, 11, 90]
print(f"原始列表: {my_list}")
sorted_list = bubble_sort_basic(my_list.copy()) # 使用copy避免修改原列表
print(f"排序后列表 (基础版): {sorted_list}")上面这个版本虽然能工作,但有个小问题:如果列表在某个时候已经完全有序了,它还是会傻傻地把所有循环都走完。为了避免这种不必要的计算,我们可以加一个优化:引入一个标志位,如果在某次内循环中没有发生任何交换,那就说明列表已经有序了,可以直接提前结束。
优化后的冒泡排序:

def bubble_sort_optimized(arr):
n = len(arr)
# 标志位,用于判断在一趟遍历中是否发生了交换
swapped = False
for i in range(n - 1):
swapped = False # 每趟开始前重置标志位
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True # 发生了交换
# 如果这一趟没有发生任何交换,说明列表已经有序,可以提前结束
if not swapped:
break
return arr
# 示例
my_list_opt = [64, 34, 25, 12, 22, 11, 90]
print(f"原始列表: {my_list_opt}")
sorted_list_opt = bubble_sort_optimized(my_list_opt.copy())
print(f"排序后列表 (优化版): {sorted_list_opt}")
# 提前结束的例子
already_sorted_list = [1, 2, 3, 4, 5]
print(f"原始列表 (已排序): {already_sorted_list}")
sorted_already_sorted = bubble_sort_optimized(already_sorted_list.copy())
print(f"排序后列表 (优化版,已排序): {sorted_already_sorted}")这个优化版在处理部分有序或完全有序的列表时,效率会高很多。
冒泡排序的工作原理是什么?它为什么叫“冒泡”?
冒泡排序的工作原理其实非常直观。它通过重复地走访过要排序的数列,一次比较两个相邻的元素,如果它们的顺序不对(比如从小到大排序时,前一个比后一个大),就把它们交换过来。这个过程会持续进行,直到没有再需要交换的元素,也就是说,整个数列都排好序了。
想象一下水底的气泡,它们会一点点向上浮。在冒泡排序中,每次遍历,最大的(或最小的,取决于排序方向)未排序元素就像一个“气泡”,通过一系列相邻元素的交换,逐渐“浮”到列表的末尾(或开头)它应该在的位置。每次内层循环结束,都能保证当前未排序部分的最大元素已经“冒泡”到了正确的位置。因为这种“大”元素逐渐“浮”到末端的形象,所以它被形象地称为“冒泡排序”。
冒泡排序的性能如何?在什么场景下它不适用?
谈到性能,冒泡排序通常不是首选,因为它在大多数情况下的效率并不高。它的时间复杂度在最坏和平均情况下都是O(n²),这意味着当列表的元素数量n增加时,排序所需的时间会以n的平方级别增长。举个例子,如果列表长度从100增加到1000,排序时间可能增加100倍。空间复杂度方面,它只需要常数级别的额外空间,即O(1),因为它是在原地进行排序,不需要创建新的数组。
尽管有前面提到的优化,将最好情况下的时间复杂度降低到O(n)(当列表已经有序时),但对于随机或逆序的、规模较大的数据集,它的表现依然不尽人意。
因此,冒泡排序在以下场景下通常不适用:
- 大型数据集: 当你需要处理成千上万甚至更多的数据时,O(n²)的复杂度会让你等到天荒地老。
- 对性能有严格要求的系统: 在需要快速响应或处理大量数据的应用中,冒泡排序会成为瓶颈。
- 实时系统: 它的不确定性(在最坏情况下性能急剧下降)使其不适合需要稳定、可预测性能的实时应用。
那么,它在什么场景下可能还有点用呢?或许是教育目的,因为它简单易懂,是理解排序算法基础概念的好例子;或者在处理非常小的、几乎有序的列表时,它的代码量小,实现简单,可能比引入更复杂的算法更方便。但即便如此,Python内置的sort()方法或sorted()函数通常是更好的选择,它们底层使用了Timsort,效率要高得多。
除了基础实现,冒泡排序还有哪些优化思路?
除了我们前面提到的那个通过swapped标志位来提前终止排序的优化,冒泡排序其实还有一些其他思路,虽然它们并不能改变其O(n²)的本质复杂度,但在特定情况下能带来一些边际效益。
一个常见的思路是,我们知道在每一趟内层循环结束后,最大的元素已经“冒泡”到了它最终的位置。因此,下一趟循环时,我们不需要再比较已经排好序的末尾元素了。这就是为什么我们的代码中内层循环的范围是range(n - 1 - i),这里的i就代表了已经有多少个元素“归位”了。这本身就是一种优化,它缩小了每趟比较的范围。
另一个稍微复杂一点的优化是记录最后一次交换发生的位置。因为在最后一次交换之后的所有元素,都是已经排好序的。所以,下一趟循环的比较范围可以进一步缩小到这个位置之前。
def bubble_sort_optimized_further(arr):
n = len(arr)
# last_swap_index 记录上一趟最后一次交换的位置
# 在这个位置之后的元素都已排序
last_swap_index = n - 1
while last_swap_index > 0:
current_swap_index = 0 # 记录当前趟最后一次交换的位置
for j in range(last_swap_index):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
current_swap_index = j # 更新最后交换位置
last_swap_index = current_swap_index # 更新下一趟的比较范围
# 如果 current_swap_index 还是 0,说明没有发生交换,列表已排序
if current_swap_index == 0:
break
return arr
# 示例
my_list_further_opt = [64, 34, 25, 12, 22, 11, 90]
print(f"原始列表: {my_list_further_opt}")
sorted_list_further_opt = bubble_sort_optimized_further(my_list_further_opt.copy())
print(f"排序后列表 (进一步优化版): {sorted_list_further_opt}")这个版本在某些特定数据分布下,可能会减少一些不必要的比较,但它的核心逻辑依然是冒泡排序,复杂度等级并没有改变。还有一些变体,比如双向冒泡排序(也叫鸡尾酒排序),它会在每一趟中从两端向中间进行冒泡,理论上可以减少一些循环次数,但本质上还是O(n²)。这些优化更多是算法实现上的精进,而非颠覆性的性能提升。
今天关于《Python冒泡排序算法详解》的内容就介绍到这里了,是不是学起来一目了然!想要了解更多关于时间复杂度,Python冒泡排序,冒泡排序优化,相邻元素交换的内容请关注golang学习网公众号!
Linux多网口绑定与故障切换教程
- 上一篇
- Linux多网口绑定与故障切换教程
- 下一篇
- JavaScript闭包应用技巧解析
-
- 文章 · python教程 | 15小时前 | python · Python 十六进制 二进制调试 memoryview.hex bytes_per_sep
- Python memoryview.hex 怎样为十六进制输出设置分组分隔符
- 480浏览 收藏
-
- 文章 · python教程 | 16小时前 | python · Python decimal context same_quantum
- Python decimal.Context.same_quantum 怎样判断两个十进制数的指数是否相同
- 336浏览 收藏
-
- 文章 · python教程 | 17小时前 |
- Python textwrap.TextWrapper.drop_whitespace 怎样控制换行边缘的空白保留
- 238浏览 收藏
-
- 文章 · python教程 | 17小时前 | 标准库 · python · Python 参数绑定 Signature BoundArguments inspect.Signature.bind_partial
- Python inspect.Signature.bind_partial 怎样允许缺省必填参数进行部分绑定
- 492浏览 收藏
-
- 文章 · python教程 | 19小时前 | python · 文件系统 · Python 文件比较 mtime filecmp.clear_cache filecmp.cmp 比较缓存
- Python filecmp.clear_cache 怎样清除文件比较结果缓存
- 290浏览 收藏
-
- 文章 · python教程 | 20小时前 | 标准库 · 递归 · python · Python 解释器 递归限制 sys.getrecursionlimit
- Python sys.getrecursionlimit 怎样读取解释器设置的递归深度上限
- 129浏览 收藏
-
- 文章 · python教程 | 21小时前 | Python教程 · Python memoryview memoryview.toreadonly bytearray 只读视图 缓冲区协议
- Python memoryview.toreadonly 怎样生成只读视图而不复制底层数据
- 470浏览 收藏
-
- 文章 · python教程 | 22小时前 | 标准库 · Python教程 · Python decimal flags 精度 舍入 Context.copy_abs Decimal.copy_abs
- Python decimal.Context.copy_abs 怎样取绝对值而不受当前精度舍入影响
- 389浏览 收藏
-
- 文章 · python教程 | 23小时前 | 字符串 · 标准库 · Python教程 · Python placeholder 文本截断 textwrap TextWrapper max_lines
- Python textwrap.TextWrapper.placeholder 怎样为截断后的段落设置结束标记
- 301浏览 收藏
-
- 文章 · python教程 | 23小时前 | python · Python 参数绑定 inspect BoundArguments apply_defaults
- Python inspect.BoundArguments.apply_defaults 怎样给已绑定参数补上默认值
- 411浏览 收藏
-
- 前端进阶之JavaScript设计模式
- 设计模式是开发人员在软件开发过程中面临一般问题时的解决方案,代表了最佳的实践。本课程的主打内容包括JS常见设计模式以及具体应用场景,打造一站式知识长龙服务,适合有JS基础的同学学习。
- 543次学习
-
- GO语言核心编程课程
- 本课程采用真实案例,全面具体可落地,从理论到实践,一步一步将GO核心编程技术、编程思想、底层实现融会贯通,使学习者贴近时代脉搏,做IT互联网时代的弄潮儿。
- 516次学习
-
- 简单聊聊mysql8与网络通信
- 如有问题加微信:Le-studyg;在课程中,我们将首先介绍MySQL8的新特性,包括性能优化、安全增强、新数据类型等,帮助学生快速熟悉MySQL8的最新功能。接着,我们将深入解析MySQL的网络通信机制,包括协议、连接管理、数据传输等,让
- 500次学习
-
- JavaScript正则表达式基础与实战
- 在任何一门编程语言中,正则表达式,都是一项重要的知识,它提供了高效的字符串匹配与捕获机制,可以极大的简化程序设计。
- 487次学习
-
- 从零制作响应式网站—Grid布局
- 本系列教程将展示从零制作一个假想的网络科技公司官网,分为导航,轮播,关于我们,成功案例,服务流程,团队介绍,数据部分,公司动态,底部信息等内容区块。网站整体采用CSSGrid布局,支持响应式,有流畅过渡和展现动画。
- 485次学习
-
- PubMedQA
- 深入了解PubMedQA生物医学问答数据集,涵盖其核心功能、使用方法及在临床决策、药物研发等场景的应用,助力提升NLP模型性能。
- 1114次使用
-
- H2O EvalGPT
- H2O EvalGPT是H2O.ai推出的开源LLM评估平台,提供详细的大模型性能排行榜、行业特定基准测试及A/B测试功能,助您快速选择最适合项目的高性能大语言模型。
- 1104次使用
-
- LMArena
- LMArena是加州大学伯克利分校推出的AI模型匿名评测平台。通过盲测投票机制,用户可对比不同大模型回答并生成实时排行榜,助力开发者优化模型及用户选择最佳AI工具。
- 1274次使用
-
- HELM
- 深入了解斯坦福推出的HELM(Holistic Evaluation of Language Models)大模型评测体系。本文解析其核心功能、安装配置步骤及应用场景,涵盖准确性、公平性、鲁棒性等多维度指标,助力开发者全面优化语言模型性能。
- 1217次使用
-
- MMBench
- MMBench是由上海人工智能实验室等机构联合推出的多模态基准测试平台,提供细粒度能力评估、大规模数据集及VLMEvalKit工具。本文详细介绍其核心功能、安装使用方法及应用场景,助力开发者全面评估多模态模型性能。
- 1064次使用
-
- Python TaskGroup 怎样让子任务失败统一收敛
- 2026-11-12 501浏览
-
- Python xml.dom.minidom.unlink 怎样释放不再使用的 DOM 树引用
- 2026-10-27 501浏览
-
- Python typing 怎样用 TypeIs 缩小类型
- 2026-10-24 501浏览
-
- Python sqlite3 Connection serialize 怎么导出数据库快照:备份窗口、内存占用与恢复校验
- 2026-08-26 501浏览
-
- Python监控网页状态:requests异常处理实战
- 2026-05-29 501浏览

