Go语言实现冒泡排序：从基础到优化详解

一颗松果

发布时间：2026-10-15| 8人浏览过

原创

冒泡排序是基础的交换类排序算法。本文基于Go语言演示其工作原理，包含普通实现与基于标志位的优化方案，解析如何通过减少不必要的比较来提升排序效率。

算法思路

冒泡排序的核心逻辑是通过重复遍历列表，依次比较相邻的两个元素，如果顺序错误（以升序为例，前一个大于后一个）就交换它们的位置。每一轮遍历结束后，当前未排序部分的最大值会被“冒泡”到末尾位置。

比较规则：遍历数组，相邻两两比较，若前 > 后，则交换。
每轮结果：第一轮结束，最大值归位；第二轮结束，次大值归位，以此类推。
轮次限制：对于长度为 n 的数组，最多执行 n - 1 轮。当仅剩最后一个元素时，无需再与其他元素比较，自然处于正确位置。

过程图解演示

第一轮遍历：寻找最大值

初始数组为 [4, 2, 1, 3]。

i = 0：比较 4 和 2，因为 4 > 2，交换。数组变为 [2, 4, 1, 3]。
i = 1：比较 4 和 1，因为 4 > 1，交换。数组变为 [2, 1, 4, 3]。
i = 2：比较 4 和 3，因为 4 > 3，交换。数组变为 [2, 1, 3, 4]。

第一轮结束，最大值 4 已固定在最后一位。

第二轮遍历：寻找次大值

此时只需对前三个元素 [2, 1, 3] 进行比较（最后一个 4 已就位）。

i = 0：比较 2 和 1，因为 2 > 1，交换。数组变为 [1, 2, 3, 4]。
i = 1：比较 2 和 3，因为 2 < 3，不交换。

第二轮结束，次大值 3 已固定在倒数第二位。

第三轮遍历：收尾

此时前两个元素 [1, 2] 需要比较。

i = 0：比较 1 和 2，因为 1 < 2，不交换。

执行了 n - 1 = 3 轮遍历，所有元素归位，排序完成。

普通冒泡排序实现

这是最基础的版本，严格按照 n - 1 轮进行固定次数的遍历。

import "fmt"

func main() {
    nums := [4]int{4, 2, 1, 3}
    fmt.Println("原数组：", nums)
    fmt.Println("--------------------------------")
    NormalBubbleSort(nums)
}

func NormalBubbleSort(nums [4]int) {
    // 外层循环控制轮数
    for i := 0; i < len(nums)-1; i++ {
        // 内层循环控制每轮的比较次数
        // 每次外层循环增加 i，内层比较范围减少 i 次
        for j := 0; j < len(nums)-i-1; j++ {
            if nums[j] > nums[j+1] {
                nums[j], nums[j+1] = nums[j+1], nums[j]
            }
        }
        fmt.Printf("第 %d 轮遍历后的数组：%v\n", i+1, nums)
    }
    fmt.Println("--------------------------------")
    fmt.Println("排序后的数组：", nums)
}

执行输出：

原数组： [4 2 1 3]
--------------------------------
第 1 轮遍历后的数组：[2 1 3 4]
第 2 轮遍历后的数组：[1 2 3 4]
第 3 轮遍历后的数组：[1 2 3 4]
--------------------------------
排序后的数组： [1 2 3 4]

核心参数说明

内层循环条件 j < len(nums)-i-1 中的减法操作是为了避免无效比较。每完成一轮外层循环（i增加），就有 i 个最大的元素被排定到了末尾，因此在下一轮比较时，只需遍历剩下的 len(nums)-i-1 个元素即可。

复杂度分析

总比较次数为 (n-1) + (n-2) + ... + 1，即 n*(n-1)/2。因此，无论数据初始状态如何，普通版的比较次数固定，**时间复杂度始终为 O(n²)**。

优化算法实现

在上面的例子中，第三、四轮虽然执行了遍历，但内部并未发生元素交换，说明数组已经有序。为了处理这种情况，可以引入一个布尔标志位 isSwapped 来检测本轮是否发生过交换。

优化逻辑

若某轮遍历中没有发生任何交换，说明整个数组已经是有序的，可以直接跳出循环，不再进行后续的无意义遍历。
这种优化在最坏情况（完全逆序）下仍为 O(n²)，但在最好情况（原本已有序）下可提升至 **O(n)**。

import "fmt"

func main() {
    nums := [5]int{4, 2, 1, 3, 5}
    fmt.Println("原数组：", nums)
    fmt.Println("--------------------------------")
    BestBubbleSort(nums)
}

func BestBubbleSort(nums [5]int) {
    isSwapped := true // 初始化为 true 以确保至少进入一次循环
    
    // 只要发生过交换，就继续遍历
    for isSwapped {
        isSwapped = false // 每轮开始前重置标志位
        
        for i := 0; i < len(nums)-1; i++ {
            if nums[i] > nums[i+1] {
                nums[i], nums[i+1] = nums[i+1], nums[i]
                isSwapped = true // 发生了交换，标记为 true
            }
        }
        fmt.Println("遍历后的数组：", nums)
    }
    
    fmt.Println("--------------------------------")
    fmt.Println("排序后的数组：", nums)
}

执行输出：

原数组：
--------------------------------
遍历后的数组： [2 1 3 4 5]
遍历后的数组： [1 2 3 4 5]
遍历后的数组： [1 2 3 4 5]
--------------------------------
排序后的数组： [1 2 3 4 5]