Python冒泡排序入门：从零实现列表升序排列与优化技巧

之前在给初学者讲 Python 列表操作时几乎每次都会遇到同一个问题给了一组杂乱的数据怎么用代码把它按从大到小或从小到大排好很多人第一反应是直接调用sorted()或list.sort()这个答案没错但如果你还没弄明白排序背后到底发生了什么一旦面试官追问“不用内置函数怎么实现”就会卡壳。冒泡排序作为最经典的入门排序算法正好能帮你补齐这块短板。本文会从零开始拆解冒泡排序的实现思路再用 Python 逐步写出对列表进行升序排列的完整代码并针对常见报错、优化方案和工程习惯给出建议。内容适合刚学 Python 的初学者也适合想复习算法基础、准备面试的开发同学。1. 冒泡排序到底是什么1.1 一个生活化的例子想象一下你面前有一排高低不同的人老师要求按身高从矮到高站好。最笨但有效的办法是从队伍最左边开始依次比较相邻两个人的身高如果左边的人比右边的人高就让他们交换位置。这样走完一趟后最高的人就像气泡一样“浮”到了队伍最右边。接着再从头开始重复同样的过程只不过这次不需要再管最右边那个已经排好的人。等到再也没有相邻位置需要交换时整支队伍就排好了。这个“相邻比较、不符合顺序就交换”的过程就是冒泡排序的核心逻辑。因为大的元素会像水里的气泡一样逐步向上浮动所以叫“冒泡排序”。1.2 冒泡排序的专业定义冒泡排序Bubble Sort是一种基于比较和交换的稳定排序算法。它重复地遍历待排序的列表一次比较两个相邻元素如果它们的顺序错误就交换过来。遍历列表的工作会重复多轮直到没有任何一对相邻元素需要交换为止。用更严谨的话描述输入一个包含n个元素的列表。操作进行多轮相邻元素比较按升序要求将较大的元素向右移动。输出完成升序排列的新列表或原列表。时间复杂度最坏和平均情况为 O(n²)最好情况列表已经有序优化后可达到 O(n)。空间复杂度O(1)因为只需要一个临时变量用于交换是原地排序算法。1.3 为什么初学者要掌握冒泡排序很多同学会觉得明明有现成的sort()方法为什么还要学冒泡排序主要有三点原因理解排序的底层逻辑。直接调用 API 很容易但排序算法的比较、交换、循环边界才是编程基本功。培养循环思维。冒泡排序使用双层循环内层循环负责一趟比较外层循环控制趟数非常适合锻炼对for循环和while循环的理解。面试和考试常考。无论是 Python 二级、数据结构课还是技术面试手写冒泡排序都是高频考点。另外冒泡排序的实现代码短小非常适合用来分析一个算法的执行过程。学会它之后你再接触选择排序、插入排序、快速排序时会有更清晰的方向感。2. 环境准备与 Python 基础回顾2.1 Python 环境说明本文示例代码基于 Python 3推荐使用 3.8 及以上版本。如果你还不知道如何安装 Python可以在 Python 官网下载对应系统的安装包安装时务必勾选“Add Python to PATH”。安装完成后打开终端或命令行输入python --version如果能输出类似Python 3.10.11的版本信息说明环境已经就绪。本文所有代码都使用 Python 自带的标准库和内置函数不需要额外安装第三方包。2.2 列表基础操作回顾冒泡排序的操作对象是列表所以先快速回顾几个列表的基础操作。创建一个列表numbers [5, 2, 9, 1, 7] print(numbers)访问和修改元素numbers[0] 99 print(numbers[0])获取列表长度print(len(numbers))列表的切片操作在观察排序过程时会用到sub numbers[1:3] # 获取索引1到索引2的元素不包含索引3 print(sub)这些操作虽然简单但都是后续代码的基础。如果你对列表切片和索引还不够熟悉可以先用下面的小例子熟悉一下arr [10, 20, 30, 40, 50] print(arr[0]) # 10 print(arr[-1]) # 50负索引从末尾开始数 print(arr[1:4]) # [20, 30, 40]2.3 交换两个变量的值冒泡排序中频繁用到“交换元素”。在 Python 里交换两个变量可以写成a 3 b 5 a, b b, a print(a, b) # 输出 5 3这种写法利用 Python 的元组解包特性不需要中间变量。但在讲解算法原理时为了更通用有时会使用一个临时变量temp来完成交换a 3 b 5 temp a a b b temp print(a, b) # 输出 5 3很多其他语言不支持直接交换所以理解临时变量方式能帮你更好地阅读跨语言代码。在 Python 实战中推荐直接使用a, b b, a代码更简洁。2.4 如何观察排序过程写算法时最容易出现“代码跑完发现结果不对但不知道错在哪”。我的建议是在关键位置加print()把每一轮排序后的列表打印出来用肉眼观察数据变化。后面章节会专门演示这种做法。3. 冒泡排序核心原理拆解3.1 基本思想以升序排列为例冒泡排序的基本思想是每一轮从左到右依次比较相邻的两个元素。如果左侧元素大于右侧元素就交换它们。每一轮结束后当前范围内最大的元素会移动到最右侧。下一轮比较时可以忽略已经排好的右侧区域缩小比较范围。重复上述过程直到所有元素都处于正确位置。3.2 一趟排序做了什么假设有一个列表[5, 1, 4, 2, 8]我们只执行一趟完整的相邻比较来看会发生什么。初始状态[5, 1, 4, 2, 8]第一步比较索引 0 和索引 1 的元素即 5 和 1。因为 5 1交换[1, 5, 4, 2, 8]第二步比较索引 1 和索引 2 的元素即 5 和 4。因为 5 4交换[1, 4, 5, 2, 8]第三步比较索引 2 和索引 3 的元素即 5 和 2。因为 5 2交换[1, 4, 2, 5, 8]第四步比较索引 3 和索引 4 的元素即 5 和 8。因为 5 8不需要交换。一轮结束后列表变成了[1, 4, 2, 5, 8]最大值 8 已经移动到了最后。这一趟操作也验证了一个规律每一趟结束至少能让当前未排序区间的最大值归位。3.3 多趟排序为什么能完成整体排序既然一趟只能让一个最大值归位那包含 n 个元素的列表最多需要 n-1 趟。因为当 n-1 个元素都排好时剩下那个元素自然也在正确位置。继续基于上面的列表第二趟比较范围可以排除最后一个元素。过程中 5 会逐步浮动到倒数第二个位置第三趟时 4 会归位第四趟时 2 和 1 也完成排序。最终得到[1, 2, 4, 5, 8]这里容易有一个误区是不是必须执行正好 n-1 趟不一定。如果列表中某个元素已经有序而且某一轮全程没有任何交换说明列表已经有序可以提前结束。优化时通常利用这一点。3.4 关键代码模板冒泡排序最经典的嵌套循环结构如下n len(arr) for i in range(n - 1): for j in range(n - 1 - i): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j]外层循环i控制第几趟内层循环j控制这一趟比较哪些相邻位置。n - 1 - i是因为每一趟结束后都会有一个元素在末尾固定下来不需要再参与下一趟比较。4. Python 实现列表升序排列的完整实战这一节会从基础版逐步优化写出完整、可直接运行的 Python 冒泡排序代码。4.1 基础版无优化冒泡排序先实现一个最“老实”的版本固定执行n - 1趟每趟都遍历到未排序区间的末尾。# bubble_sort_basic.py def bubble_sort_basic(arr): 对列表进行冒泡排序升序原地修改列表 n len(arr) for i in range(n - 1): # 外层循环控制第几趟 for j in range(n - 1 - i): # 内层循环控制相邻比较 if arr[j] arr[j 1]: # 升序排列左边大于右边就交换 arr[j], arr[j 1] arr[j 1], arr[j] if __name__ __main__: numbers [64, 34, 25, 12, 22, 11, 90] bubble_sort_basic(numbers) print(排序结果:, numbers)运行输出排序结果: [11, 12, 22, 25, 34, 64, 90]这个版本是最容易理解的但没有考虑“提前结束”的可能。如果列表已经有序它仍然会傻乎乎地执行完所有循环。4.2 优化一减少不必要的比较轮数细心观察会发现列表长度是 n 时最多只需要 n-1 趟。即使列表原本已经有序基础版也会把 n-1 趟全部执行完。为了降低最好情况下的时间开销可以增加一个标记变量swapped# bubble_sort_optimized.py def bubble_sort_optimized(arr): 带交换标记优化的冒泡排序升序 n len(arr) 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这个优化的关键点在于如果内层循环一轮遍历下来没有任何相邻元素需要交换那整个列表已经处于有序状态不必再继续剩余循环。例如列表[1, 2, 3, 4, 5]第一轮扫描时所有相邻元素都满足arr[j] arr[j1]swapped保持为False循环直接退出时间复杂度退化为 O(n)。4.3 优化二记录最后一次交换位置还有一个更细致的优化每一轮内层循环的结束位置不一定要按n - 1 - i来定可以记录最后一轮发生交换的位置因为该位置之后的元素在上一轮已经排好序下一轮无需再比较。# bubble_sort_last_swap.py def bubble_sort_last_swap(arr): 记录最后一次交换位置的冒泡排序优化版 n len(arr) end n - 1 while end 0: last_swap 0 for j in range(end): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] last_swap j # 更新最后一次交换的位置 end last_swap # 下次比较只需进行到这里这个优化思路理解起来稍难但在面对大量数据时能减少不少无效比较。初学者可以先把前两种版本写熟练再慢慢消化这一版。4.4 封装成函数实际项目中不建议把排序逻辑直接写在主流程里更推荐封装成函数。函数除了接收待排列表还可以增加一个参数控制升序还是降序def bubble_sort(arr, reverseFalse): 冒泡排序实现 :param arr: 待排序列表 :param reverse: False 表示升序True 表示降序 n len(arr) for i in range(n - 1): swapped False for j in range(n - 1 - i): # 升序时左边大于右边需要交换降序时左边小于右边需要交换 if (not reverse and arr[j] arr[j 1]) or (reverse and arr[j] arr[j 1]): arr[j], arr[j 1] arr[j 1], arr[j] swapped True if not swapped: break调用方式my_list [3, 1, 4, 1, 5, 9, 2, 6] bubble_sort(my_list) print(my_list) # [1, 1, 2, 3, 4, 5, 6, 9] my_list2 [3, 1, 4, 1, 5, 9, 2, 6] bubble_sort(my_list2, reverseTrue) print(my_list2) # [9, 6, 5, 4, 3, 2, 1, 1]这种封装方式对调用方更友好后续修改算法细节时也不会影响外部调用逻辑。4.5 使用示例与输出下面给一个完整的演示脚本包含随机数生成和排序结果打印# demo.py import random def bubble_sort(arr): n len(arr) 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 if __name__ __main__: random.seed(42) data [random.randint(1, 100) for _ in range(10)] print(原始列表:, data) bubble_sort(data) print(排序后为:, data)5. 运行、验证与代码可视化5.1 在命令行运行脚本把上面的demo.py保存到本地后在终端执行python demo.py预期输出类似原始列表: [82, 15, 4, 95, 36, 32, 29, 18, 95, 14] 排序后为: [4, 14, 15, 18, 29, 32, 36, 82, 95, 95]这里的随机数序列是seed(42)固定的所以每次输出相同便于重复观察。5.2 用 print 观察每一轮变化为了看清楚冒泡排序的过程可以改造函数在每轮交换后或每轮结束后打印列表状态def bubble_sort_with_trace(arr): n len(arr) 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 print(f第 {i 1} 轮后: {arr}) if not swapped: break nums [5, 1, 4, 2, 8] print(初始列表:, nums) bubble_sort_with_trace(nums)输出初始列表: [5, 1, 4, 2, 8] 第 1 轮后: [1, 4, 2, 5, 8] 第 2 轮后: [1, 2, 4, 5, 8] 第 3 轮后: [1, 2, 4, 5, 8]这里第 2 轮完成后列表已经有序第 3 轮进入时发现swapped仍为False于是直接退出没有再执行第 4 轮。这个现象就是优化开关在起作用。5.3 用断言验证排序结果手写排序算法之后建议使用assert自动验证结果是否真的正确而不用肉眼一条条检查def test_bubble_sort(): test_cases [ [], [1], [2, 1], [3, 3, 3], [5, 2, 9, 1, 5, 6], [10, 9, 8, 7, 6, 5, 4, 3, 2, 1], ] for case in test_cases: temp case[:] # 复制一份避免影响原列表 bubble_sort(temp) # 调用排序函数 assert temp sorted(case) # 与内置排序结果对比 print(全部测试用例通过) test_bubble_sort()这种测试思路在写算法题时非常实用。利用 Python 内置sorted()作为参照能帮你快速发现代码中的逻辑错误。5.4 小扩展降序排列如果你已经掌握升序排列降序排列只需把比较符号反转def bubble_sort_desc(arr): n len(arr) 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当然也可以复用 4.4 中的reverse参数不必重复写函数。6. 常见问题与排查思路6.1 排序后原列表被修改了问题现象我调用排序函数后原本的列表变了但我不想让原列表被修改。原因分析冒泡排序是原地排序算法函数内对列表元素的修改会直接作用到原对象上。这不是 bug而是设计如此。解决方案如果你需要保留原始列表在调用排序函数前用copy()或切片复制original [3, 1, 2] new_list original[:] # 复制一份 bubble_sort(new_list) # 对副本排序 print(original) # 原列表不受影响或者封装时不修改原列表而是先创建一个新列表再排序def bubble_sort_immutable(arr): result arr[:] # 复制 # 对 result 执行排序 return result6.2 为什么排序函数返回 None问题现象我执行result bubble_sort(my_list)然后打印result发现是None。原因分析你写的函数内部没有return函数默认返回None。原地排序修改的是传入的列表本身所以不需要返回值。这是 Python 中常见的设计像list.sort()就是原地排序并返回None而sorted()则是返回新列表。解决思路如果你想通过返回值接收排序结果要么在函数末尾return arr要么改用排序新列表的实现。6.3 索引越界问题现象代码报错IndexError: list index out of range。原因分析内层循环的边界范围计算错误。常见错误是写成for j in range(n - i): if arr[j] arr[j 1]: # j 最大为 n-1 时arr[j1] 越界解决方法内层循环范围应该是range(n - 1 - i)确保j 1最大为n - 1不会越界。6.4 相等元素位置变化了吗问题现象列表中有相同元素排序后它们的相对顺序会变吗分析冒泡排序只在时交换等于时不交换所以相同元素的先后顺序不会改变。这种性质称为“稳定性”。例如[2a, 1, 2b]排序后2a仍然在2b前面不会因为排序导致相同值的位置颠倒。6.5 列表中有 None 或字符串会报错吗问题现象列表中混入了None或不同类型元素排序时报错TypeError。原因分析冒泡排序依赖比较运算符和。Python 中不同的类型之间通常无法直接比较比如整数和字符串5 3 # TypeError: not supported between instances of int and str对于NonePython 3 中也不允许与数字直接比较。解决建议排序前保证列表元素类型一致。如果确实需要处理混合数据可以自定义比较规则但更推荐在数据清洗阶段就统一类型。6.6 排查清单遇到问题时按下面顺序排查问题现象常见原因解决思路结果不是升序比较符号写反检查还是列表有大数没排到末尾内层循环边界少了-1检查range(n - 1 - i)结果正确但运行慢未做提前退出优化增加swapped标记函数返回 None没有return arr原地排序可忽略返回值原始列表被改动函数内部原地排序调用前切片复制类型错误列表元素类型不一致先统一类型7. 最佳实践与工程建议7.1 排序函数的封装与类型提示日常工程中如果只是排序直接调用sorted()是最省事的。但为了学习或特定场景需要手写冒泡排序时建议给函数加上类型注解和文档字符串让代码更清晰from typing import List def bubble_sort(arr: List[int]) - None: 使用冒泡排序对整数列表进行原地升序排序。 参数: arr: 待排序的整数列表会原地修改。 n len(arr) 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: break7.2 复制列表避免修改原数据无论使用哪种排序函数只要你不希望函数影响原始数据就应该显式地复制data [4, 2, 9, 1] # 推荐使用切片复制 copied data[:] # 或者使用 copy 方法 copied2 data.copy() # 或者list工厂函数 copied3 list(data)记住直接赋值copied data并没有创建新列表两个变量指向的是同一个对象。7.3 什么场景下不应该用冒泡排序冒泡排序的时间复杂度是 O(n²)当列表长度很大例如超过几千甚至上万时性能会明显下降。在生产环境中处理真实业务数据时请直接使用 Python 内置的排序sorted(data)返回一个新的排好序的列表。data.sort()原地排序更节省内存。自定义排序sorted(data, keylambda x: x[age])。冒泡排序更适合教学、算法入门、小规模数据或对性能要求不高的场景。如果你在实际项目中为了提高排序性能手写冒泡排序一定要慎重内置排序 Timsort 的实现远比简单的冒泡排序高效。7.4 结合 lambda 或 key 实现对象排序虽然冒泡排序本身不提供key参数但你可以先对元素应用某种规则生成中间列表再排序。也可以改造冒泡排序让它按照指定的函数返回值进行比较def bubble_sort_by_key(arr, keylambda x: x): n len(arr) for i in range(n - 1): swapped False for j in range(n - 1 - i): if key(arr[j]) key(arr[j 1]): arr[j], arr[j 1] arr[j 1], arr[j] swapped True if not swapped: break students [ {name: Alice, score: 88}, {name: Bob, score: 72}, {name: Cathy, score: 95}, ] bubble_sort_by_key(students, keylambda s: s[score]) print(students)运行后 students 会按成绩score升序排列。这个示例展示了如何将冒泡排序思想灵活运用于字典等复杂对象。7.5 测试与边界情况写任何算法函数都要考虑边界情况空列表[]排序后仍为空。单元素列表[1]排序后不变。全部相同元素[2, 2, 2]算法应稳定且快速结束。倒序列表[5, 4, 3, 2, 1]这是冒泡排序最差的情况。已升序列表[1, 2, 3, 4, 5]优化版可以在第一轮后提前退出。把这些用例写进测试函数能有效避免以后改动代码时引入隐藏 bug。8. 总结与后续学习建议到这里冒泡排序的完整内容已经讲完了。你现在应该能理解冒泡排序的两层循环结构外层控制轮数内层控制相邻比较也能写出带提前退出优化的 Python 函数还知道了原地排序与返回新列表的区别以及如何通过切片复制来保护原始数据。这个过程中接触到的比较、交换、索引边界和稳定性等概念会继续出现在你后续学习的所有排序算法中。下一步可以从两个方向继续深入再实现选择排序、插入排序比较它们和冒泡排序的异同。研究 Python 内置排序为什么快学习 Timsort 的基本思想。如果只是为了业务开发请牢记一点不需要重复造轮子直接使用sorted()或list.sort()。但如果你想提升算法功底或应对面试手写冒泡排序是一个很不错的起点。你可以把本文代码复制到本地试着修改比较符号实现降序试着加入print观察每轮变化再用assert验证结果。多动手改代码理解才会更深刻。