聊到排序冒泡排序几乎是绕不开的第一个算法。它简单到让人觉得“就这”但实际写起来尤其是亲手调试的时候才体会到什么叫“一看就会一写就废”。对我来说这个算法是块很好的试金石——它不考验智力考验的是你有没有真正理解循环边界和变量交换也是后端、前端、嵌入式等方向面试时都爱问的基础题。这篇文章我准备从核心思想讲到三种主流语言的写法再到优化思路和新手必踩的坑最后把冒泡排序和选择排序放在一起掰扯清楚。刚学编程的朋友可以把它当入门教程写过几段代码的老哥也能看看优化和排查部分保证有收获。1. 冒泡排序到底在干什么1.1 一句话搞懂核心思路冒泡排序的思路就一句话重复地遍历数组依次比较相邻的两个元素如果顺序错了就交换直到整个数组有序。每次遍历的时候较大的元素会一点一点地往后“挪”就像水里的气泡往上升一样所以叫“冒泡排序”。每一轮遍历结束总有一个数会被推到它最终该待的位置——这个数就是当前未排序区间里的最大值。这里面最要紧的动作是“相邻比较”。它不是让某个元素去和其他所有元素比而是始终比较arr[j]和arr[j1]这种紧挨着的两个数。正是这一条决定了冒泡排序是稳定排序也决定了它每一趟能把一个最大值送到末尾。1.2 用排队的故事把算法“演”一遍想象有一队人站成一排老师要求按身高从矮到高排好。你从队伍最左端开始先看第一个人和第二个人如果左边比右边高就让两个人交换位置接着看第二个人和第三个人同样地左边高就交换。这样一路看下去走到队伍末尾时你会发现最高那个人已经被“顶”到了最后面就像气泡浮到了顶。第一趟结束你成功把全班最高的人放到了最后的位置这个位置就再也不需要动了。第二趟只需要处理前 n-1 个人同样的方法第二高的人会被放到倒数第二个位置。如此反复总共需要 n-1 趟最后一趟只剩一个人不用再比队伍就排好了。这个故事里藏着两个关键点为什么是 n-1 趟以及为什么内层比较次数是 n-1-i。这两个问题想明白了冒泡排序你就真懂了。1.3 为什么说它的名字起得很形象“冒泡”这个叫法特别贴切。你去看每一趟的比较过程越小的元素会越过它前面的大元素一点一点地向前移动。那种在数组里往前“飘”的感觉和气泡从水底升起来几乎一模一样。还有个说法也很有意思如果从最终结果往回看每一趟结束最大的数都准确地落到了它该待的位置像一颗石子沉到水底。但算法里元素确实是在“冒”到顶部所以大家还是习惯叫冒泡。理解这个名字你就会记住它的行为特征每趟选出一个当前范围内最大或最小的元素放到正确的一端。2. 三种主流语言实现与对比2.1 C语言版数组与指针的经典配合C语言版本是最朴素、也最能看清冒泡排序本质的实现。因为没有现成的交换函数你手写 temp 交换逻辑反而能加深对“值传递”的理解。#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]); } return 0; }这里有几个细节值得停下来看。外层i从 0 到n-2正好是 n-1 趟因为最后一趟只剩一个元素时不需要比较。内层j从 0 到n-2-i是因为每一趟结束后数组末尾的 i1 个元素已经排好不需要再碰它们。你要是把内层条件写成j n - i当 i 为 0 时 j 可以取到 n-1访问arr[j1]就等于访问arr[n]越界程序直接崩溃。2.2 C版模板和标准库让代码更通用C 里可以玩得更花一点。用模板把类型抽象出来函数既能排 int 数组也能排 double、float甚至自定义结构体需要重载比较运算符。#include iostream #include vector #include algorithm // for std::swap template typename T void bubble_sort(std::vectorT arr) { int n static_castint(arr.size()); for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { std::swap(arr[j], arr[j 1]); } } } } int main() { std::vectorint arr {64, 34, 25, 12, 22, 11, 90}; bubble_sort(arr); for (int x : arr) { std::cout x ; } return 0; }用std::swap的好处是不用自己写 temp 逻辑代码更短也不容易漏掉中间的赋值步骤。但注意std::swap对复杂类型可能涉及移动或拷贝开销不一定比手写小只是在这种入门场景里完全不用纠结。2.3 Java版方法与数组对象的封装Java 版本在思路上和 C 完全一样区别在于 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 ); } } }Java 里因为没有给基本类型数组提供现成的 swap 方法所以还是手写三行交换。也不要想着用Arrays.sort代替那就不是冒泡排序了。这三个版本你只要吃透一个其他语言基本就是换皮逻辑骨架完全一致。对比项C语言CJava数组处理数组长度参数vector容器模板数组对象交换方式手写temp三行std::swap手写temp三行适用类型仅对应类型通用类型仅对应类型典型场景嵌入式/底层算法竞赛/工程后端业务/刷题3. 从能用走向好用三种经典优化3.1 提前结束没有交换就收工原始版本的冒泡排序有一个明显的问题即使数组本来就有序它照样兢兢业业地比较 n(n-1)/2 次。比如[1, 2, 3, 4, 5]第一趟从头比到尾一次交换都没发生这时候就可以断定数组已经有序直接退出。优化方法就是加一个标志位swapped。每一趟开始时置为 false只要发生任何一次交换就置为 true。一趟结束后检查这个标志如果还是 false说明整趟下来没有需要调整的元素后面也不需要再比了。void bubble_sort_early_exit(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; } } }这个优化效果非常直观最好情况下一开始就发现有序时间复杂度从 O(n^2) 直接降到 O(n)。实际开发中如果数据本身有序或接近有序这个标志位能省下大量无效比较。3.2 记录最后一次交换的位置缩小扫描范围第二个优化稍微进阶一点。每一趟内层循环结束之前最后一次发生交换的位置lastSwap之后的元素其实已经全部有序了。下一趟循环完全不用扫描到 n-1-i只需要扫到lastSwap就行了。void bubble_sort_tail_mark(int arr[], int n) { int lastSwap n - 1; while (lastSwap 0) { int currentSwap 0; for (int j 0; j lastSwap; j) { if (arr[j] arr[j 1]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; currentSwap j; } } lastSwap currentSwap; } }这里currentSwap记录的不是交换次数而是最后一次交换发生时 j 的位置。下一趟只需要遍历到这个位置它之后的部分已经确定有序。对于“数组后面大半已经有序”这类情况这个技巧能省一半甚至更多的比较次数。3.3 鸡尾酒排序双向冒泡效率翻倍鸡尾酒排序也叫双向冒泡排序思路是一趟从左往右把最大值送到末尾下一趟从右往左把最小值送到开头来回交替像调鸡尾酒一样。void cocktail_sort(int arr[], int n) { int left 0; int right n - 1; while (left right) { for (int i left; i right; i) { if (arr[i] arr[i 1]) { int temp arr[i]; arr[i] arr[i 1]; arr[i 1] temp; } } right--; for (int i right; i left; i--) { if (arr[i - 1] arr[i]) { int temp arr[i - 1]; arr[i - 1] arr[i]; arr[i] temp; } } left; } }这种写法在“大部分元素有序只有少数几个元素待归位”的场景里优势特别明显。举个例子[2, 3, 4, 5, 1]普通冒泡需要把 1 从最左边一路换到最右边过程非常漫长鸡尾酒排序在第二趟回扫时就能把 1 快速带到最前面。不过它仍然处理不了真正的乱序数组复杂度还是 O(n^2)只是常数因子小了一些。4. 冒泡排序和选择排序怎么选4.1 两者核心差异在“交换”选择排序的思路和冒泡完全不同每一趟扫描未排序区间找到最小值所在的下标一趟结束后只交换一次把这个最小值放到正确的位置。它不进行大量的相邻交换而是记录位置最后统一换。这个差异在数据规模变大时体现得很明显。假设有 n 个数冒泡排序最坏情况下要做 n(n-1)/2 次交换选择排序不管数据多乱每一趟最多交换一次总共最多 n-1 次交换。如果数组里的元素是大型结构体一次交换的代价可能是拷贝几百字节的数据这时候选择排序的优势就出来了。4.2 稳定性到底差在哪选择排序有一个致命的问题它是不稳定的。原因在于它做的是“跳跃式交换”——把最小值直接换到前面可能会把两个相等元素的相对顺序打乱。比如数组[3a, 3b, 1]选择排序会把 1 换到最前面那 3a 和 3b 谁在前面就取决于实现细节大概率变成[1, 3b, 3a]原来 3a 在 3b 前面的相对顺序被破坏了。冒泡排序只交换相邻元素相等的元素不会被交换所以能保持原来的相对顺序是稳定的排序算法。如果你后续还要按其他字段排序稳定性就很重要。比如先按姓名排序再按年龄排序稳定的排序可以保证年龄相同的人仍然按姓名排列。4.3 实际开发中该怎么选说了这么多理论落到实际中我就给大家一个可以直接抄作业的结论元素数量小于 100 甚至几十两者性能差异肉眼感觉不到选哪个全看你更熟悉哪个。元素是大型结构体一次赋值开销很大优先选选择排序因为它交换次数少。需要保持相等元素的相对顺序有多个排序字段需求选冒泡。数据几乎有序用加了提前退出优化的冒泡效果远超选择排序。数据量一旦到千级、万级这两个都不太行了直接上快排、归并这类更高效的排序。对比维度冒泡排序选择排序平均时间复杂度O(n^2)O(n^2)最好时间复杂度O(n)优化后O(n^2)最坏时间复杂度O(n^2)O(n^2)空间复杂度O(1)O(1)交换次数最多 n(n-1)/2最多 n-1稳定性稳定不稳定实现难度极简简单5. 新手最容易踩的坑与排查实录5.1 数组越界是最狠的一刀冒泡排序里的越界问题几乎都出在内层循环的边界上。我见过最典型的写法是for (int j 0; j n - i; j)然后循环体里写if (arr[j] arr[j1])。当 i0 时j 最大能取到 n-1arr[j1]就是arr[n]直接越界。C 语言对越界访问往往不会直接报错而是读到一块未知内存数值千奇百怪结果排序乱得毫无规律。更可怕的是如果越界的那块内存恰好在写操作范围内你可能会悄悄把别的变量改掉。调试这种问题不如直接从根上记住外层 i 次数是 n-1内层 j 终点是 n-1-i多一个都不行。5.2 比较符号写反排序顺序全反如果你想要升序应该是if (arr[j] arr[j1])才交换也就是“左边比右边大就换”。很多人紧张的时候会写成结果变成“左边比右边小就换”一趟跑完数组从升序变成了降序而且程序完全正常、不报错特别难排查。减少符号错误的技巧是先把需求用中文说出来“把大的往后挪”然后翻译成代码就是arr[j] arr[j1]时交换。你要是搞不清降序怎么写就反过来想“把小的往后挪”那条件就是arr[j] arr[j1]。5.3 死循环的出入口控制while 版本比 for 版本更容易写出死循环。比如有人想用while (i n-1)控制外层循环却忘了让 i 自增或者内层用 while 控制 j忘记在循环体末尾更新 j。遇到这种情况程序就会一直停在原地交换同一对元素CPU 直接拉满风扇狂转。我排查死循环的思路是先看循环变量有没有向退出条件推进的变化再看退出条件是不是永远为真。在冒泡排序的场景中i和j必须按预期自增n不能在中途被修改。最好的预防办法是尽量用 for 循环把循环变量的初始化、条件判断、自增写在同一个地方不容易漏。5.4 空数组和单元素数组很多新手写的排序函数丢进空数组或者只有一个元素的数组就直接崩了。原因是代码里没做长度判断n - 1可能变成负值循环直接进入奇怪的状态。if (n 1) { return; }像这样的防御性判断放在函数开头几毫秒的性能损失可以忽略不计但能避免大量边界问题。这也是工程代码和练习代码的区别工程代码里你永远要假设输入可能是任何离谱的数据。5.5 常见错误速查表为了方便大家排查我把实际辅导过程中遇到的高频问题整理成了表格按出现频率排序症状可能原因处理方式排序后结果乱序内层循环越界访问检查j n - 1 - i输出为降序比较符号写反换成arr[j] arr[j1]数组没变交换逻辑忘记写检查有没有 temp 三行交换程序卡死不动while 循环变量未更新改用 for 循环空数组崩溃缺少长度判断开头加if (n 1) return重复元素顺序变了用了统一改成6. 复杂度分析与适用边界6.1 时间复杂度是怎么算出来的冒泡排序的时间复杂度推导非常直观不需要高等数学。外层循环跑 n-1 趟第一趟内层比较 n-1 次第二趟 n-2 次第三趟 n-3 次……最后一趟 1 次。总的比较次数就是(n-1) (n-2) ... 1这是一个等差数列求和结果是n(n-1)/2。当 n 足够大时n(n-1)/2约等于n^2/2所以时间复杂度为 O(n^2)。最坏的情况是完全逆序的数组每一趟每一次比较都需要交换比较次数和交换次数都是 n(n-1)/2最好的情况是数组已经有序优化版本只需要 n-1 次比较就能结束时间复杂度降到 O(n)。空间复杂度是 O(1)因为整个排序过程只用了 temp 这一个额外变量原地完成排序不随 n 增长而增长。6.2 稳定性为什么是它的王牌属性前面提到过冒泡排序是稳定排序。这里我想补充一个细节稳定性不是所有排序都有的快排、选择排序都不稳定归并排序稳定但实现复杂。在很多真实业务里比如订单先按金额排序再按时间排序如果排序算法不稳定第二次排序就可能把相同金额的订单顺序打乱。冒泡排序即使在没有优化的版本里也只在arr[j] arr[j1]时交换。遇到两个相等的元素它不会交换它们所以相等元素的相对位置始终保持不变。这一特性在需要多关键字排序时是无价之宝。6.3 什么场景才值得用冒泡排序聊到这里很多人会问既然 O(n^2)为什么还要学它、用它我自己的理解是冒泡排序的价值主要在三个地方一是教学它的逻辑足够简单是建立“循环交换”心智模型最好的素材二是小数据集数据量不超过几十个时哪怕是 O(n^2)在实际运行中也是毫秒级的事用冒泡排序反而代码最简洁、最难出错三是面试面试官问排序算法时如果你能先快速写出一个正确的冒泡排序然后自然讲出优化方案再对比分析复杂度这本身就是一种高级的沟通能力。在工程上我见过有人在嵌入式设备上用它处理不到 50 个元素的缓冲区排序因为实现短小、无递归、不占栈空间还方便移植到各种架构。指望用冒泡排序处理百万级数据那肯定是选型问题不是算法本身的问题。最后分享一个小技巧初学阶段建议拿扑克牌或者纸片写数字按冒泡排序的规则手动“跑”一遍你真的会看到那个“气泡”是怎么冒出来的。我当年就是靠这个动作彻底理解了它之后看任何语言的写法都觉得是理所当然。排序作为计算机科学里最基础的一类算法冒泡排序又是这条路上最平的台阶踩稳了后面爬任何一座山都会轻松不少。
