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

算法思路

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

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

过程图解演示

第一轮遍历：寻找最大值

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

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

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

第二轮遍历：寻找次大值

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

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

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

第三轮遍历：收尾

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

1. 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]

效果对比

• 对于数组 [4, 2, 1, 3, 5]，普通版会强制跑完4轮，而优化版在第3轮检测到无交换后结束（尽管本例中前两轮已完成排序，第3轮仅做检查）。
• 对于完全有序的数组（如 [1, 2, 3, 4, 5]），优化版仅执行一轮遍历并立即退出，时间复杂度降为 O(n)。
• 对于接近有序的数据集，优化版能显著减少无效比较的次数。

小结

冒泡排序是一种直观且易于实现的入门级排序算法。通过引入标志位 isSwapped，可以有效跳过那些已经有序的子序列，从而在最佳情况下将性能从 O(n²) 提升至 O(n)。理解这一优化机制有助于掌握更高效的算法设计思维。

以上就是Go语言实现冒泡排序算法的详细过程，更多关于Go语言算法的资料请关注本站其它相关文章！