冒泡排序详解：从原理到代码实现与优化，数据结构入门必学

从“看不懂”到“能默写”冒泡排序为什么是数据结构的第一课如果你正在学《数据与数据结构》选修一大概率会在 5.3 节遇到冒泡排序。很多同学在这里容易卡住不是因为代码有多难而是因为不知道这段代码到底在干嘛为什么要两重循环为什么内层循环要减i为什么明明叫“冒泡”代码里却没有一个气泡这篇文章的目的很简单把冒泡排序从原理讲到代码再从代码讲到易错点让你看完之后不仅能看懂教材上的示例还能自己动手写出来、跑起来并知道它适合解决什么问题、不适合解决什么问题。我们直接给出一个判断冒泡排序是排序算法里最适合“第一次学习”的算法不是因为它最高效而是因为它把“比较”和“交换”这两个排序的基本动作展示得最透明。你把这个算法的逻辑吃透了后面学选择排序、插入排序、快速排序都会轻松很多。1. 这篇文章真正要解决的问题很多初学者面对冒泡排序真正的问题不是“看不懂代码”而是没有建立起算法的执行过程画面。教材上通常直接给出代码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]这段代码看起来很短但它背后藏着三层逻辑外层循环控制什么控制“总共需要几轮排序”。内层循环控制什么控制“每一轮比较到哪个位置为止”。交换条件是什么相邻两个元素如果前一个比后一个大就交换位置。如果你只是抄代码不理解这三层逻辑一旦题目稍微变化——比如要求从大到小排序、要求只排一部分数据、要求统计交换次数——就容易懵。这篇文章会从最基础的概念讲起接着用一张过程表模拟冒泡排序的完整执行过程再给出 Python、C、Java 三种语言的完整代码实现最后讲解复杂度、常见坑和优化思路。读完你不仅能应付考试和实验报告还能真正理解“排序算法”这类问题的通用解法。2. 冒泡排序的核心概念与适用场景2.1 什么是排序排序就是按照某种规则把一组数据重新排列。比如把成绩从高到低排列把商品价格从低到高排列把姓名按照字典序排列。排序在计算机科学里非常基础因为查找、去重、统计等很多操作都依赖有序数据。可以这么说如果你拥有一组有序数据很多问题的难度都会立刻下降一档。2.2 冒泡排序的基本思想冒泡排序的英文名是 Bubble Sort。它的思路非常直观重复地遍历要排序的列表依次比较相邻两个元素如果它们的顺序错误比如前一个大于后一个就把它们交换位置。每一轮遍历都会把当前范围内最大的元素“浮”到末尾就像气泡从水底浮到水面因此得名“冒泡排序”。这个描述里有两个关键信息比较对象是相邻元素不是任意两个元素。这一点和选择排序有明显区别。每一轮确定一个元素的最终位置。第一轮确定最大值的位置第二轮确定第二大的位置以此类推。2.3 冒泡排序适合什么场景冒泡排序的时间复杂度是O(n²)在数据量较大时效率偏低。它的适用场景主要是数据量较小比如几十个、几百个元素教学演示帮助理解排序算法的基本流程数据本身基本有序利用优化后的冒泡排序可以快速完成排序对稳定性有要求且数据量不大的场景。不适用场景也很明确海量数据排序比如百万级数据性能要求很高的实时排序。2.4 初学者最容易误解的几个点误区一以为冒泡排序是“把最小的浮上来”这是理解偏差。冒泡排序每轮是把当前未排序部分的最大值“沉”到末尾或者理解成把大元素往右移动。当然你也可以调整比较条件把最小值“冒”到最前面但那需要改变内层循环的遍历方向和交换条件。教材上的标准写法默认是把最大值送到底部。误区二以为内层循环每次都要比较到最后一个位置这个误区非常常见。第一轮比较到最后一个元素没问题但第二轮已经确定最后一个是最大值了没必要再比较它。所以内层循环的范围是n - 1 - i其中i是外层已经完成的轮数。这就叫“有序区”和“无序区”的划分。误区三以为交换可以用等号直接赋值这是新手写代码最容易出错的地方arr[j] arr[j 1] arr[j 1] arr[j] # 错误此时 arr[j] 已经变成原 arr[j1] 的值这种写法会把两个数字都变成同一个值导致数据丢失。交换必须使用临时变量或者使用 Python 的元组交换语法。3. 冒泡排序的算法原理与过程模拟3.1 算法步骤冒泡排序的标准步骤如下从第一个元素开始比较arr[0]和arr[1]。如果arr[0] arr[1]交换它们。继续比较arr[1]和arr[2]如果顺序错误交换。重复这个过程直到比较完最后一对相邻元素arr[n-2]和arr[n-1]。此时最大的元素已经被移动到了最后一个位置。对前n-1个元素重复上述过程因为最后一个元素已经就位。每次减少一个元素的比较范围直到只剩一个元素为止。3.2 完整过程模拟我们用一个具体例子来模拟。假设数组初始为[64, 34, 25, 12, 22, 11, 90]第一轮排序比较操作比较结果操作数组状态64 vs 3464 34交换[34, 64, 25, 12, 22, 11, 90]64 vs 2564 25交换[34, 25, 64, 12, 22, 11, 90]64 vs 1264 12交换[34, 25, 12, 64, 22, 11, 90]64 vs 2264 22交换[34, 25, 12, 22, 64, 11, 90]64 vs 1164 11交换[34, 25, 12, 22, 11, 64, 90]64 vs 9064 90不交换[34, 25, 12, 22, 11, 64, 90]第一轮结束后90 到达了最终位置。观察数组最大的元素已经沉到了最右边。第二轮排序比较范围缩减为前 6 个元素比较操作比较结果操作数组状态34 vs 2534 25交换[25, 34, 12, 22, 11, 64, 90]34 vs 1234 12交换[25, 12, 34, 22, 11, 64, 90]34 vs 2234 22交换[25, 12, 22, 34, 11, 64, 90]34 vs 1134 11交换[25, 12, 22, 11, 34, 64, 90]34 vs 6434 64不交换[25, 12, 22, 11, 34, 64, 90]第二轮结束后64 也到达了最终位置。第三轮排序比较操作比较结果操作数组状态25 vs 1225 12交换[12, 25, 22, 11, 34, 64, 90]25 vs 2225 22交换[12, 22, 25, 11, 34, 64, 90]25 vs 1125 11交换[12, 22, 11, 25, 34, 64, 90]25 vs 3425 34不交换[12, 22, 11, 25, 34, 64, 90]第三轮结束后34 到达最终位置。第四轮排序比较操作比较结果操作数组状态12 vs 2212 22不交换[12, 22, 11, 25, 34, 64, 90]22 vs 1122 11交换[12, 11, 22, 25, 34, 64, 90]22 vs 2522 25不交换[12, 11, 22, 25, 34, 64, 90]第四轮结束后25 到达最终位置。第五轮排序比较操作比较结果操作数组状态12 vs 1112 11交换[11, 12, 22, 25, 34, 64, 90]12 vs 2212 22不交换[11, 12, 22, 25, 34, 64, 90]第五轮结束后22 到达最终位置。第六轮排序只剩下[11, 12]比较后顺序正确无需交换。最终结果为[11, 12, 22, 25, 34, 64, 90]这个模拟过程非常重要。你可以看到每一轮内层循环结束时都会有一个元素被“固定”在它最终的位置上。这正是判断是否跳出外层循环的关键依据。4. 冒泡排序的完整代码实现4.1 Python 实现def bubble_sort(arr): 冒泡排序升序 参数: arr: 待排序的列表会原地修改 n len(arr) # 外层循环控制排序轮数一共需要 n-1 轮 for i in range(n - 1): # 内层循环在未排序部分进行相邻比较 # n - 1 - i 表示每轮结束后末尾已经有 i 个元素就位 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__: test_arr [64, 34, 25, 12, 22, 11, 90] print(排序前:, test_arr) bubble_sort(test_arr) print(排序后:, test_arr)运行结果排序前: [64, 34, 25, 12, 22, 11, 90] 排序后: [11, 12, 22, 25, 34, 64, 90]Python 代码里arr[j], arr[j 1] arr[j 1], arr[j]是 Python 特有的元组赋值交换。如果使用其他语言一般需要临时变量。4.2 C 实现// 文件路径bubble_sort.cpp #include iostream using namespace std; void bubbleSort(int arr[], int n) { // 外层循环控制排序轮数 for (int i 0; i n - 1; i) { // 内层循环在未排序部分进行相邻比较 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; } } } } int main() { int arr[] {64, 34, 25, 12, 22, 11, 90}; int n sizeof(arr) / sizeof(arr[0]); cout 排序前: ; for (int i 0; i n; i) { cout arr[i] ; } cout endl; bubbleSort(arr, n); cout 排序后: ; for (int i 0; i n; i) { cout arr[i] ; } cout endl; return 0; }C 的交换需要使用临时变量temp这是和 Python 最大的区别。如果忘记临时变量直接arr[j] arr[j1]数据就会丢失。运行结果排序前: 64 34 25 12 22 11 90 排序后: 11 12 22 25 34 64 90编译运行命令g bubble_sort.cpp -o bubble_sort ./bubble_sort4.3 Java 实现// 文件路径BubbleSort.java public class BubbleSort { public static void bubbleSort(int[] arr) { int n arr.length; // 外层循环控制排序轮数 for (int i 0; i n - 1; i) { // 内层循环在未排序部分进行相邻比较 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; } } } } public static void main(String[] args) { int[] arr {64, 34, 25, 12, 22, 11, 90}; System.out.print(排序前: ); for (int num : arr) { System.out.print(num ); } System.out.println(); bubbleSort(arr); System.out.print(排序后: ); for (int num : arr) { System.out.print(num ); } System.out.println(); } }运行结果排序前: 64 34 25 12 22 11 90 排序后: 11 12 22 25 34 64 90编译运行命令javac BubbleSort.java java BubbleSort5. 从内层循环边界看“减 i”的真正含义上面三种语言的实现里最核心也最容易写错的一行代码是for j in range(n - 1 - i):很多同学不理解为什么要- i。这里用图示方式解释。假设数组有n 7个元素第 1 轮排序前所有元素都未确定位置需要比较n-1 6次也就是比较arr[0]~arr[1]、arr[1]~arr[2]、……、arr[5]~arr[6]。第 1 轮结束后arr[6]已经是最大值。第 2 轮排序时我们只需要处理前 6 个元素即比较arr[0]~arr[5]只需要 5 次也就是n-2次。第 3 轮排序时只需要处理前 5 个元素比较 4 次也就是n-3次。归纳一下第i轮从 0 开始计数需要比较n - 1 - i次。所以这行代码不是“魔法”。它的作用就是每一轮少比较一次因为上一轮确定位置的元素已经无需再参与比较。如果这里不写- i会怎样程序仍然可能运行只是多做了很多毫无意义的比较。比如for j in range(n - 1):这样每一轮都会从头比较到末尾把已经排序好的元素再比一遍效率变低但结果通常还是正确的。所以从“结果正确”的角度看这个 bug 不太致命但从“算法效率”和学习规范的角度看这就是错误写法必须避免。6. 冒泡排序的时间复杂度与空间复杂度分析6.1 时间复杂度分析冒泡排序核心是看比较次数和交换次数。最坏情况待排序数组是逆序的即完全反序。第 1 轮比较n-1次交换n-1次第 2 轮比较n-2次交换n-2次依次递减。总的比较次数为(n-1) (n-2) ... 1 n(n-1)/2因此最坏时间复杂度为O(n²)。最好情况待排序数组已经有序。第 1 轮比较n-1次发现没有任何元素需要交换如果代码里加入了“是否交换”的标志位可以提前退出此时时间复杂度为O(n)。平均情况时间复杂度也是O(n²)。6.2 空间复杂度冒泡排序是原地排序它只需要常数级别的额外空间比如交换用的临时变量所以空间复杂度是O(1)。6.3 稳定性稳定性的定义是如果两个相等元素的相对顺序在排序前后保持不变那么算法是稳定的。冒泡排序在比较时只有当前一个元素严格大于后一个元素才会交换。如果两个元素相等不满足arr[j] arr[j1]不会交换。因此冒泡排序是稳定排序算法。维度结论最坏时间复杂度O(n²)最好时间复杂度O(n)平均时间复杂度O(n²)空间复杂度O(1)稳定性稳定排序方式原地排序7. 冒泡排序的优化思路从“傻比较”到“聪明退出”标准冒泡排序有一个明显问题即使数组已经有序它仍然会傻傻地执行完所有轮次。我们可以加入一个“交换标志”如果某一轮完全没有发生交换说明数组已经有序直接退出。7.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这种优化对“基本有序”的数组效果非常明显。比如数组[1, 2, 3, 4, 5, 6]只比较一轮 5 次发现没有交换直接退出。7.2 记录最后交换位置还有一种更精细的优化记录每一轮最后一次交换的位置下一轮只需要比较到该位置即可。def bubble_sort_last_swap(arr): n len(arr) last_swap n - 1 while last_swap 0: current_last 0 for j in range(last_swap): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] current_last j # 记录最后一次交换的位置 last_swap current_last # 下一轮只需比较到 current_last这种优化的原理是current_last之后的元素都已经有序无需再比较。7.3 双向冒泡排序鸡尾酒排序传统冒泡每轮只向一个方向移动最大值。双向冒泡则是先向右移动最大值再向左移动最小值交替进行。它在处理“大部分元素已经有序、少量元素位于两端”的数组时比标准冒泡更快。def cocktail_sort(arr): n len(arr) start 0 end n - 1 swapped True while swapped: swapped False # 从左到右把最大值移动到 end for j in range(start, end): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] swapped True if not swapped: break end - 1 swapped False # 从右到左把最小值移动到 start for j in range(end - 1, start - 1, -1): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] swapped True start 1双向冒泡在某些场景下可以减少排序轮数但实现复杂度更高。从教材“第一课时”的角度先掌握标准冒泡即可双向冒泡可以作为拓展内容。8. 冒泡排序的常见问题与排查方法8.1 数组越界错误问题现象可能原因排查方式解决方案程序报IndexError: list index out of range内层循环边界多写了 1比如range(n - 1)写成range(n)导致arr[j1]访问到不存在的下标检查j 1最大取值是否小于数组长度内层循环严格写成range(n - 1 - i)C 访问越界但不报错结果异常数组长度计算错误或者循环变量越界用sizeof(arr) / sizeof(arr[0])或直接传入n打印输出每个循环的j最大值确认j1 n8.2 排序结果不对问题现象可能原因排查方式解决方案排序后仍然乱序交换逻辑写错了比如赋值顺序颠倒用小数组手动模拟一轮使用临时变量或者 Python 元组交换从大到小排成了从小到大比较条件方向写反检查if语句的比较运算符降序排序把改成某些元素缺失或重复交换时覆盖了数据检查是否有arr[j] arr[j1]后没有临时变量保护确保交换三步temparr[j]; arr[j]arr[j1]; arr[j1]temp8.3 排序效率极低问题现象可能原因排查方式解决方案数据量大时排序很慢使用了冒泡排序处理大规模数据分析数据量是否超过几千换用快速排序、归并排序等更高效的算法数据已经有序但仍然执行很多轮没有添加“是否交换”标志位在每轮结束后打印本轮是否发生交换加入swapped标志提前退出8.4 空数组或单元素数组对于空数组[]或只有一个元素的数组[5]标准冒泡排序也需要能正常工作。检查方法很简单len(arr) 0时外层循环n - 1为负数导致外层循环不会执行len(arr) 1时外层循环执行 0 次。代码应该自然处理这种情况如果报错检查是否在循环前使用了arr[0]。9. 冒泡排序的教学深层次价值排序算法有很多为什么第 5.3 节偏偏先讲冒泡排序一个重要的原因是冒泡排序把“比较”和“交换”这两个最基本的操作展示得最直观。它的逻辑链条是线性的输入数组 → 比较相邻元素 → 发现顺序错误 → 交换 → 继续比较 → 最大值沉底 → 缩小范围 → 重复这种理解路径天然适合初学者建立“算法执行过程”的心理模型。而快速排序需要在脑子里递归分治归并排序需要理解合并有序数组初学者直接上手容易卡住。从教学角度看冒泡排序还是理解“循环不变式”的绝佳素材。所谓循环不变式就是“在循环的每一轮开始时哪些条件一定成立”。对于冒泡排序来说外层循环执行到第i轮时数组末尾的i个元素已经是排序好的最大值内层循环每执行一次都会把当前范围内的最大值向后移动一格。如果你能自己说出这两句话说明你对冒泡排序的理解已经超过了“背代码”的阶段。10. 冒泡排序的常见变式与易错辨析10.1 从大到小排序只需要把交换条件改一下if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j]判断条件从“前一个大于后一个才交换”改成“前一个小于后一个才交换”。这样每一轮会把最小值沉到末尾最终得到降序序列。10.2 使用 while 循环实现有些教材愿意使用 while 循环来实现冒泡排序便于控制循环退出条件def bubble_sort_while(arr): n len(arr) i 0 while i n - 1: j 0 while j n - 1 - i: if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] j 1 i 1这种写法逻辑不变只是把for循环改成while循环。好处是变量i、j的生命周期更可见适合调试。10.3 传值 vs 传引用在 Python 中列表作为参数传入函数函数内部对列表的修改会直接反映到原列表上因为 Python 传递的是引用。所以上面bubble_sort(arr)会修改原数组。在 C 中数组名本身就是指针函数内部修改数组同样会影响原数组。在 Java 中数组也是引用类型传入函数后修改会影响原数组。如果你不希望修改原数组可以在调用时复制一份new_arr arr.copy() bubble_sort(new_arr)11. 冒泡排序的两个“反直觉”真相11.1 外层循环真的需要 n-1 轮吗理论上n个元素最多需要n-1轮排序。因为每轮至少能确定一个元素的最终位置。如果某一轮没有发生任何交换说明数组已经有序可以提前退出。但一个常见问题是即使数组在第 2 轮就已经有序标准冒泡仍然执行剩余的轮次。这就是为什么“基准版本”效率低而加上swapped标志的优化版本更适合实际使用。11.2 冒泡排序在数据“近似有序”时表现并不差虽然冒泡排序的时间复杂度是O(n²)但经过优化的冒泡排序对近似有序的数组非常友好。比如数组[1, 2, 3, 4, 6, 5]优化后的冒泡排序第一轮就能发现只有一次交换第二轮再比较时发现没有交换直接退出。总共只做了5 4 9次比较时间复杂度接近O(n)。这意味着选择排序算法时“数据初始状态”是一个不可忽视的因素。这也是为什么某些场景下即使冒泡排序平均性能一般开发人员仍然会选择它——因为它对“基本有序”的数据表现相当好。12. 冒泡排序与选择排序、插入排序的对比学冒泡排序时最好同时了解它与选择排序、插入排序的区别这样才能在真实项目里做出合理选择。排序算法基本思想时间复杂度平均空间复杂度稳定性冒泡排序相邻比较逐步把最大值推到最后O(n²)O(1)稳定选择排序每轮从未排序部分选出最小值放到最前面O(n²)O(1)不稳定插入排序将每个元素插入到已排序部分的合适位置O(n²)O(1)稳定三者的对比可以这样理解冒泡排序像一群人在排队相邻两个人不断比较身高高的往后站直到最高的站到最后。选择排序像老师每次从队伍里找出最矮的让他站到最前面然后从剩下的人里再找最矮的。插入排序像你打扑克牌时每摸一张新牌就把它插入到手牌中的合适位置。这种类比能帮你区分三种算法的核心操作完全不同冒泡是“相邻交换”选择是“选取最值”插入是“定位插入”。13. 冒泡排序的动手练习建议只看不练很难真正理解算法。建议按以下顺序练习练习 1过程模拟准备 10 张扑克牌随机打乱。按照冒泡排序的思路手动执行两轮排序每执行一轮用手机拍下当前牌序。最后和代码运行结果对比。练习 2代码改造把本文的 Python 代码复制到本地依次完成以下改造把升序改成降序添加swapped标志打印每轮是否有交换添加一个参数reverseFalse控制排序方向把列表改为字符串列表实现按字典序排序。练习 3统计交换次数修改代码返回排序过程中的交换次数。思考一个完全逆序的长度为n的数组交换次数是不是n(n-1)/2练习 4理解提前退出构造一个已经有序的数组运行优化版冒泡排序打印“实际执行轮数”。你会发现只执行了 1 轮。14. 章节总结与学习方法建议写到这里冒泡排序的核心内容已经完整覆盖了。我们重新梳理一下这节课的关键点冒泡排序的思想通过相邻元素的比较和交换把最大值逐步“沉”到末尾。代码结构外层循环控制轮数内层循环控制每轮的比较范围核心是for j in range(n - 1 - i)。时间复杂度最坏O(n²)最好O(n)空间复杂度O(1)是稳定排序。优化方向添加交换标志提前退出记录最后交换位置或者使用双向冒泡。常见坑数组越界、交换逻辑错误、内层循环边界忘记减i。如果你正在准备数据结构考试或者做 5.3 节的课后作业建议按照“模拟一遍过程 → 自己写一遍代码 → 调试到通过 → 尝试改造成降序 → 尝试加优化”这个顺序来学习。代码写不出来没关系先从纸上模拟开始模拟三遍之后代码自然就能写出来了。冒泡排序是整个排序算法章节的“入门钥匙”。它的代码虽然简单但承载了“比较”“交换”“循环嵌套”“边界条件”“复杂度分析”这些贯穿整个数据结构课程的核心概念。把这一节学扎实后面学习快速排序、归并排序时你会明显感觉轻松很多。建议把本文从过程模拟到代码实现完整过一遍再找几道排序相关的练习题动手验证。等你能不看书就写出一段正确的、带优化标志位的冒泡排序代码这一节的任务就真正完成了。