排序算法是《数据与数据结构》里绕不开的第一块硬骨头。这次我们重点看 5.3 节冒泡排序的第 3 课时把教材里的基础排序用工程化的方式重新过一遍原理、代码、优化、复杂度、测试、排错一次讲完。如果你正在学数据结构或者准备面试时手写排序算法这篇可以直接收藏。先给结论冒泡排序不是效率最高的排序算法平均时间复杂度是 O(n²)但它代码量小、思路直观、很容易观察每一轮数据的移动过程。对于“理解排序到底在做什么”这件事它比快排、归并更适合作为第一个排序算法来学。本文会用 Python 写出可运行的冒泡排序再补充 C、C、Java 版本最后给出优化方案和一组批量测试用例帮你把教材上的“伪代码”变成真正能跑的代码。读完这篇文章你可以做到三件事第一独立写出一个正确的冒泡排序第二解释清楚为什么内层循环边界是 n-1-i第三能应付“冒泡排序优化”“稳定性”“复杂度分析”这类常见考查点。1. 冒泡排序核心能力速览能力项说明算法类型基于交换的排序算法排序方式原地排序不需要额外大块内存稳定性稳定排序最好时间复杂度O(n)数据基本有序时优化版只需一轮平均时间复杂度O(n²)最坏时间复杂度O(n²)数据逆序时空间复杂度O(1)只使用常量级辅助变量比较次数最坏 n(n-1)/2 次交换次数最坏 n(n-1)/2 次左右适合数据规模几千条以内的小规模数据教学定位排序算法入门、理解两层循环与交换逻辑工程定位基本不用于大规模生产排序但常用于教学和面试基础从表中可以看出来冒泡排序的优点是简单、稳定、原地排序。缺点是数据量一大比较和交换次数会呈平方级增长。实际工程中数据量大时会选择快速排序、归并排序或内置的 sorted() 等更高效的方案但冒泡排序作为理解“比较-交换”模型的基础地位依然很重要。2. 算法原理与单轮排序过程演示冒泡排序的核心思想一句话就能讲完重复遍历待排序的序列依次比较相邻两个元素如果顺序错误就交换直到没有需要交换的元素为止。为什么叫“冒泡”因为每一轮遍历都会把当前未排序部分的最大值像气泡一样“冒”到序列的末尾。以升序排序为例每轮结束后最大的元素一定到达它最终的位置下一轮就只需要处理前面剩下的部分。来看一个具体例子。假设待排序数组是arr [5, 1, 4, 2, 8]第一轮的过程比较 5 和 15 1交换数组变为 [1, 5, 4, 2, 8]比较 5 和 45 4交换数组变为 [1, 4, 5, 2, 8]比较 5 和 25 2交换数组变为 [1, 4, 2, 5, 8]比较 5 和 85 8不交换数组保持 [1, 4, 2, 5, 8]第一轮结束后最大值 8 到了最后一位。第二轮只需要处理前四个元素 [1, 4, 2, 5]最后会把 5 放到倒数第二位。如此反复直到整个数组有序。这里有一个最容易被忽略的边界条件内层循环为什么要写成 range(n - 1 - i)原因分两层相邻元素比较最后一个能参与比较的下标是 n-2它和 n-1 比较所以比较次数是 n-1而不是 n。每完成一轮末尾已经排好了 i1 个元素这些元素不需要再参与下一轮比较所以还要再减 i。如果内层循环写成 range(n)就会出现数组中最后一个下标越界访问并且会重复比较已经排好的元素排序结果可能不正确也可能产生不必要的性能浪费。外层循环控制的是“需要多少轮”。n 个元素最多需要 n-1 轮因为每轮确定一个最大值的位置前 n-1 个位置确定后最后一个位置自然也就确定了。3. Python 实现与运行结果验证Python 是理解算法的好工具代码简洁和教材伪代码之间的转换成本最低。基础版冒泡排序如下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这段代码直接修改了传入的列表也就是“原地排序”。Python 中这种写法是常见做法。测试一下data [64, 34, 25, 12, 22, 11, 90] print(排序前:, data) bubble_sort(data) print(排序后:, data)运行结果排序前: [64, 34, 25, 12, 22, 11, 90] 排序后: [11, 12, 22, 25, 34, 64, 90]如果想在循环过程中观察每一轮的变化可以加打印输出def bubble_sort_debug(arr): n len(arr) print(初始状态:, 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} 轮交换下标 {j} 和 {j 1}: {arr}) if not swapped: print(f第 {i 1} 轮没有发生交换提前结束) break return arr bubble_sort_debug([5, 1, 4, 2, 8])这段调试版代码会打印出每一轮、每一次交换的中间状态。对于学习来说这个输出比只看最终结果有用得多能直观感受到“较大元素逐步向后移动”的过程。特别注意一点bubble_sort_debug 中提前退出用到了 swapped 标记这已经属于优化范畴后面的章节会专门展开。4. C、C、Java 实现对比Python 适合快速验证思路但高中信息技术教材和很多数据结构课程也会用 C 语言描述算法。下面给出 C、C、Java 三个版本方便对照。C 语言版本void bubble_sort(int arr[], int n) { for (int i 0; i n - 1; i) { int swapped 0; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; swapped 1; } } if (swapped 0) { break; } } }C 语言版本最核心的注意点是交换逻辑必须用临时变量 temp 暂存其中一个值。这和 Python 的arr[j], arr[j 1] arr[j 1], arr[j]一行交换有明显区别。C 版本#include vector #include algorithm void bubble_sort(std::vectorint arr) { int n arr.size(); for (int i 0; i n - 1; i) { bool swapped false; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { std::swap(arr[j], arr[j 1]); swapped true; } } if (!swapped) { break; } } }C 版本使用了标准库中的 std::swap代码更简洁。需要注意函数参数是std::vectorint引用传递才会修改原始容器。Java 版本public static void bubbleSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { boolean swapped false; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; swapped true; } } if (!swapped) { break; } } }Java 数组是引用类型方法内部对数组元素的修改会反映到原数组。这是 Java 和 C 类似、但和普通 int 参数传递不同的地方。对比这三个版本可以看到算法思想完全一致区别只在于语言语法Python 用元组解包交换元素写起来最快C 需要手动管理临时变量C 可以用标准库函数Java 的数组下标访问和 C 类似写代码时不要死记硬背某一门语言的写法先记住“两层循环 相邻比较 条件交换”这个骨架再按语言语法翻译即可。5. 三种优化方案提前退出、记录交换点、双向冒泡很多数据结构教材会把冒泡排序直接写成基础版但实际使用时基础版在“数据已经基本有序”的情况下仍然会执行完整的 n-1 轮循环浪费大量比较次数。三种常见优化方案可以显著减少无意义操作。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, 6, 7, 8]优化版只比较 n-1 次时间复杂度从 O(n²) 降到 O(n)这是冒泡排序最好情况的关键。5.2 记录最后交换位置每一轮内层循环中最后一次交换发生的位置说明该位置之后的元素已经是有序状态。下一轮不需要再遍历到数组末尾只需要遍历到最后交换位置即可。def bubble_sort_last_swap(arr): n len(arr) while n 1: last_swap 0 for j in range(n - 1): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] last_swap j 1 n last_swap return arr这种写法把外层循环的 for 换成了 while每轮结束后把 n 更新为最后一次交换的位置。如果某一轮没有交换last_swap 保持 0while 条件 n 1 不成立函数结束。5.3 双向冒泡鸡尾酒排序基础冒泡排序每轮只能将一个最大值移到末尾。双向冒泡则交替进行“从左到右”和“从右到左”两轮遍历一轮把最大值移到最后一轮把最小值移到最前。对于类似 [2, 3, 4, 5, 6, 7, 8, 1] 的数据普通冒泡需要很多轮才能把 1 移到最前面双向冒泡一次就能完成。def cocktail_sort(arr): left 0 right len(arr) - 1 while left right: for j in range(left, right): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] right - 1 for j in range(right, left, -1): if arr[j - 1] arr[j]: arr[j - 1], arr[j] arr[j], arr[j - 1] left 1 return arr双向冒泡并不是复杂度级别上的突破最坏情况依然是 O(n²)但它减少了最值移动所需的轮数在特定数据分布下能明显降低比较次数。三种优化可以叠加使用吗可以。实际生产代码没必要把冒泡优化到极致因为这些优化之后冒泡依然无法和快排、归并竞争。优化的价值更多在于训练思维理解“怎样减少无效操作”这个能力可以迁移到其他算法优化中。6. 接口设计与批量测试从函数到可复用模块很多初学者写完排序函数就直接 print 一下看到结果对就说“完成了”。但想要确认一个排序函数真的正确至少要做多组边界测试和随机数据测试。先确定函数接口设计。这里有两种常见选择原地排序形如bubble_sort(arr)修改原列表不返回新列表。返回新列表形如sorted_arr bubble_sort(arr)不修改原列表。教材中的伪代码通常采用原地排序Python 的list.sort()也是原地排序内置函数sorted()则返回新列表。实际写代码时两种方式都可以但一定要在注释或文档里说明清楚避免调用者混淆。接口确定后批量测试可以这样写import random 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 def test_sort(sort_func): test_cases [ [], [1], [2, 1], [5, 4, 3, 2, 1], [1, 2, 3, 4, 5], [3, 1, 2, 3, 1], [random.randint(0, 1000) for _ in range(100)], [random.randint(0, 10000) for _ in range(1000)], ] for i, case in enumerate(test_cases): expected sorted(case) result sort_func(case.copy()) assert result expected, f用例 {i} 失败: {result} ! {expected} print(f用例 {i} 通过数据量为 {len(case)}) test_sort(bubble_sort)这段测试代码覆盖了空列表、单元素、逆序、顺序、重复元素、随机数据等多个场景。使用 assert 断言一旦某个用例不通过就会直接抛出异常并指出是哪组数据出错。注意一个细节调用sort_func(case.copy())传的是副本防止测试数据被原地排序修改后影响后续用例。这个习惯在实际项目中非常重要。还可以扩展统计比较次数和交换次数def bubble_sort_with_count(arr): n len(arr) compare_count 0 swap_count 0 for i in range(n - 1): for j in range(n - 1 - i): compare_count 1 if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] swap_count 1 return arr, compare_count, swap_count运行这个函数可以得到一组具体数字。以完全逆序的 10 个元素为例比较次数是 45 次交换次数也是 45 次。这个统计过程能帮助理解复杂度的计算方式。7. 复杂度分析与性能观察冒泡排序的复杂度分析是考试和面试的高频考点需要从两个维度理解比较次数和交换次数。最坏情况是输入数组完全逆序。例如 [5, 4, 3, 2, 1]每一对相邻元素都需要交换。第一轮比较 n-1 次第二轮比较 n-2 次最后一轮比较 1 次。总比较次数是(n-1) (n-2) ... 1 n(n-1)/2交换次数和最坏情况下的比较次数相同也是 n(n-1)/2。所以最坏时间复杂度是 O(n²)。平均情况下数组中约有一半的元素位置需要调整比较次数仍然接近 n(n-1)/2因此平均时间复杂度也是 O(n²)。最好情况是输入已经有序。优化版冒泡排序只需要一轮 n-1 次比较发现没有交换后立即退出时间复杂度是 O(n)。未优化的基础版即使数据已经有序仍然会执行完整的 n-1 轮循环复杂度保持 O(n²)。这就是为什么实际使用中几乎都要加提前退出标记。空间复杂度方面冒泡排序是原地排序只需要一个临时变量用于交换元素空间复杂度是 O(1)。稳定性方面冒泡排序是稳定的。关键在于只有当arr[j] arr[j 1]时才交换如果两个元素相等不交换因此它们原本的相对顺序不会被破坏。这一点和选择排序不同选择排序在某些实现下不稳定。在性能观察时可以设计一个简单的对比实验分别对 100、1000、10000 个随机整数执行排序用 time.perf_counter() 统计耗时import time import random def run_time_test(sort_func, data): start time.perf_counter() sort_func(data.copy()) return time.perf_counter() - start for size in [100, 1000, 10000]: data [random.randint(0, 100000) for _ in range(size)] elapsed run_time_test(bubble_sort, data) print(f数据量 {size}: {elapsed:.4f} 秒)运行时间和机器性能相关但趋势非常明确数据量从 1000 增加到 10000数据量扩大 10 倍运行时间大约会扩大 100 倍左右这正是 O(n²) 复杂度的直观体现。如果数据量进一步增加到 10 万级冒泡排序的运行时间会迅速变得不可接受。8. 常见问题与排查方法问题现象可能原因排查方式解决方案程序报错 list index out of range内层循环边界写成 range(n)访问到 arr[n]检查内层循环改为 range(n - 1 - i)排序后数组没有变化传入的是列表副本函数结果没有返回打印函数内外变量原地排序不 return或在函数开始时 arr arr.copy()只排好一部分元素外层循环轮数不足打印每一轮结果外层循环改为 range(n - 1)数据基本有序但运行很慢缺少提前退出优化统计每轮是否发生交换加入 swapped 标记相等元素顺序被打乱条件写成 用包含重复元素的数据测试改为 调用自定义排序后原数据被修改函数原地修改列表检查调用方式调用时传入 copy()或设计返回新列表运行时间明显异常未加优化且数据接近 O(n²) 最坏情况统计比较次数使用优化版或数据量大时改用更优排序算法这里重点提两个最典型的问题。第一个是下标越界。初学者最容易把内层循环写成for j in range(n)再加上访问arr[j 1]当 j 等于 n-1 时arr[n] 必然越界。正确写法的关键不是死记代码而是理解“相邻元素比较最多只能进行到倒数第二个元素”。第二个是原地排序和返回值混淆。Python 中如果函数直接修改传入的列表函数内部没有再 return调用后原列表会被修改。如果调用时写result bubble_sort(data)result 会是 None让人误以为排序失败。解决办法是明确接口约定要么原地修改并 return arr要么只修改原列表不返回调用者不要直接 print 函数结果。9. 学习与教学建议如果你是在课堂上学习这一节或者准备教这一节下面的建议可以直接参考。第一先不要对着教材代码抄。先准备 5 个左右的小数字手动模拟一轮冒泡过程把每一轮比较和交换的结果写下来。手动模拟时最容易理解“为什么每轮结束末尾元素已经固定”。第二写代码时把调试输出打开。前面给出的 bubble_sort_debug 函数就是很好的学习工具。每一步交换后打印数组可以看到较大的数字一步步向后移动这个过程远看文字描述更有画面感。如果环境支持还可以把过程绘制成柱状图动画效果更直观。第三重点解决内层循环边界。让学习者自己修改几组 n 值观察 range(n - 1 - i) 的实际范围。例如 n5 时第一轮 i0内层循环 range(4)比较下标 0 和 1、1 和 2、2 和 3、3 和 4第二轮 i1内层循环 range(3)比较下标 0 和 1、1 和 2、2 和 3。把数字拆开看边界问题一次就能理解。第四优化部分按顺序讲。先讲提前退出再讲记录最后交换位置最后讲双向冒泡。每一步都回到“减少无效操作”这个核心目标学生就能明白优化不是炫技而是有明确收益的实际问题。第五一定要写批量测试。很多学生写完排序算法后只用一组数据验证这远远不够。空列表、单元素、重复元素、逆序数据、随机数据都要测。养成批量测试的习惯后后续学习选择排序、插入排序、快速排序时都会受益。10. 总结与下一步冒泡排序是数据结构课程中第一个真正意义上的排序算法。它的价值不在于“快”而在于用最简单的方式展示了排序算法的核心逻辑比较、交换、重复、收敛。建议最先掌握的知识点是两层循环结构和边界条件这是冒泡排序最容易出错也最需要理解清楚的地方。最容易踩的坑是内层循环写成 range(n) 导致越界以及 Python 中原地修改与返回 None 造成调用结果混淆。建议先花 10 分钟手动模拟一轮排序再动手写基础版最后加上提前退出优化并用批量测试脚本验证正确性。学完冒泡排序之后下一步可以按顺序学习选择排序、插入排序、希尔排序、归并排序和快速排序。其中快速排序和归并排序分别代表了“分而治之”和“递归”两大核心思想理解起来要比冒泡排序难一些但底层仍然离不开“比较与交换”这些基础操作。把冒泡排序真正吃透之后后面算法的学习会顺畅得多。
