Golang学习-冒泡排序（Bubble Sort）

冒泡排序Bubble Sort一、算法思想冒泡排序的核心思想非常朴素相邻元素两两比较如果前一个比后一个大就交换它们。每一轮冒泡都会把当前未排序部分的最大值浮到最右端——就像气泡从水底往上冒一样这就是名称的由来。以[5, 3, 8, 1, 2]为例第一轮冒泡的过程[5, 3, 8, 1, 2] 比较 5 和 3 → 53交换 [3, 5, 8, 1, 2] 比较 5 和 8 → 58不交换 [3, 5, 8, 1, 2] 比较 8 和 1 → 81交换 [3, 5, 1, 8, 2] 比较 8 和 2 → 82交换 [3, 5, 1, 2, 8] ← 8 已冒泡到最右端第二轮继续在[3, 5, 1, 2]中冒泡把次大值 5 推到倒数第二位……以此类推n 个元素最多需要 n-1 轮冒泡。二、Go 实现2.1 基础版本packagemainimportfmt// BubbleSort 基础冒泡排序funcBubbleSort(arr[]int){n:len(arr)fori:0;in-1;i{// 外层控制冒泡轮数forj:0;jn-i-1;j{// 内层每轮比较范围逐渐缩小ifarr[j]arr[j1]{// 相邻比较左大右小就交换arr[j],arr[j1]arr[j1],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;in-1;i{swapped:falseforj:0;jn-i-1;j{ifarr[j]arr[j1]{arr[j],arr[j1]arr[j1],arr[j]swappedtrue}}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;in-1;i{swapped:falseborder:lastSwap// 本轮只需遍历到上一轮最后交换处forj:0;jborder;j{ifarr[j]arr[j1]{arr[j],arr[j1]arr[j1],arr[j]swappedtruelastSwapj// 记录本次交换的位置}}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[j1]时才交换严格大于arr[j] arr[j1]时不会交换所以相等元素的相对顺序不会被改变。原始: [3a, 3b, 1] (3a 和 3b 值相同a 在 b 前) 排序后: [1, 3a, 3b] ← 3a 仍在 3b 前面稳定 ✓如果改为arr[j] arr[j1]就交换就会破坏稳定性——这是面试常见陷阱。五、冒泡排序 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;ik;i{forj:0;jn-i-1;j{ifarr[j]arr[j1]{arr[j],arr[j1]arr[j1],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)稳定性来源于严格大于才交换会破坏稳定性实际开发中几乎不用冒泡排序但面试中经常考它的优化和稳定性分析