Golang学习-冒泡排序（Bubble Sort）
冒泡排序（Bubble Sort）
一、算法思想
冒泡排序的核心思想非常朴素：相邻元素两两比较，如果前一个比后一个大就交换它们。每一轮"冒泡"都会把当前未排序部分的最大值"浮"到最右端——就像气泡从水底往上冒一样，这就是名称的由来。
以[5, 3, 8, 1, 2]为例，第一轮冒泡的过程：
[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, 1, 2]中冒泡，把次大值 5 推到倒数第二位……以此类推，n 个元素最多需要 n-1 轮冒泡。
二、Go 实现
2.1 基础版本
packagemainimport"fmt"// BubbleSort 基础冒泡排序funcBubbleSort(arr[]int){n:=len(arr)fori:=0;i<n-1;i++{// 外层：控制冒泡轮数forj:=0;j<n-i-1;j++{// 内层：每轮比较范围逐渐缩小ifarr[j]>arr[j+1]{// 相邻比较，左大右小就交换arr[j],arr[j+1]=arr[j+1],arr[j]}}}}funcmain(){arr:=[]int{5,3,8,1,2,7,4,6}fmt.Println("排序前:",arr)BubbleSort(arr)fmt.Println("排序后:",arr)}运行结果：
排序前: [5 3 8 1 2 7 4 6] 排序后: [1 2 3 4 5 6 7 8]2.2 优化版本：提前终止
如果某一轮冒泡过程中没有发生任何交换，说明数组已经排好序了，没必要继续后续轮次。我们可以用一个swapped标记来检测这种情况。
// BubbleSortOptimized 优化冒泡排序（提前终止）funcBubbleSortOptimized(arr[]int){n:=len(arr)fori:=0;i<n-1;i++{swapped:=falseforj:=0;j<n-i-1;j++{ifarr[j]>arr[j+1]{arr[j],arr[j+1]=arr[j+1],arr[j]swapped=true}}if!swapped{// 这一轮没有交换，数组已有序break}}}对于已经排好序的数组[1, 2, 3, 4, 5]，优化版只需要一轮就检测到没有交换并终止——从 O(n²) 降到了 O(n)。
2.3 进一步优化：记录最后交换位置
每轮冒泡后，最后发生交换的位置之后的元素其实已经排好了。下一轮只需要遍历到这个位置即可，不必遍历到n-i-1。
// BubbleSortAdvanced 双优化冒泡排序（提前终止 + 缩减范围）funcBubbleSortAdvanced(arr[]int){n:=len(arr)lastSwap:=n-1// 上一轮最后交换的位置fori:=0;i<n-1;i++{swapped:=falseborder:=lastSwap// 本轮只需遍历到上一轮最后交换处forj:=0;j<border;j++{ifarr[j]>arr[j+1]{arr[j],arr[j+1]=arr[j+1],arr[j]swapped=truelastSwap=j// 记录本次交换的位置}}if!swapped{break}}}这个优化对部分有序的数组效果显著——比如[2, 1, 3, 4, 5, 6, 7]，只需要处理前两个元素，后面的大段有序区域完全跳过。
三、复杂度分析
| 情况 | 时间复杂度 | 说明 |
|---|---|---|
| 最坏情况 | O(n²) | 逆序数组，每轮都要全量比较和交换 |
| 最好情况 | O(n) | 已排序数组，优化版一轮就退出 |
| 平均情况 | O(n²) | 随机数组，平均需要约 n²/2 次比较 |
| 空间复杂度 | O(1) | 原地排序，只需常数额外空间 |
3.1 比较次数推导
最坏情况下：
- 第 1 轮比较 n-1 次
- 第 2 轮比较 n-2 次
- …
- 第 n-1 轮比较 1 次
总比较次数 = (n-1) + (n-2) + … + 1 = n(n-1)/2 →O(n²)
3.2 交换次数推导
最坏情况（完全逆序）下每次比较都需要交换，交换次数 = 比较次数 = n(n-1)/2 →O(n²)
四、稳定性分析
冒泡排序是稳定排序。
稳定性定义：如果两个相等的元素在排序前后相对顺序不变，则排序是稳定的。
冒泡排序只有当arr[j] > arr[j+1]时才交换（严格大于），arr[j] == arr[j+1]时不会交换，所以相等元素的相对顺序不会被改变。
原始: [3a, 3b, 1] (3a 和 3b 值相同，a 在 b 前) 排序后: [1, 3a, 3b] ← 3a 仍在 3b 前面，稳定 ✓如果改为arr[j] >= arr[j+1]就交换，就会破坏稳定性——这是面试常见陷阱。
五、冒泡排序 vs 其他排序
| 对比维度 | 冒泡排序 | 选择排序 | 插入排序 |
|---|---|---|---|
| 最好时间 | O(n)（优化版） | O(n²) | O(n) |
| 平均时间 | O(n²) | O(n²) | O(n²) |
| 最坏时间 | O(n²) | O(n²) | O(n²) |
| 空间 | O(1) | O(1) | O(1) |
| 稳定性 | ✅ 稳定 | ❌ 不稳定 | ✅ 稳定 |
| 交换次数 | 多（每次比较都可能交换） | 少（每轮只交换1次） | 中等 |
六、适用场景
冒泡排序的实际应用场景非常有限，因为 O(n²) 的复杂度在大数据下不可接受。但它仍有价值：
- 教学用途：最直观的排序算法，适合入门理解排序的本质
- 小数据量：n < 50 时 O(n²) 和 O(n log n) 差异不明显
- 近乎有序的数据：优化版冒泡对几乎排好的数据非常高效（接近 O(n))
- 检测有序性：用优化版跑一遍，如果一轮就退出则说明数据已有序
七、用冒泡思想解决实际问题
7.1 找数组中第 k 大的元素
不需要完全排序，只跑 k 轮冒泡，最右端就会出现第 k 大的值：
// BubbleTopK 找第 k 大的元素（只冒泡 k 轮）funcBubbleTopK(arr[]int,kint)int{n:=len(arr)fori:=0;i<k;i++{forj:=0;j<n-i-1;j++{ifarr[j]>arr[j+1]{arr[j],arr[j+1]=arr[j+1],arr[j]}}}returnarr[n-k]}funcmain(){arr:=[]int{3,1,5,2,4}fmt.Println("第2大:",BubbleTopK(arr,2))// 4}这种做法的时间复杂度是 O(n × k)，比完全排序 O(n²) 快——当然，更优的做法是用快速选择（O(n) 平均），但冒泡思路简单直观。
八、小结
冒泡排序是最容易理解的排序算法，但也是效率最低的之一。它的核心价值不在实际应用，而在帮助理解排序的基本机制——比较、交换、轮次推进。
关键记忆点：
- 相邻比较，大者右移——这就是冒泡的全部逻辑
- 优化版提前终止可以把最好情况降到 O(n)
- 稳定性来源于严格大于才交换，
>=会破坏稳定性 - 实际开发中几乎不用冒泡排序，但面试中经常考它的优化和稳定性分析