冒泡排序：相邻元素两两比较

冒泡排序相邻元素两两比较软考程序员考试中冒泡排序是排序算法章节的必考内容。今天我们就来聊聊这个最温柔的排序算法——它每次只敢和邻居比一比。一、为什么叫冒泡想象一锅烧开了的水底部的气泡一点点往上冒。大的气泡跑得快先冒到水面小的气泡慢慢悠悠后上来。冒泡排序的原理一模一样每一轮从第一个元素开始相邻的两个元素两两比较。如果前面的比后面的大升序情况就交换它们的位置。一轮下来最大的那个元素就像最大的气泡一样冒到了最后面。二、具体怎么操作来看一个例子假设要对[5, 3, 8, 1, 2]进行升序排序第一轮5 和 3 比5 3交换 →[3, 5, 8, 1, 2]5 和 8 比5 8不交换 →[3, 5, 8, 1, 2]8 和 1 比8 1交换 →[3, 5, 1, 8, 2]8 和 2 比8 2交换 →[3, 5, 1, 2, 8]第一轮结束8 已经冒到了最后面。第二轮3 和 5 比不交换5 和 1 比交换 →[3, 1, 5, 2, 8]5 和 2 比交换 →[3, 1, 2, 5, 8]第二轮结束5 也到位了。依次类推经过 n-1 轮整个序列就排好了。三、代码怎么写用伪代码表示for i 0 to n-1: for j 0 to n-1-i: if arr[j] arr[j1]: swap(arr[j], arr[j1])注意内层循环的范围是n-1-i因为每轮结束后最后 i 个元素已经排好序了不需要再比较。四、优化提前结束有个聪明的优化思路如果某一轮比较下来一次交换都没有发生说明序列已经有序了还比什么直接结束怎么实现加一个标志位swapped每轮开始时设为 false发生交换时设为 true。一轮结束后如果 swapped 还是 false就 break。for i 0 to n-1: swapped false for j 0 to n-1-i: if arr[j] arr[j1]: swap(arr[j], arr[j1]) swapped true if swapped false: break这个优化在最好情况已经有序下时间复杂度能从 O(n²) 降到 O(n)。五、性能分析情况时间复杂度说明最好情况O(n)已经有序一轮比较就结束最坏情况O(n²)完全逆序每轮都要交换平均情况O(n²)大致是 n²/4 次交换空间复杂度O(1)只需要一个临时变量用于交换是原地排序。稳定性稳定。相等的元素不会交换位置所以相同元素的相对顺序不变。六、软考常考点考点1冒泡排序的比较次数最好情况n-1 次比较最坏情况n(n-1)/2 次比较考点2冒泡排序的交换次数最好情况0 次已经有序最坏情况n(n-1)/2 次完全逆序考点3稳定性判断冒泡排序是稳定的排序算法因为相邻元素相等时不交换。考点4优化后的最好情况加了 swapped 标志后最好情况时间复杂度为 O(n)。软考小贴士冒泡排序虽然效率不高但胜在简单易懂。考试中常考它的比较次数、交换次数的计算以及稳定性的判断。记住它是稳定的、原地的、时间复杂度 O(n²) 的排序。一句话记住冒泡排序就像水中气泡大的慢慢浮上去每轮把一个最大元素送到末尾。互动时间你觉得冒泡排序在实际开发中还有用武之地吗什么场景下用它反而合适评论区聊聊你的看法觉得这篇讲清楚了点个赞收藏起来转发给正在备考软考的朋友吧关注「通俗易懂学IT」我们一起把计算机知识学透想系统备考软考程序员加入我们的知识星球获取完整备考资料、真题解析、学习打卡助你一次通关