你写的冒泡排序,真的是冒泡排序吗？Go 实现避坑

冒泡排序是一种通过反复比较相邻两个元素、把较大值逐步"浮"到末尾的排序算法。

注意这两个字：相邻。

这是它和选择排序最大的区别，也是最容易写错的地方。

一段"看起来对"的错误代码

先看下面这段。很多冒泡排序的教程里都长这样：

func bubbleSort(arr []int) []int {
	length := len(arr)
	if length <= 1 {
		return arr
	}
	for i := 0; i < len(arr); i++ {
		for j := i; j < len(arr); j++ {
			if arr[j] > arr[i] {
				arr[j], arr[i] = arr[i], arr[j]
			}
		}
	}
	return arr
}

它有两个问题。

第一，

它比较的是 arr[j] 和 arr[i]，也就是拿当前位置和后面所有元素挨个比。

这是选择排序的思路，不是冒泡。

冒泡必须比相邻的 arr[j] 和 arr[j+1]。

第二，

条件写的是 arr[j] > arr[i] 就交换，结果是从大到小排。

大多数人想要的是升序，这里悄悄反了。

输入 [11,8,2,5,7,10,3,6]，它给你的是 [11,10,8,7,6,5,3,2]。能跑，但不是你想要的。

说白了，名字叫冒泡，干的是选择排序的活，还顺手降了序。

冒泡排序到底怎么动

冒泡的核心动作只有一个：从头到尾扫一遍，每次比较相邻两个数，左边比右边大就交换。

一轮扫完，最大的那个数一定被推到了最右边。

下一轮扫描就可以少看一位，因为末尾已经排好了。

重复这个过程，数组就有序了。

拿 [3, 1, 2] 走一遍第一轮：

• 比较 3 和 1，3 大，交换 → [1, 3, 2]
• 比较 3 和 2，3 大，交换 → [1, 2, 3]

一轮下来 3 沉底，剩下的下一轮处理。形象点说，大的数像气泡一样一个个冒到水面。

正确的 Go 实现

package main

import "fmt"

func bubbleSort(arr []int) []int {
	n := len(arr)
	if n <= 1 {
		return arr
	}
	// 外层控制轮数，每轮固定一个最大值到末尾
	for i := 0; i < n-1; i++ {
		// 内层比较相邻元素，j+1 不能越界，所以到 n-1-i
		for j := 0; j < n-1-i; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}
	return arr
}

func main() {
	arr := []int{11, 8, 2, 5, 7, 10, 3, 6}
	fmt.Println(bubbleSort(arr)) // [2 3 5 6 7 8 10 11]
}

几个容易踩的点：

• 内层循环边界是 n-1-i，不是 n。因为要访问 arr[j+1]，j 最多到 n-2；又因为每轮末尾已经排好 i 个，所以再减 i。
• 外层只需要 n-1 轮。n 个数，固定 n-1 个，最后一个自然就位。
• 升序用 >，降序改成 < 就行。

我刚学的时候在 n-1-i 这个边界上卡了挺久，要么越界 panic，要么少排一轮。

建议自己拿三个数手推一遍，比记公式靠谱。

加一个提前退出优化

如果某一轮扫描下来一次交换都没发生，说明数组已经有序了，后面的轮次纯属浪费。

加个标志位就能跳出：

func bubbleSortOpt(arr []int) []int {
	n := len(arr)
	for i := 0; i < n-1; i++ {
		swapped := false
		for j := 0; j < n-1-i; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
				swapped = true
			}
		}
		if !swapped {
			break // 这一轮没动过，已经有序
		}
	}
	return arr
}

这个优化在数组接近有序时很管用。

极端情况下，对一个已经排好的数组，优化版只扫一轮就退出，时间复杂度从 O(n²) 降到 O(n)。

复杂度和适用场景

冒泡是稳定排序——相等的元素不会被交换，相对顺序保持不变。这一点在按多关键字排序时有用。

但实话说，工程里几乎没人用冒泡。O(n²) 的性能在数据量稍大时就扛不住。Go 标准库的 sort.Ints 用的是内省排序（快排 + 堆排 + 插入排序的混合），随手就能用：

import "sort"

arr := []int{11, 8, 2, 5, 7, 10, 3, 6}
sort.Ints(arr) // 升序，原地修改

冒泡的价值在于教学。它把"比较"和"交换"这两个排序最基本的动作讲得最清楚，适合拿来理解排序到底在干嘛。

常见问题

冒泡排序和选择排序有什么区别？

冒泡比较的是相邻元素，满足条件就立刻交换，一轮里可能交换很多次。

选择排序是每轮先扫一遍找到最值的下标，最后只交换一次。

本文开头那段错误代码，干的其实就是选择排序的事。

为什么内层循环是 n-1-i 而不是 n？

两个原因叠加。

一是要访问 arr[j+1]，j 不能等于 n-1，否则越界；二是每完成一轮，末尾就多固定一个已排好的元素，没必要再比，所以再减去已完成的轮数 i。

冒泡排序是稳定的吗？

是稳定的。

代码里用的是 arr[j] > arr[j+1]，严格大于才交换。

两个相等的元素遇到时不会交换，原本的先后顺序就保住了。

如果改成 >=，稳定性会被破坏。

实际开发中该用冒泡排序吗？

基本不用。

它的 O(n²) 复杂度在大数据量下太慢。直接用 sort.Ints、sort.Slice 这类标准库函数即可，性能和正确性都有保障。冒泡更多是面试和入门教学的素材。

写在最后

冒泡排序本身不难，难的是别把它写成别的算法。

记住"比相邻、大的往后挪"这一句，再手推几个小数组，基本就不会错了。

如果你对边界条件 n-1-i 还是有点懵，或者想看看快排、归并这些更快的排序怎么写，欢迎在评论区聊～～～