如果你正在准备高中信息技术选修一《数据与数据结构》或者刚接触算法那么冒泡排序大概率是你遇到的第一个“真正意义”上的排序算法。这一节不讲花哨内容重点就是把冒泡排序的每一轮比较、交换、边界条件彻底拆开让你能在纸上手写、在机器上跑通也能用 C、C 语言或 Python 复现它。这篇文章会给出一套可以直接照着做的学习路径先看懂原理再写代码再跑测试最后做优化和排错。内容密度会比较高建议收藏备用。1. 本节核心知识速览知识点说明算法名称冒泡排序Bubble Sort所属章节选修一《数据与数据结构》5.3 冒泡排序1核心操作相邻元素两两比较逆序则交换位置典型实现语言Python、C、C、Java排序方向从小到大升序或从大到小降序是否稳定稳定排序相同值元素不会发生相对位置变化时间复杂度最坏 O(n^2)最好 O(n)平均 O(n^2)空间复杂度O(1)原地排序不需要额外数组数据结构基础一维数组顺序表遍历、下标访问、元素交换适合学习阶段高中信息技术、数据与数据结构课程入门、编程初学者从课程安排来看这一节“冒泡排序1”通常只要求掌握冒泡排序的基本思想、手工模拟排序过程和简单代码实现不涉及复杂优化但作为技术博客我会把后续常见的优化思路和踩坑点也放进来方便你学完基础后继续深挖。2. 冒泡排序的基本原理2.1 排序问题是什么先明确一个基础问题排序就是把一组无序数据按照某个规则重新排列。比如下面这个数组[64, 34, 25, 12, 22, 11, 90]升序排序后的结果是[11, 12, 22, 25, 34, 64, 90]在数据结构里这个数组可以看成顺序表的一维存储形式数组下标从 0 开始长度为 7。冒泡排序要做的事情就是通过多次扫描这个数组把最大的元素“冒泡”到数组末尾最终得到有序序列。2.2 “冒泡”的直观理解冒泡排序的名字来源于一个现象值较大的元素会像气泡一样逐渐向上向后移动值较小的元素会慢慢向前移。在一轮排序中算法从数组的第一个位置开始依次比较相邻的两个元素如果前一个元素比后一个元素大就交换它们。如果前一个元素不大于后一个元素就保持不变。然后继续比较下一对相邻元素。每比较一次较大的值会向右移动一位。经过一轮完整的扫描当前未排序区间里的最大值一定被移动到了数组的最后。下一轮排序时就不需要再考虑这个已经就位的最大值。2.3 一轮排序的例子用数组[64, 34, 25, 12, 22, 11, 90]来演示第一轮。第一轮开始比较次数比较的元素是否交换交换后数组第 1 次64 和 34是[34, 64, 25, 12, 22, 11, 90]第 2 次64 和 25是[34, 25, 64, 12, 22, 11, 90]第 3 次64 和 12是[34, 25, 12, 64, 22, 11, 90]第 4 次64 和 22是[34, 25, 12, 22, 64, 11, 90]第 5 次64 和 11是[34, 25, 12, 22, 11, 64, 90]第 6 次64 和 90否[34, 25, 12, 22, 11, 64, 90]第一轮结束后最大值 90 已经在数组末尾。接下来再对前 6 个元素重复同样操作第二轮会把 64 移动到倒数第二个位置。依次类推直到所有元素有序。这里有一个容易忽略的细节第一轮一共比较了 6 次而不是 7 次。数组长度为 n 时每一轮最多比较 n-1 次因为最后一个元素不需要和自己比较。3. 冒泡排序的代码实现学习排序算法最好是先能手动模拟再看代码最后自己写一遍。下面给出 Python、C、C 三种语言的实现。Python 适合快速验证算法逻辑C/C 适合理解数组和内存操作。3.1 Python 实现def bubble_sort(arr): n len(arr) # 外层循环控制排序轮数最多 n-1 轮 for i in range(n - 1): # 内层循环控制每一轮的相邻比较 # n - 1 - 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] bubble_sort(test_arr) print(排序结果, test_arr)运行上面的代码控制台会输出排序结果 [11, 12, 22, 25, 34, 64, 90]这段代码里最关键的是内层循环的范围range(n - 1 - i)。第一次外层循环时i0内层循环要访问arr[j]和arr[j1]j最大取到n-2正好能访问到最后一个元素arr[n-1]。第二次外层循环时i1最后一对比较的是arr[n-3]和arr[n-2]已经排好的arr[n-1]不参与。如果这里把范围写错很容易出现数组越界。3.2 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]); bubble_sort(arr, n); for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); return 0; }用 C 语言写冒泡排序交换部分需要借助一个临时变量temp。这一点在课程考试和上机练习中经常被考到尤其是不能直接写arr[j] arr[j1]否则会把原来的值覆盖掉。3.3 C 实现#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]) { swap(arr[j], arr[j 1]); } } } } int main() { int arr[] {64, 34, 25, 12, 22, 11, 90}; int n sizeof(arr) / sizeof(arr[0]); bubbleSort(arr, n); for (int i 0; i n; i) { cout arr[i] ; } cout endl; return 0; }C 标准库里的swap函数可以简化交换代码原理和 C 语言里的临时变量交换一致。如果学习环境不支持 C 11也可以在头文件里包含algorithm。3.4 Java 实现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}; bubbleSort(arr); for (int num : arr) { System.out.print(num ); } } }四种语言的实现思路完全一样区别只在语法细节。建议你至少用两种语言各写一遍这样能更好地区分“算法思想”和“语言语法”两个层面。4. 手工模拟与边界条件4.1 为什么外层循环是 n-1 次一个长度为 n 的数组如果每次都有元素“冒泡”到正确位置那么排序 n-1 轮后前 n-1 个元素已经就位第 n 个元素自然也就在正确位置。所以外层循环只需要执行 n-1 次。用[5, 1, 2, 3, 4]这个“大部分有序”的数组来观察第一轮结束后数组为[1, 2, 3, 4, 5]。按照最外层循环n-1 4次的标准算法还会继续扫描三遍但这三遍里没有发生任何交换。这就是后续内容里“加标志位提前结束”优化可以发挥作用的地方。4.2 内层循环为什么是 n-1-i每一轮结束后数组末尾会多出一个已经排好序的元素。例如第一轮结束后最大值确定在arr[n-1]第二轮不需要再去比较包含arr[n-1]的相邻对。如果内层循环写成for (int j 0; j n - 1; j)虽然不会导致结果错误因为已经排好的元素不会再被交换但会白白做一些无意义的比较。在数据量较大时这种多余比较会拖慢程序。4.3 数组越界问题一个初学者高频错误是for (int j 0; j n - i; j) { if (arr[j] arr[j 1]) { swap(arr[j], arr[j 1]); } }当i0、jn-1时arr[j1]就是arr[n]已经超出数组范围。在 C/C 中这种越界不一定会立刻崩溃但它属于未定义行为可能导致数据被意外修改。严格写法是j n - 1 - i。5. 运行测试与结果验证写完之后需要测试不能只靠“看起来对”。下面是一套适合课堂和自学的验证思路。5.1 单调递增数组测试输入[1, 2, 3, 4, 5]。这个用例本身已经有序冒泡排序仍然会执行 n-1 轮但在没有任何交换的轮次里代码依然会比较每一对相邻元素。预期输出还是[1, 2, 3, 4, 5]。5.2 单调递减数组测试输入[5, 4, 3, 2, 1]。这是冒泡排序最不利的情况。每轮比较都会发生交换第一轮后变成[4, 3, 2, 1, 5]第二轮后变成[3, 2, 1, 4, 5]直到最终变成[1, 2, 3, 4, 5]。这个测试能直观看到“逆序数组”下的交换次数。5.3 含有重复元素的数组测试输入[3, 1, 2, 3, 1]。预期输出为[1, 1, 2, 3, 3]。这里还要注意稳定性因为代码只在arr[j] arr[j1]时才交换遇到相等元素不会交换位置所以两个 3 的相对顺序保持原样。对于不要求稳定性的排序这点可能不重要但课程里经常会问。5.4 空数组和单元素数组测试输入[]或[1]。冒泡排序对这两种输入都能直接返回原数组因为它们天然有序。写代码时要注意len(arr)为 0 或 1 时外层循环不会执行或只执行 0 次不能出现数组越界。5.5 测试辅助代码可以用下面的 Python 代码批量检查排序结果def is_sorted(arr): for i in range(len(arr) - 1): if arr[i] arr[i 1]: return False return True test_cases [ [1, 2, 3, 4, 5], [5, 4, 3, 2, 1], [3, 1, 2, 3, 1], [], [1], [64, 34, 25, 12, 22, 11, 90], ] for arr in test_cases: bubble_sort(arr) print(arr, is_sorted(arr))如果所有输出都满足is_sorted返回True说明这一段代码在基本功能上没有问题。不过输出有序只能证明“能排序”还需要确认排序是否稳定、是否有多余比较这些就要结合代码逻辑和优化点来分析了。6. 时间复杂度与空间复杂度6.1 比较次数冒泡排序比较次数与数据规模 n 有关。最坏情况下每一轮都要比较 n-1 次一共 n-1 轮总比较次数为(n-1) (n-2) ... 1 n(n-1)/2所以最坏时间复杂度是 O(n^2)。最好情况是数组已经有序但仍然会执行 n-1 轮扫描每轮比较 n-1-i 次总比较次数仍然是 n(n-1)/2。如果加了“某一轮无交换就提前结束”的优化最好情况下只需要扫描一轮比较 n-1 次时间复杂度降到 O(n)。6.2 交换次数交换次数取决于逆序对的数量。最坏情况下数组完全逆序每次比较都需要交换交换次数也是 n(n-1)/2 数量级。最好情况下不需要交换。6.3 空间复杂度冒泡排序只使用常数个额外变量比如临时变量属于原地排序空间复杂度 O(1)。这一点在和其他排序算法对比时很重要比如归并排序需要 O(n) 的辅助空间。6.4 对课程学习的意义学时间复杂度不是单纯记公式而是要学会从代码结构观察。冒泡排序是嵌套循环结构外层循环和内层循环的规模都和 n 相关所以很容易看出 O(n^2)。如果以后学了快速排序、归并排序可以用同样的“嵌套层数 数据规模”方式来估算复杂度。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这个优化对“接近有序”的数据效果非常明显。课程中如果要求“将数组排序并输出比较轮数”可以用这个标志位来统计。7.2 记录最后一次交换位置另一种优化是记录本轮最后一次发生交换的位置。最后一次交换之后的位置在下一轮扫描时不需要再参与比较因为它右边的元素已经有序。def bubble_sort_last_swap(arr): n len(arr) last_exchange n - 1 while last_exchange 0: last 0 for j in range(last_exchange): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] last j last_exchange last相比“标志位优化”这种写法在重复元素较多、部分有序的情况下可以减少无效扫描。7.3 鸡尾酒排序鸡尾酒排序双向冒泡排序是指先从左往右扫描再从右往左扫描交替进行。它可以在某些数据 pattern 下减少排序轮数比如序列[2, 3, 4, 5, 1]单向冒泡需要多轮而双向冒泡可以更快把 1 移到最前面。这个属于拓展内容课程基础阶段不需要掌握但感兴趣的话可以自己实现。def cocktail_sort(arr): n len(arr) start 0 end n - 1 swapped True while swapped: swapped False for i in range(start, end): if arr[i] arr[i 1]: arr[i], arr[i 1] arr[i 1], arr[i] swapped True end - 1 if not swapped: break swapped False for i in range(end, start, -1): if arr[i] arr[i - 1]: arr[i], arr[i - 1] arr[i - 1], arr[i] swapped True start 18. 常见错误与调试方法8.1 循环边界写错导致越界错误代码示例问题正确写法for j in range(n - i)最后一轮访问到arr[n]for j in range(n - 1 - i)for j in range(n - 1)不会越界但存在多余比较for j in range(n - 1 - i)排查方法在循环里打印j的最大值和j1的值观察是否超过数组长度。8.2 交换逻辑写错导致数据丢失# 错误示例 arr[j] arr[j 1] arr[j 1] arr[j]这段代码执行后arr[j]的新值已经覆盖了旧值下一步再赋给arr[j1]时两个元素会变成同一个数。Python 中可以使用多重赋值C/C/Java 中必须使用临时变量。8.3 比较方向写反如果代码写的是if (arr[j] arr[j 1])那么排序结果是降序不是升序。做题时要看清题目要求是从小到大还是从大到小。8.4 没有处理边界输入空数组和单元素数组虽然不会出错但如果你在外层循环前用arr[1]之类的方式初始化变量就可能越界。建议先把边界输入写进测试用例。8.5 调试方法在每一轮结束后打印数组观察数据变化是否符合预期。只对 4 到 5 个元素的小数组测试方便手工模拟对照。用断点调试观察每一轮比较的i、j下标。如果结果不对先怀疑比较方向再怀疑交换逻辑最后检查循环范围。9. 冒泡排序与数据结构的衔接冒泡排序不是一个孤立的算法它在课程中承担着“数组遍历 元素交换 算法设计”入门教学任务。首先是数组遍历。冒泡排序体现了典型的线性表顺序访问方式内层循环通过下标j访问相邻元素。如果没有理解数组是一段连续存储空间就很难理解为什么arr[j]和arr[j1]是相邻元素。其次是元素交换。这个操作在后续很多算法中都会用到比如选择排序、快速排序分区。交换可以通过临时变量实现也可以利用数学运算不推荐或语言自带函数但基本思路是一致的。再次是算法稳定性。在后续学习更复杂的排序算法时稳定性会影响多关键字排序。冒泡排序因为只在严格大于时才交换所以是稳定排序。这一点在考试判断题和填空题里经常出现。最后是复杂度分析启蒙。很多初学者第一次接触时间复杂度就是从冒泡排序开始的。可以这样观察当 n 从 10 变成 100 时冒泡排序的最坏比较次数从 45 变成 4950增长远快于线性增长这直观说明了 O(n^2) 的含义。10. 课堂练习与作业建议本节如果作为课程作业建议按照以下顺序完成手写模拟给一个包含 6 个整数的无序数组写出每一轮冒泡排序后的数组状态。代码实现用 Python 或 C 完成升序冒泡排序并添加注释。输出验证在每一轮结束后打印当前数组验证和手写结果一致。改写降序把比较条件从改成重新运行测试。加入标志位优化统计没有交换时的提前退出情况。扩展题用冒泡排序对字符串数组按字典序排序。以数组[7, 2, 9, 1, 5]为例第一轮结束后的中间状态是[2, 7, 1, 5, 9]第二轮结束后是[2, 1, 5, 7, 9]第三轮结束后是[1, 2, 5, 7, 9]。你可以自己手算之后再用代码验证如果某个位置对不上大概率是交换逻辑或者循环边界出了问题。11. 冒泡排序学习自测清单自测项是否掌握能说明第一轮排序后最大值为什么在最右边是 / 否能写出内层循环range(n - 1 - i)的理由是 / 否能用手工模拟 5 个元素的逆序数组排序全过程是 / 否能用 Python 和 C 分别完成基础实现是 / 否能解释冒泡排序是稳定排序是 / 否能说出最好、最坏时间复杂度是 / 否能说出“标志位优化”的原理是 / 否能在不加调试器的情况下通过代码自查越界问题是 / 否通过这张表你可以快速判断自己是否达到了《数据与数据结构》5.3 冒泡排序1的基本要求。如果有一两项没掌握建议回到第 4 节和第 8 节重新看一遍代码和错误案例再动手写一遍。排序算法看十遍不如自己写一遍特别是循环边界这种细节只有在编译器或运行结果暴露问题时才会真正记住。