冒泡排序

ByWhat'sUs

冒泡排序

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求，如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

package main

import "fmt"

func bubbleSort(nums []int) []int {
    if len(nums) <= 1 {
        return nums
    }

    // 冒泡排序核心实现代码
    for i := 0; i < len(nums); i++ {
        flag := false
        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]
                flag = true
            }
        }
        if !flag {
            break
        }
    }

    return nums
}

func main() {
    nums := []int{4, 5, 6, 7, 8, 3, 2, 1}
    nums = bubbleSort(nums)
    fmt.Println(nums)
}

性能分析

• 时间复杂度： O(n²)
• 空间复杂度：只涉及相邻元素的交换，是原地排序算法
• 算法稳定性：元素相等不会交换，是稳定的排序算法