冒泡排序(Bubble Sort)

冒泡排序是一种交换排序，对给定的数组进行多次遍历，每次比较相邻的数字，如果前一个比后一个大，则交换二者的位置，否则不进行操作，以此类推。
其核心思想是将数据分为有序区和无序区，每次操作将无序区的最大元素放到有序区的最前端，重复n-1次后就能保证数组有序。

算法步骤

1. 比较相邻两个元素是否满足大小关系要求，如不满足则将二者交换
2. 一次冒泡会让至少一个元素移动到它应该在的位置
3. 重复n次，完成排序
4. 可以加一个提前退出冒泡排序的标志，但对性能的提升很有限

   动画演示

   

   分析

• 空间复杂度：

每次只进行相邻两个元素的位置互换，因此空间复杂度为

• 时间复杂度：

项目	平均情况	最差情况	最好情况
时间复杂度
比较次数
交换次数	逆序数		0

• 稳定性

存在大小关系的数据才会进行交换，值相等的数据只比较不交换，因此冒泡排序是稳定排序

代码实现

func bubboleSort(nums []int){
    for i := 0; i < len(nums); i++ {
        // 提前退出冒泡排序标志
        var flag bool
        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
        }
    }
}