冒泡排序大概是很多人学编程时遇到的第一个排序算法名字听起来甚至有点可爱——像水底冒上来的气泡。但真正把冒泡排序学透的人并不多。高中信息技术选择性必修一《数据与数据结构》5.3 小节用三节课讲冒泡排序第三节课通常要解决两件事一是把前面学过的“比较—交换”思路完整写成程序二是在基础版本之上做优化理解为什么要记录“是否发生交换”。很多同学卡在这里不是因为算法难而是因为代码里的边界条件、循环嵌套和交换逻辑混在一起稍微一走神就写错了。这篇文章想做一个完整的梳理从教材 5.3 冒泡排序3出发把原理、代码、优化、验证、考试考点一次讲清楚。无论你是正在学选修一的高中生还是刚接触数据结构的大学新生或者想复习排序基础准备面试的开发者这篇文章的思路都适用。读完这篇文章你能做到三件事第一不看教材也能默写出冒泡排序的 Python 和 C 语言实现第二理解“提前结束”“记录边界”两个优化点为什么能让冒泡排序在最好情况下达到 O(n) 复杂度第三面对考试中的流程追踪题和代码补全题不会再搞错内层循环的边界条件。1. 这篇文章真正要解决的问题为什么一个几十年前的简单排序算法值得专门用三节课来学先给一个判断冒泡排序不是用来“实际排序大数据”的它是用来“建立算法思维”的。真正工程里没人用冒泡排序排十万条数据但几乎每个学编程的人都要先写一遍冒泡排序。原因在于它把算法最核心的三个东西一次全部呈现出来循环嵌套、条件判断、状态交换。这三个东西组合在一起就构成了绝大多数排序算法的骨架。对于选修一这门课来说5.3 冒泡排序3处在第五章排序部分的中间位置前两节课通常完成“什么是排序”“冒泡排序的基本思路”“手工模拟一轮排序”这些任务第三节课的重点自然落到编程实现和算法优化上。换句话说前两节课解决“看得懂”第三节课解决“写得出、写得对、写得聪明”。这篇文章要解决的痛点很具体很多同学能够手工模拟冒泡排序但一到写代码就出错最常见的是内层循环的边界写错把 n 和 n-1-i 混在一起结果要么数组越界要么少排一轮。另一个痛点是教材或很多资料会提到“优化”但优化到底优化了什么、优化后效率提升多少、为什么最好情况下复杂度能变成 O(n)很多文章没有讲透。本文会把这两件事都拆开讲清楚。我还会额外讲一个很容易被忽略的问题怎么看一段冒泡排序代码对不对。很多新手写完代码直接运行看到结果“看起来排序了”就结束。实际上验证排序算法要关注的不只是最终结果还包括每一轮执行完后数组的状态、比较次数、交换次数、以及是否提前退出。这些观察点才是考试和工程调试真正需要的。2. 冒泡排序的核心原理与适用场景2.1 核心原理相邻元素两两比较冒泡排序的基本思想一句话概括就是从前往后反复扫描待排序序列每次比较相邻两个元素如果顺序错误就交换每一轮扫描结束后都会有一个元素“冒”到它最终应该在的位置。为什么要叫“冒泡”你可以想象一个杯子里的气泡密度小的气泡会逐渐上升到水面。冒泡排序里大的元素就像气泡一样在一轮轮比较和交换中逐渐“浮”到数组尾部。如果是从小到大排序每一轮结束当前未排序区间的最大值就会被送到最右边。用数组 [64, 34, 25, 12] 举例第一轮扫描过程如下比较 64 和 3464 更大交换数组变为 [34, 64, 25, 12]比较 64 和 2564 更大交换数组变为 [34, 25, 64, 12]比较 64 和 1264 更大交换数组变为 [34, 25, 12, 64]第一轮结束后64 被送到了最后一位这是它的最终位置。下一轮只需要处理前三个元素。这个“每轮缩小一个范围”的规律对应到代码里就是内层循环的终止条件是 n-1-i其中 i 是已经完成的轮数。2.2 两个容易混淆的概念比较与交换冒泡排序有两个动作初学者经常把它们混为一谈。比较comparison指判断两个相邻元素谁大谁小它只读取数据不改变数组交换swap指把两个元素的值互换位置它改变数组的状态。在分析算法效率时比较次数和交换次数是分开统计的。最坏情况下一个长度为 n 的逆序数组冒泡排序的比较次数是 n(n-1)/2交换次数同样是 n(n-1)/2。但最好情况下一个已经有序的数组如果做了优化比较次数是 n-1交换次数是 0。搞清楚比较和交换的区别对后续理解优化很有帮助。优化的本质是在不需要交换的时候减少多余的比较甚至直接终止整个排序。2.3 排序算法的四个评价维度在数据结构课程里评价一个排序算法通常看四个维度时间复杂度、空间复杂度、稳定性、实现复杂度。冒泡排序在这四个维度上的表现可以用下面的表格概括评价维度冒泡排序的表现最坏时间复杂度O(n²)最好时间复杂度O(n)优化后平均时间复杂度O(n²)空间复杂度O(1)原地排序稳定性稳定相等元素不交换位置实现难度低适合入门空间复杂度 O(1) 指的是冒泡排序只需要一个临时变量来完成交换不需要额外的大块内存属于“原地排序”。稳定性指的是如果两个元素值相等排序后它们的相对顺序不会改变。这一点在按关键字多级排序时很重要也是冒泡排序相对选择排序的一个优势。面试或考试中经常出现“稳定排序有哪些”这类问题答案里通常包含冒泡排序、插入排序和归并排序而选择排序不稳定快速排序也不稳定。为什么冒泡排序稳定因为只有当 arr[j] arr[j1] 时才交换等于时不交换所以相等元素的相对位置始终不变。3. 环境准备与前置条件3.1 教材版本与课时定位说明本文围绕选修一《数据与数据结构》5.3 冒泡排序3展开。不同地区使用的教材版本在例题和活动设计上会有差异但冒泡排序的算法结构是通用的。建议读者以学校使用的教材为准本文重点讲清楚算法本身、代码实现和优化思路这部分在任何教材版本下都适用。课程安排上第三节课通常已经有前两节的基础所以本文不会花太多篇幅讲“什么是排序”而是直接进入原理、代码和优化。3.2 编程环境Python 与 C 各准备一套冒泡排序的代码量很小对环境要求极低但为了顺畅地运行和验证结果还是建议准备好以下环境。Python 环境Python 3.8 或更高版本本文示例使用 Python 3 语法。不需要额外安装第三方库标准库足够。推荐使用 VS Code、PyCharm或者直接在 Jupyter Notebook 中运行。C 语言环境GCC 编译器或者 Dev-C、Code::Blocks 等集成环境。如果你使用的是 Windows可以安装 MinGW-w64 或直接使用 Visual Studio 的 C 语言开发环境。如果暂时不想安装本地环境也可以使用在线编译器快速验证代码但不建议长期依赖在线环境因为考试和作业通常需要本机调试。操作系统方面Windows、macOS、Linux 都没有问题本文的命令行示例主要基于通用 shell 语法。如果你所在的学校信息技术课使用 Python 作为主要语言建议优先把 Python 示例跑通如果课程更偏 C 语言或准备参加相关竞赛则可以把 C 示例作为主要练习对象。两种语言的核心逻辑完全一致区别主要在语法细节例如 Python 的多元赋值交换与 C 的临时变量交换。3.3 前置知识清单学习 5.3 冒泡排序3之前建议先确认自己已经掌握以下知识数组的基本操作知道数组下标从 0 开始能够通过下标读取和修改元素for 循环与 range 函数的用法尤其是 range(n-1, -1, -1) 这种倒序写法函数的定义与返回值能够把排序过程封装成函数基本的时间复杂度概念知道 O(n²) 和 O(n) 的含义。如果前面几项还有薄弱的地方建议先回到教材对应章节复习。否则直接在第三节课学编程实现很容易出现“算法思路懂了但代码写不出来”的情况。4. 基础版冒泡排序代码实现与逐轮推演4.1 用 Python 写出第一版冒泡排序先来看最基础、没有任何优化的 Python 实现。建议把这个代码作为“标准模板”记牢因为它结构清晰便于后面在此基础上添加优化。# 文件路径bubble_sort_basic.py def bubble_sort(arr): 基础版冒泡排序从小到大排序 n len(arr) # 外层循环控制轮数一共需要 n-1 轮 for i in range(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] return arr if __name__ __main__: test_arr [64, 34, 25, 12, 22, 11, 90] print(排序前, test_arr) bubble_sort(test_arr) print(排序后, test_arr)这段代码里最需要理解的是两层循环的边界。外层循环 range(n-1) 表示最多执行 n-1 轮为什么是 n-1 而不是 n因为当 n-1 个元素已经放到正确位置后剩下的最后一个元素自然就是正确位置不需要再排。内层循环 range(n-1-i) 表示第 i 轮需要比较 n-1-i 次。当 i0 时比较 n-1 次当 i1 时比较 n-2 次以此类推。这样设计的原因是每一轮结束后数组末尾会多一个已经排好的元素下一轮不需要再碰它。运行这段代码预期输出结果如下排序前 [64, 34, 25, 12, 22, 11, 90] 排序后 [11, 12, 22, 25, 34, 64, 90]4.2 逐轮推演把代码翻译成过程为了不让自己只是“背代码”建议对 [64, 34, 25, 12, 22, 11, 90] 这个输入手动推演每一轮的结果。下面是完整推演。第 1 轮比较 64 和 34交换 → [34, 64, 25, 12, 22, 11, 90]比较 64 和 25交换 → [34, 25, 64, 12, 22, 11, 90]比较 64 和 12交换 → [34, 25, 12, 64, 22, 11, 90]比较 64 和 22交换 → [34, 25, 12, 22, 64, 11, 90]比较 64 和 11交换 → [34, 25, 12, 22, 11, 64, 90]比较 64 和 90不交换 → [34, 25, 12, 22, 11, 64, 90]第 1 轮结束后最大值 90 到达末尾。严格来说 90 本来就在末尾但它在第一轮中参与了最后一次比较所以它的最终位置得到确认。第 2 轮比较 34 和 25交换 → [25, 34, 12, 22, 11, 64, 90]比较 34 和 12交换 → [25, 12, 34, 22, 11, 64, 90]比较 34 和 22交换 → [25, 12, 22, 34, 11, 64, 90]比较 34 和 11交换 → [25, 12, 22, 11, 34, 64, 90]比较 34 和 64不交换 → [25, 12, 22, 11, 34, 64, 90]第 2 轮结束后64 和 90 到达正确位置。注意64 是在这一轮最后一次比较后被确认的。第 3 轮比较 25 和 12交换 → [12, 25, 22, 11, 34, 64, 90]比较 25 和 22交换 → [12, 22, 25, 11, 34, 64, 90]比较 25 和 11交换 → [12, 22, 11, 25, 34, 64, 90]比较 25 和 34不交换 → [12, 22, 11, 25, 34, 64, 90]第 4 轮比较 12 和 22不交换 → [12, 22, 11, 25, 34, 64, 90]比较 22 和 11交换 → [12, 11, 22, 25, 34, 64, 90]比较 22 和 25不交换 → [12, 11, 22, 25, 34, 64, 90]第 5 轮比较 12 和 11交换 → [11, 12, 22, 25, 34, 64, 90]比较 12 和 22不交换 → [11, 12, 22, 25, 34, 64, 90]第 6 轮比较 11 和 12不交换 → [11, 12, 22, 25, 34, 64, 90]整个排序完成。注意第 6 轮只比较了一次而且这一轮没有发生任何交换。这引出一个很重要的观察如果一个轮次里一次交换都没发生说明整个数组已经有序后面继续比较是浪费的。这正是下一节优化的切入点。4.3 C 语言实现临时变量交换的典型写法C 语言没有 Python 的多元赋值语法交换必须借助临时变量。这个写法在几乎所有编程语言里都通用也是考试中经常要求书写的重点。// 文件路径bubble_sort.c #include stdio.h void bubble_sort(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]); printf(排序前); for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); bubble_sort(arr, n); printf(排序后); for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); return 0; }C 版本中有几个细节值得注意。第一函数参数是数组和长度 n数组在 C 语言中作为参数传入时会退化为指针所以必须在外部计算好长度再传入不能在函数内部用 sizeof(arr) 计算完整数组长度。第二交换三行代码的顺序不能乱先用 temp 保存 arr[j]再让 arr[j] 接收 arr[j1]最后把 temp 写回 arr[j1]。如果调换顺序数据就会丢失。第三main 函数中的 n sizeof(arr) / sizeof(arr[0]) 是一段很实用的数组长度计算模板建议记住。编译和运行命令gcc bubble_sort.c -o bubble_sort ./bubble_sort4.4 Java 实现面向对象风格下的排序方法如果你在学 Java冒泡排序通常会写成一个静态方法在主函数中调用。这里给出一个带标志位优化的 Java 版本因为它兼顾了代码简洁性和实际效率。// 文件路径BubbleSort.java public class BubbleSort { 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; } } } 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(); } }对比三种语言的实现可以发现算法逻辑完全一样差异只在语法层。Python 用多元赋值 arr[j], arr[j1] arr[j1], arr[j] 交换C 和 Java 都要写三行临时变量交换。Python 和 Java 有布尔类型可以直接用 swapped 标志位C 语言可以用 int 变量模拟布尔值0 表示假、非 0 表示真。语言交换写法布尔类型典型运行方式Pythonarr[j], arr[j1] arr[j1], arr[j]boolpython bubble_sort_basic.pyC三行 temp 交换int 模拟gcc 编译后运行可执行文件Java三行 temp 交换booleanjavac 编译后运行 class5. 冒泡排序的三种优化策略5.1 优化一用标志位提前结束排序从上面的逐轮推演可以看到第 6 轮只做了一次比较没有任何交换。实际上第 5 轮结束后数组已经完全有序第 6 轮完全没必要执行。优化的思路很直接在每一轮开始前设置一个标志位 swapped False只要在这一轮中发生任何一次交换就把标志位改成 True。每一轮结束时检查标志位如果这一轮完全没有发生交换说明数组已经有序直接 break 退出循环。# 文件路径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 return arr if __name__ __main__: test_arr [11, 12, 22, 25, 34, 64, 90] print(排序前, test_arr) bubble_sort_optimized(test_arr) print(排序后, test_arr)这个版本的改进效果可以通过一个已经有序的数组来体现。输入 [11, 12, 22, 25, 34, 64, 90] 时第一轮从头到尾比较 n-1 次一次交换都没发生swapped 保持 False第一轮结束时立刻 break整个排序只比较了 6 次时间复杂度是 O(n)。最坏情况下例如输入完全逆序的数组每一轮都会发生交换优化标志位永远不会触发 break排序轮数还是 n-1 轮时间复杂度依然是 O(n²)。所以这个优化不改变最坏情况复杂度但大幅提升最好情况下的性能。5.2 优化二记录最后一次交换的位置第二个优化不那么常见但非常巧妙教材进阶内容或竞赛题里偶尔会用到。回顾内层循环的逻辑每一轮从位置 0 比较到 n-1-i。但在很多情况下数组的后半部分可能已经有序真正的“乱序区间”只集中在前半段。例如数组 [1, 3, 2, 4, 5, 6, 7]第一轮扫描后后面的 4、5、6、7 都已经就位下一轮完全不需要再比较它们。如何让程序知道“后半部分已经有序”方法是记录本轮最后一次发生交换的位置。假设本轮扫描到位置 k 时发生了最后一次交换那么位置 k1 到末尾的所有元素都已经有序下一轮只需要扫描到位置 k 即可。# 文件路径bubble_sort_boundary.py def bubble_sort_boundary(arr): 边界优化版冒泡排序记录最后一次交换位置 n len(arr) # last_swap 表示本轮最后一次交换发生的位置 # 初始值为 n-1表示第一轮需要扫描到末尾 last_swap n - 1 while last_swap 0: boundary last_swap # 本轮扫描右边界 last_swap 0 # 重置为 0如果本轮没有交换则循环结束 for j in range(boundary): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] last_swap j 1 return arr这个版本把 for 循环换成了 while 循环。每次进入新一轮先用 boundary 保存当前扫描范围然后把 last_swap 重置为 0。内层循环中一旦发生交换就更新 last_swap 为 j1表示从 j1 往后的区域暂时不需要再扫描。内层循环结束后如果 last_swap 仍然是 0说明这一轮没有任何交换排序结束。对部分有序的数组这个优化能明显减少比较次数。但对完全逆序的数组每一轮的 last_swap 都会是 boundary 本身优化效果和基础版一致。5.3 优化三双向冒泡排序第三个优化是鸡尾酒排序Cocktail Sort也叫双向冒泡排序。它不再只从左到右扫描而是先从左到右把最大值送到末尾再从右到左把最小值送到开头来回交替扫描。为什么这样做能更快考虑数组 [2, 3, 4, 5, 6, 7, 1]基础版冒泡排序需要 6 轮才能把 1 从末尾一路交换到开头因为每轮只能让它向左移动一个位置。如果用双向冒泡排序第一轮从左到右把 7 送到末尾第二轮从右到左扫描时1 可以一路交换到开头相当于扫两轮就完成了大部分工作减少了整体的扫描次数。# 文件路径cocktail_sort.py def cocktail_sort(arr): 双向冒泡排序鸡尾酒排序 n len(arr) left 0 right n - 1 swapped True while swapped: swapped False # 从左到右把最大值送到右侧 for j in range(left, right): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] swapped True right - 1 if not swapped: break # 从右到左把最小值送到左侧 for j in range(right, left, -1): if arr[j - 1] arr[j]: arr[j - 1], arr[j] arr[j], arr[j - 1] swapped True left 1 return arr这个代码有两处细节需要注意。第一从右到左扫描时内层循环用的是 range(right, left, -1)比较的是 arr[j-1] 和 arr[j]方向与从左到右相反。第二每一轮结束后right 减 1、left 加 1相当于两个方向各扫一次后未排序区间两端各缩小一个元素。鸡尾酒排序在最好情况下的时间复杂度同样是 O(n)最坏情况下还是 O(n²)。它通常不是教材 5.3 的必考内容但作为拓展非常值得掌握因为能帮助你理解“扫描方向”这个被基础版忽略的维度。5.4 三种优化策略对比优化方式核心思想最好时间复杂度最坏时间复杂度适用场景标志位优化某轮无交换即结束O(n)O(n²)基本有序的数据边界优化缩小每轮扫描范围O(n)O(n²)部分有序、后半段有序的数据双向冒泡正反交替扫描O(n)O(n²)最小值在末尾等极端分布注意一个容易混淆的点标志位优化和边界优化可以同时使用并不冲突。实际工程或竞赛代码中常见的写法是把标志位优化作为默认版本因为它的代码最简单收益最直观。边界优化则更适合“数组大部分已经有序、只有少数元素错位”的场景。考试中如果题目没有明确要求优化写基础版也不会丢分但如果题目明确问“如何让冒泡排序在最好情况下达到 O(n)”答案就是标志位优化。6. 运行验证与结果分析6.1 统一测试脚本对比四种实现为了验证上面几段代码的正确性建议写一个统一的测试脚本把基础版、标志位优化版、边界优化版、双向冒泡版放在一起用同一组数据测试。# 文件路径test_all_bubble_sorts.py from bubble_sort_basic import bubble_sort from bubble_sort_optimized import bubble_sort_optimized from bubble_sort_boundary import bubble_sort_boundary from cocktail_sort import cocktail_sort test_cases [ [64, 34, 25, 12, 22, 11, 90], [11, 12, 22, 25, 34, 64, 90], [90, 64, 34, 25, 22, 12, 11], [5], [], ] sort_funcs { 基础版: bubble_sort, 标志位优化版: bubble_sort_optimized, 边界优化版: bubble_sort_boundary, 双向冒泡版: cocktail_sort, } for name, func in sort_funcs.items(): print(f {name} ) for case in test_cases: arr case.copy() func(arr) print(arr)预期输出是四组排序函数对所有测试用例的输出完全一致分别是排好序的数组以及原样返回的单元素数组和空数组。这个测试脚本的价值不只是“确认代码能跑”它还能帮助你发现一个常见坑函数是否原地修改了传入的数组。在 Python 中如果直接在函数内部修改传入的列表调用方的列表也会被改变。上面的测试里使用了 case.copy()是为了每次都用原始数据的副本避免前一个函数改坏了数组影响到后面函数的测试结果。实际项目里是否允许原地修改数组取决于你的设计约定如果不想让调用方数据被修改可以在函数入口先复制一份。6.2 统计比较次数与交换次数判断一个排序算法的优劣只看最终结果是不够的还要关注它在排序过程中执行了多少次比较和交换。下面这段代码能够在运行冒泡排序的同时统计这两个指标。# 文件路径count_bubble_sort.py def bubble_sort_with_count(arr): 统计比较次数和交换次数的冒泡排序 n len(arr) compare_count 0 swap_count 0 for i in range(n - 1): swapped False 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 swapped True if not swapped: break return compare_count, swap_count if __name__ __main__: arr1 [64, 34, 25, 12, 22, 11, 90] arr2 [11, 12, 22, 25, 34, 64, 90] c1, s1 bubble_sort_with_count(arr1) c2, s2 bubble_sort_with_count(arr2) print(f乱序数组比较 {c1} 次交换 {s1} 次) print(f有序数组比较 {c2} 次交换 {s2} 次)预期输出大致是乱序数组比较 21 次交换 14 次 有序数组比较 6 次交换 0 次对于乱序数组 [64, 34, 25, 12, 22, 11, 90]完整推演得到 21 次比较和 14 次交换对于已经有序的数组因为标志位优化在第一轮就触发了 break所以只比较 6 次交换 0 次。如果运行结果和这个数字对不上优先检查内层循环边界是否写成了 n-1 而不是 n-1-i。这个统计功能在考试复习中很有用你可以用它验证自己对任意输入的推演是否正确。7. 常见错误与排查思路7.1 内层循环边界写错这是冒泡排序出现频率最高的错误。常见写法是 for j in range(n-1) 而不是 for j in range(n-1-i)。如果内层循环不减去 i每一轮都会扫描整个数组包括已经被送到末尾的已排序元素。排序结果通常还是对的因为已排序区域的相邻元素不会再交换但会多做大量无意义的比较比较次数从 n(n-1)/2 变成 n(n-1)在 n 比较大的时候性能差异非常明显。更隐蔽的错误是写成 for j in range(n)当 j 等于 n-1 时访问 arr[j1] 就会越界。Python 会抛出 IndexErrorC 语言则是未定义行为可能读到未知内存。排查方式先看内层循环的 range 上界再看数组访问的下标。记住一个口诀有 n 个元素相邻比较最多 n-1 次第 i 轮要排除末尾 i 个元素所以是 n-1-i。7.2 交换逻辑写错Python 写多了之后很多人会忘记其他语言没有多元赋值。在 C 语言中交换必须借助临时变量顺序必须是先把 arr[j] 存到 temp再把 arr[j1] 赋给 arr[j]最后把 temp 赋给 arr[j1]。如果写成 arr[j] arr[j1] 在前arr[j] 的原始值就会丢失。初学者最常见的错误代码是直接两句赋值缺少临时变量运行后两个位置的值完全相同原数组数据直接丢失。排查时先看交换语句是否包含三行逻辑保存、赋值、回写或者是否声明了临时变量。// 错误示例缺少临时变量的交换 arr[j] arr[j 1]; arr[j 1] arr[j]; // 两个位置都变成了 arr[j1] 的值7.3 是否无意中修改了原数组Python 的列表是可变对象函数内直接修改 arr 会影响到调用方。如果业务逻辑希望保留原始数据必须在函数入口复制arr arr[:] 或 arr arr.copy()。这一点在考试里一般不考但在实际项目中很重要。例如你写了一个排序函数调用后原始数据的顺序被改变可能会导致后续逻辑出错。设计函数时要么明确规定“本函数会原地修改数组”要么在文档注释里写清楚返回值避免调用方产生误解。7.4 稳定性被破坏冒泡排序本身是稳定排序但如果代码里把 if arr[j] arr[j1] 写成 if arr[j] arr[j1]相等元素也会交换稳定性就被破坏了。对于纯数值排序这一点看不出来但对包含多条字段的对象排序稳定性差异会直接影响结果。例如你有一组学生记录先按学号排序再按成绩排序如果第二次排序不稳定学号的相对顺序就可能被打乱。排查稳定性问题时可以用一组包含重复元素的输入在排序前后记录相同元素的相对位置是否发生变化。问题现象可能原因排查方式解决方案Python 抛 IndexError内层循环 range(n) 越界访问查看报错行和数组长度改为 range(n-1-i)C 程序输出乱码或崩溃交换缺少临时变量检查交换语句是否为三行使用 temp 中间变量排序结果正确但很慢内层循环没有减 i统计比较次数边界改为 n-1-i调用方数组被改变函数内原地修改列表打印函数调用前后数据入口处复制数组排序不稳定判断条件用了 用重复元素测试改为 8. 教材与考试视角怎么考、怎么答8.1 选择题比较次数与交换次数考试中最常见的题型是给定一个长度为 n 的数组问冒泡排序在最坏情况下需要比较多少次答案是 n(n-1)/2。如果题目给定具体的数组并要求写出“第一轮排序后数组的状态”则必须在草稿纸上模拟一次完整扫描注意题目问的是“一轮”还是“一次”。这类题目的得分关键是看清楚问的是第几轮。第 1 轮结束后最大值到达末尾第 2 轮结束后次大值到达倒数第二位。如果题目问“第 k 轮排序后数组末尾的 k 个元素分别是什么”答案就是最大的 k 个数按从小到大排列因为它们按轮次依次确定。8.2 填空题补全算法代码另一种常见题型是给出一段冒泡排序代码把内层循环条件、交换语句挖成空让考生填写。这要求对代码结构非常熟悉而不是只会“读懂”。建议把基础版代码背下来特别是几个关键点外层循环是 range(n-1)内层循环是 range(n-1-i)判断条件是 arr[j] arr[j1]等号必须注意交换可以用 Python 多元赋值也可以写成三行临时变量交换优化版需要在每轮开始初始化 swapped False交换时置 True轮末判断。这些点几乎就是填空题的所有考点。8.3 操作题手工模拟排序过程手工模拟冒泡排序是选修一最常见的操作题没有捷径只能逐轮逐次推演。但有一个技巧可以减少出错每轮推演时用一个竖线把“已排序区域”和“未排序区域”分开。例如初始 [64 34 25 12 22 11 | 90] 第一轮后 [34 25 12 22 11 | 64 90]注意在这个示例里90 虽然不是通过交换到达末尾的但它原本就在末尾所以第一轮之后末尾的“已排序区域”实际上包含 64 和 90 两个元素。很多同学在这里会漏算把 90 也当成还要参与下一轮排序的元素导致后面的推演全错。判断一个元素是否已经就位的标准是“它是否已经是当前未排序区间的最大值”而不是“它这一轮是否发生了交换”。8.4 与插入排序、选择排序的对比教材第五章通常会同时讲冒泡排序、选择排序和插入排序考试也喜欢考三者对比。排序算法基本思想最好时间复杂度最坏时间复杂度稳定性是否原地冒泡排序相邻比较交换O(n)O(n²)稳定是选择排序每轮选最小值O(n²)O(n²)不稳定是插入排序逐个插入有序区O(n)O(n²)稳定是选择排序为什么不稳定因为它会“跨位置”交换可能把相同元素的相对顺序打乱。冒泡排序只在相邻元素之间交换且严格大于才交换所以稳定。如果题目问“需要一个稳定的、代码简单的排序算法”冒泡和插入都是合格答案如果问“最坏情况下比较次数固定的是谁”选择排序的比较次数固定为 n(n-1)/2而冒泡和插入在最好情况下可以减少但在最坏情况下同样是 n(n-1)/2。这张对比表建议抄在笔记本上考试前重点复习。9. 总结与下一步学习建议这篇文章围绕选修一《数据与数据结构》5.3 冒泡排序3做了完整梳理。核心内容可以浓缩成四句话冒泡排序是相邻元素两两比较、按轮次把最大值“冒”到末尾的排序算法代码结构是两层循环加一个交换内层循环边界是 n-1-i这是最容易出错的地方也是考试填空题的高频考点通过标志位、边界位置、双向扫描三种方式可以对冒泡排序进行优化其中标志位优化让最好情况复杂度达到 O(n)验证排序算法不能只看最终结果还要观察每轮状态、比较次数和交换次数。如果你正在学习选修一建议按这个顺序练习先手工模拟三组不同的数据每组至少 6 个元素把每一轮结果写清楚再照着基础版代码打一遍运行成功后再把代码背写出来不看样例然后实现标志位优化版用有序数组验证是否只比较 n-1 次就结束最后尝试给排序过程加计数功能手动对比“乱序数组”和“有序数组”的比较次数差异。如果你是为了面试或竞赛复习冒泡排序本身通常不会作为最终答案出现但它经常被用来考察基础代码能力面试官可能让你手写并分析复杂度也可能追问如何优化掌握本文的三种优化已经能覆盖绝大多数追问。下一步可以接着学习插入排序和选择排序把三种 O(n²) 排序放在一起对比再往后可以学习更高效的快速排序和归并排序理解“分治”思想如何把复杂度降到 O(n log n)。排序是数据结构里最值得深挖的主题之一因为几乎所有后续算法和数据处理场景都会用到它。建议把这篇文章收藏起来等学到第五章后半部分再回来对照复习。