这次我们来聊一个 Python 基础但面试经常被问到的排序问题用冒泡排序实现列表的升序排列。内容不涉及第三方库不依赖 CUDA不挑显卡只要有 Python 解释器就能跑。对于刚学 Python 的朋友来说冒泡排序是理解循环、列表索引和元素交换最好的入门案例之一对于正在准备笔试、面试的朋友来说手写一个可运行的冒泡排序并且能讲清楚时间复杂度和优化思路也是基本要求。先说这篇文章要解决的问题给一个包含数字的 Python 列表比如[64, 34, 25, 12, 22, 11, 90]通过冒泡排序算法把元素从小到大排列好。文章会从冒泡排序的原理讲起给出基础版、优化版、支持自定义排序规则等几种写法然后带你完成功能测试、性能观察和常见错误排查。读完你不仅能写出正确的冒泡排序还能知道什么时候该自己写什么时候直接调sorted()更合适。文章适合这几类读者刚开始学 Python 列表操作的人正在复习数据结构与算法的人想让代码从“能运行”变成“更规范、更可复用”的人。如果你只是想快速把一个列表排成升序可以只看第 5 节的内置方法对比如果你想彻底搞懂冒泡排序建议从头开始看。1. 核心能力速览能力项说明目标使用 Python 手写冒泡排序实现列表升序排列输入Pythonlist元素通常为数字或可比较对象输出原地排序后的原列表从小到大排列内置排序对比可使用list.sort()或sorted()一行完成升序是否依赖第三方库否仅使用 Python 标准库算法时间复杂度平均和最坏情况 O(n²)算法空间复杂度O(1)原地排序只使用常数级别额外空间稳定性稳定排序相等元素相对顺序不变是否支持降序可以修改比较符号或增加reverse参数是否支持复杂对象可以通过key参数或自定义比较逻辑扩展适合场景教学、面试、小规模列表排序不适合场景大数据量排序建议使用内置 Timsort这张表需要特别说明一点冒泡排序的 O(n²) 复杂度是针对比较和交换次数说的。如果列表长度从 1000 变成 10000运行时间可能增加约 100 倍。所以真实业务里的海量数据排序几乎不会手写冒泡排序这也是文章后面会用较大篇幅讲“什么时候不要自己写”的原因。2. 适用场景与使用边界冒泡排序的适用场景非常明确小数据量、教学演示、面试手写算法。先说适合谁。对初学 Python 的人来说冒泡排序是一个非常典型的双重循环结构外层控制排序的趟数内层控制每一趟中相邻元素的比较次数。通过这个案例你可以把range、列表索引、条件判断、元素交换这几个知识点串起来。对准备算法面试的人来说冒泡排序虽然简单但考官可能会让你现场写一个“提前终止的优化版”考察你对循环边界和标志位的理解。再说不适合什么。如果你的列表里有几万、几十万个元素或者你的程序需要频繁排序用冒泡排序会明显变慢。Python 内置的list.sort()和sorted()底层是基于 Timsort 实现的平均时间复杂度是 O(n log n)而且经过大量优化远远优于手写冒泡排序。不要因为学会了冒泡排序就在生产代码里强行用它处理大数据。还有一个边界需要提醒Python 的列表不要求元素类型完全一致但冒泡排序通过或比较元素大小。如果列表中混入无法比较的类型比如数字和字符串放在一起运行时会出现TypeError。这在学习和测试阶段需要特别注意别把“列表能装不同类型”理解成“排序时可以随便混装”。3. 环境准备与前置条件冒泡排序不需要任何第三方库所以环境准备很简单。一个能运行 Python 的环境就够。3.1 确认 Python 版本打开终端或命令行输入以下命令确认 Python 环境可用python --version如果你安装了多个 Python 版本可能需要使用python3python3 --version从输出可以看到当前版本。本文的代码在 Python 3 环境下都可以运行建议至少使用 Python 3.6 以上的版本因为代码中会用到 f-string 等语法时会更方便。需要说明的是不同 Python 小版本之间表现基本一致实际运行请以你本机环境为准。3.2 选择一个运行方式你可以用以下几种方式执行文章里的代码直接在 Python 交互式解释器里逐行输入把代码保存成.py文件比如bubble_sort.py再用python bubble_sort.py运行在 VSCode、PyCharm、Jupyter Notebook 等编辑器里运行。新手比较推荐第二种方式。把代码保存在文件里方便修改和重复运行。3.3 准备测试列表为了演示效果可以先准备几个有代表性的列表nums [64, 34, 25, 12, 22, 11, 90] empty_list [] single_list [42] duplicate_list [5, 3, 8, 5, 2, 5]后续所有代码都可以围绕这些用例测试。验证排序是否正确时最好包含空列表、单元素列表、重复元素列表和乱序列表这样能更全面地发现问题。4. 冒泡排序原理与基础实现4.1 冒泡排序原理冒泡排序的核心思想一句话就能概括每一轮从头到尾比较相邻元素如果前面的元素比后面的大就交换它们。这样每一轮结束后当前未排序部分的最大值就会像气泡一样“浮”到最后面。举个例子。假设列表是[5, 1, 4, 2, 8]第一轮比较过程如下比较 5 和 15 比 1 大交换变成[1, 5, 4, 2, 8]比较当前相邻的 5 和 45 比 4 大交换变成[1, 4, 5, 2, 8]比较 5 和 2交换变成[1, 4, 2, 5, 8]比较 5 和 85 小于 8不交换。第一轮结束后列表最右边的 8 已经是最大值。第二轮只需要比较前 4 个元素也就是[1, 4, 2, 5]的部分。每一轮都会把当前范围内最大的元素送到右端因此已经到位的元素就不再参与后续比较。4.2 基础版代码实现根据上面的原理可以写出第一个版本def bubble_sort(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] return arr这段代码里有几个关键细节外层range(n - 1)n 个元素最多需要 n-1 趟排序。内层range(n - 1 - i)每完成一趟末尾就会多一个已经排好的最大值所以下一轮可以减少一次比较。交换操作arr[j], arr[j 1] arr[j 1], arr[j]是 Python 特有的元组解包写法它等价于其他语言中借助临时变量的交换。这样写更简洁也不会产生多余变量。4.3 运行与预期结果把代码保存成bubble_sort_demo.py内容如下def bubble_sort(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] return arr if __name__ __main__: nums [64, 34, 25, 12, 22, 11, 90] print(排序前:, nums) bubble_sort(nums) print(排序后:, nums)运行结果如下排序前: [64, 34, 25, 12, 22, 11, 90] 排序后: [11, 12, 22, 25, 34, 64, 90]注意bubble_sort(nums)会直接修改传入的列表。看到排序后列表变成升序就说明基础版已经跑通。4.4 原地排序与原列表被修改Python 的列表是可变对象函数内通过arr修改元素会直接影响外部传入的列表。这既是优点也是风险。如果你希望调用函数后保留原列表不变可以先复制一份再对副本排序nums [64, 34, 25, 12, 22, 11, 90] sorted_nums bubble_sort(nums[:]) print(原列表:, nums) print(新列表:, sorted_nums)这里nums[:]创建了原列表的浅拷贝排序发生在副本上。对于元素是不可变对象的列表来说这种拷贝方式足够安全。如果列表里的元素本身是可变对象排序时不会修改这些对象的内部状态通常也安全但如果元素是字典并想按字段排序则需要更复杂的处理方式。5. 冒泡排序优化与 Python 内置方法对比基础版冒泡排序的缺点很明显即使列表已经是升序排列它仍然会执行完所有比较。针对这一点可以加入提前终止机制。5.1 优化版提前终止已经有序的列表思路是如果某一轮比较中一次交换都没有发生说明列表已经有序可以直接跳出外层循环。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 return arr这个版本对基本有序的列表效果很好。例如输入[1, 2, 3, 4, 5]第一轮从头到尾比较一遍没有发生交换立刻结束。基础版仍然需要跑完 n-1 轮而优化版的比较次数显著减少。面试时如果能写出这个优化版本通常会被认为理解了冒泡排序的本质。5.2 优化版记录最后一次交换位置另一个优化思路是记录每轮最后一次发生交换的位置。该位置之后的元素已经有序下一轮比较不需要再访问它们。def bubble_sort_last_swap(arr): n len(arr) last_swap_index n - 1 while last_swap_index 0: border last_swap_index last_swap_index 0 for j in range(border): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] last_swap_index j return arr这个版本比只加标志位的版本更精细。实际效果受数据分布影响但思路本身值得掌握。你不一定在项目里用到它但遇到“手写优化版冒泡排序”的面试题时能多给出一个方案。5.3 使用内置方法一行完成升序回到标题本身任务是“列表升序排列”。站在工程角度Python 已经提供了最直接的工具nums [64, 34, 25, 12, 22, 11, 90] nums.sort() print(nums)也可以用sorted()nums [64, 34, 25, 12, 22, 11, 90] sorted_nums sorted(nums) print(sorted_nums)两者都能实现升序。它们的区别很关键方法是否修改原列表返回值list.sort()原地修改返回Nonesorted(list)不修改原列表返回新的排序列表内置排序是生产环境的首选。底层是 Timsort针对现实中常见的“部分有序”数据做了优化效率和稳定性都远超手写冒泡排序。那为什么还要学冒泡排序因为面试和算法入门仍然需要它。更重要的是理解冒泡排序能帮你理解“稳定排序”“原地排序”“时间复杂度”这些概念这些概念在阅读 Python 官方文档和第三方库源码时经常出现。6. 封装成通用排序函数基础函数只能对数字列表升序排列实际使用时还不够灵活。我们可以把它封装成支持降序、支持按 key 排序的通用函数。6.1 支持升序和降序增加一个reverse参数默认False表示升序传入True表示降序def bubble_sort(arr, reverseFalse): n len(arr) for i in range(n - 1): swapped False for j in range(n - 1 - i): left arr[j] right arr[j 1] need_swap left right if not reverse else left right if need_swap: arr[j], arr[j 1] arr[j 1], arr[j] swapped True if not swapped: break return arr测试nums [64, 34, 25, 12, 22, 11, 90] print(bubble_sort(nums[:], reverseTrue)) # 预期输出[90, 64, 34, 25, 22, 12, 11]6.2 支持按 key 字段排序列表里的元素不一定是简单数字也可能是字典、对象、元组。如果要让学生对象按成绩排序可以传入key函数。实现时要注意不能每比较一次就调用一次key否则效率低且难以保持一致。正确做法是预先计算所有排序键再根据键的对比结果交换原列表元素。def bubble_sort_by(arr, keyNone, reverseFalse): key_func (lambda x: x) if key is None else key n len(arr) keys [key_func(item) for item in arr] for i in range(n - 1): swapped False for j in range(n - 1 - i): left_key keys[j] right_key keys[j 1] need_swap left_key right_key if not reverse else left_key right_key if need_swap: arr[j], arr[j 1] arr[j 1], arr[j] keys[j], keys[j 1] keys[j 1], keys[j] swapped True if not swapped: break return arr测试代码students [ {name: 小明, score: 88}, {name: 小红, score: 95}, {name: 小刚, score: 72}, ] bubble_sort_by(students, keylambda s: s[score]) for student in students: print(student)输出顺序会是小刚、小明、小红。这里用到了“预计算排序键”的做法它能减少重复调用key带来的开销也是内置排序中key参数的一种简化模拟。6.3 批量排序多个列表如果有一批列表需要统一处理可以写一个for循环批量调用lists_to_sort [ [3, 1, 2], [9, 5, 7], [4, 4, 2, 9], ] for index, data in enumerate(lists_to_sort, start1): bubble_sort(data) print(f列表{index}: {data})输出如下列表1: [1, 2, 3] 列表2: [5, 7, 9] 列表3: [2, 4, 4, 9]如果你的批量任务很多建议在每个列表排序前先复制避免外部的原始数据被意外修改。批量处理时可以继续沿用for循环也可以使用列表推导式但要注意列表推导式不适合有副作用的排序函数还是显式循环更清晰。7. 功能测试与效果验证写完排序函数下一步是验证它是否真的正确。冒泡排序的测试重点包括空列表、单元素、重复元素、已升序列表、已降序列表、混合负数和浮点数以及排序稳定性。7.1 使用断言快速验证在开发阶段最直接的验证方式是使用assert断言from bubble_sort import bubble_sort def test_bubble_sort(): assert bubble_sort([64, 34, 25, 12, 22, 11, 90]) [11, 12, 22, 25, 34, 64, 90] assert bubble_sort([]) [] assert bubble_sort([42]) [42] assert bubble_sort([5, 3, 8, 5, 2]) [2, 3, 5, 5, 8] assert bubble_sort([5, 4, 3, 2, 1]) [1, 2, 3, 4, 5] assert bubble_sort([-3, 1.5, 0, -2, 2]) [-3, -2, 0, 1.5, 2] print(所有测试用例通过) if __name__ __main__: test_bubble_sort()这段代码直接输出了判断结果。所有断言没有报错说明函数在基础场景下表现正确。7.2 使用 unittest 做自动化验证当你要长期维护这个函数时建议把测试代码写成标准库unittestimport unittest from bubble_sort import bubble_sort class TestBubbleSort(unittest.TestCase): def test_sorted_asc(self): nums [64, 34, 25, 12, 22, 11, 90] bubble_sort(nums) self.assertEqual(nums, [11, 12, 22, 25, 34, 64, 90]) def test_empty_list(self): nums [] bubble_sort(nums) self.assertEqual(nums, []) def test_single_element(self): nums [1] bubble_sort(nums) self.assertEqual(nums, [1]) def test_duplicate_elements(self): nums [5, 3, 8, 5, 2] bubble_sort(nums) self.assertEqual(nums, [2, 3, 5, 5, 8]) def test_reverse_sorted(self): nums [5, 4, 3, 2, 1] bubble_sort(nums) self.assertEqual(nums, [1, 2, 3, 4, 5]) def test_mixed_numbers(self): nums [1.5, -3, 0, 2, -2.5] bubble_sort(nums) self.assertEqual(nums, [-3, -2.5, 0, 1.5, 2]) if __name__ __main__: unittest.main()运行方式python -m unittest test_bubble_sort.py如果所有用例通过你会看到类似下面的输出...... ---------------------------------------------------------------------- Ran 6 tests in 0.001s OK7.3 稳定性验证冒泡排序是稳定排序意味着相等的元素不会交换顺序。验证时可以在元组中加入原始序号items [(3, a), (1, b), (3, c), (2, d)] bubble_sort(items) print(items)输出中两个数字为 3 的元组应该保持原来的先后顺序即(3, a)依然在(3, c)前面。这就是冒泡排序稳定性的直观验证。7.4 判断预期结果的标准验证排序函数是否成功可以看几个标准排序后列表长度不变。对任意相邻位置i都有arr[i] arr[i 1]。排序后列表中的元素集合与原列表完全一致不发生元素丢失。如果原列表复制后做排序原列表内容不应被修改。写一个验证函数可以代替一部分单元测试def is_sorted(arr): return all(arr[i] arr[i 1] for i in range(len(arr) - 1))测试大量随机数据时这个函数非常实用。它可以配合random.shuffle一遍遍验证算法正确性。8. 性能观察与资源占用冒泡排序最大的缺点是慢。下面具体分析它的时间消耗和资源占用方式。8.1 时间复杂度与空间复杂度对于一个长度为 n 的列表外层循环最多执行 n-1 次内层循环每一轮最多比较 n-1-i 次总比较次数大约是(n-1) (n-2) ... 1 n(n-1)/2因此时间复杂度是 O(n²)。最好情况是列表已经完全有序且使用优化版冒泡排序此时第一轮只比较 n-1 次就结束时间复杂度降低到 O(n)。空间复杂度则始终是 O(1)因为它只用了变量i、j、swapped等常数空间且交换操作不需要额外数组。8.2 使用 timeit 观察不同规模耗时实际运行时间需要在本机测试这里提供一个通用的测量脚本import random import timeit 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 for size in [100, 1000, 5000]: data list(range(size)) random.shuffle(data) elapsed timeit.timeit(lambda: bubble_sort(data[:]), number1) print(f列表大小 {size}: {elapsed:.4f} 秒)随着size增大运行时间会快速上升。在多数电脑上一万个随机整数的排序也会明显卡顿。如果你使用基础版而不是优化版即使输入是有序数据它依然会执行大量无意义比较这一点可以用timeit对比验证。8.3 影响冒泡排序速度的关键因素影响速度的因素主要有以下几类因素影响列表长度 n时间复杂度 O(n²)长度翻倍耗时约翻 4 倍数据是否基本有序优化版可以提前退出明显提速元素比较开销如果元素是复杂对象比较成本更高Python 解释器本身相比编译型语言Python 手写循环天然较慢key函数是否被重复调用预计算 key 比每轮都调用 key 更快如果遇到数据量很大却必须使用冒泡排序的场景可以尝试减少比较范围、使用标志位提前退出、在外层循环开始时检查是否有序。但这些只是治标不治本更稳妥的做法是改用内置排序。9. 常见问题与排查方法手写冒泡排序时最容易遇到下面这些问题问题现象可能原因排查方式解决方案排序后列表并没有变有序内层循环范围用错导致部分相邻元素没有比较打印每一轮列表观察过程内层使用range(n - 1 - i)索引越界IndexError内层循环写成range(n)最后访问arr[j 1]越界查看完整报错堆栈保证j 1 n - i排序结果是降序比较符号使用反了检查if条件升序使用arr[j] arr[j 1]列表没有被修改函数内部重新给arr赋值或使用了切片副本打印传入对象的id和排序后列表使用arr[j]原地修改不要执行arr ...包含不同类型时报TypeError: not supported列表元素类型不统一无法比较检查列表元素类型先统一类型或使用key指定比较字段数字和字符串混排时排序随意报错Python 3 不允许隐式跨类型比较打印元素类型更换输入数据或自定义转换函数函数返回None没有写return arr检查函数末尾按要求返回原列表或新列表基本有序时仍然很慢没有使用提前终止优化增加swapped标志某一轮无交换就break排序结果不正确但代码不报错外层循环次数错误少了一轮使用随机数据反复验证外层range(n - 1)n 为元素个数排序后原列表被修改影响其他业务函数原地排序调用方可能不希望修改确认调用场景调用前使用data[:]传入副本另一个常见误解是list.sort()返回None。很多初学者会写成nums [5, 2, 3, 1] result nums.sort() print(result) # 输出 None而不是排序后的列表如果希望打印排序结果要么打印原变量nums要么使用sorted(nums)。这个坑与手写冒泡排序无关但在 Python 排序相关代码中非常常见建议留意。10. 最佳实践与使用建议10.1 学习阶段多写多验证学习冒泡排序时建议不要只看代码而是动手写一个“打印每一轮排序过程”的调试版本帮助自己建立直观认识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 return arr bubble_sort_with_trace([5, 1, 4, 2, 8])输出如下第 1 轮: [1, 4, 2, 5, 8] 第 2 轮: [1, 2, 4, 5, 8] 第 3 轮: [1, 2, 4, 5, 8]这里第三轮没有发生交换所以提前结束。看到这个过程后你会更清楚为什么需要swapped标志。10.2 生产环境优先使用内置排序日常开发中如果只是想对列表升序排列请记住两条规则要修改原列表用list.sort()要保留原列表生成新列表用sorted()。示例nums [64, 34, 25, 12, 22, 11, 90] nums.sort() # nums 变成升序 sorted_nums sorted(nums) # nums 不变sorted_nums 是升序如果要对字典列表按某个字段升序内置函数更简单students sorted(students, keylambda s: s[score])10.3 将算法封装成可复用模块如果确实要在项目中使用手写排序函数建议把它放在独立模块中例如sorting.py并提供清晰的文档字符串def bubble_sort(arr, reverseFalse): 对列表进行原地冒泡排序。 Args: arr: 可比较元素组成的列表。 reverse: 为 False 时升序为 True 时降序。 Returns: 排序后的原列表。 这样写既方便测试也方便后续替换成更快的排序算法。单元测试尽量覆盖边界条件不要只测一个正常用例。10.4 批量任务要明确数据边界如果你在写批量排序任务建议先确定输入数据的规模和类型。如果每个列表都不大循环调用bubble_sort是可行的如果列表总量很大推荐改为调用内置排序并且使用多线程或多进程时要注意列表属于可变对象避免并发修改同一份数据。排序前后的数据校验最好也要做防止输入源本身包含脏数据。11. 写在最后冒泡排序的代码量不大但它把“循环、比较、交换、边界处理、算法复杂度”这些概念都串在了一起。实现列表升序排列本质上是让每两个相邻元素符合前一个 后一个的关系。只要这个关系成立排序就是正确的。最容易踩的坑有三个一是内层循环边界写错导致索引越界或漏比较二是忘掉函数会原地修改传入列表三是把冒泡排序用于不该它处理的大数据场景。理解了这三点冒泡排序基本就不会出大问题。下一步你可以试着把代码改成降序或者给列表里的字典按某个字段排序再写一组单元测试验证正确性。练习完之后再去对比一下 Python 内置的sorted()源码文档和 Timsort 的原理你就能更清楚为什么实际项目里首选内置排序为什么算法基础仍然值得学。把这篇文章里的代码保存成自己的工具模块面试前拿出来翻一翻比临时背答案有用得多。