基于go实现冒泡排序

一、了解冒泡排序

冒泡排序，顾名思义就是一种以两两比较为基础的分类方法。因为它从一个数组中 循环比较相邻两元素，如果逆序，则进行两个元素间的交换。用go来写代码片段如下。

for j :=0; j<len(a)-1; j++ {
    if a[j]>a[j+1] {
        a[j],a[j+1]=a[j+1],a[j]
    }
}

执行这段for循环，会对数组中的所有元素进行一次相邻元素的比较，距离最终有序数组迈出了一小步。把这个排序过程想象一个成一个气泡刚从池塘底层淤泥里产生出，那么达到最终数组我们最多执行多少次这个for循环呢？想必聪明的你肯定想到最多情况我需要把这个气泡移动水的深度，即可移动气泡🫧到最终位置水面上。

它的两层for循环代码如下：

func BubbleSort(a []int) {
    for i :=0; i<len(a)-1; i++ {
        for j :=0; j<len(a)-1; j++ {
            if a[j]>a[j+1] {
                a[j],a[j+1]=a[j+1],a[j]
            }
        }
    }
}

从这个过程我们可以得到以下初步结论：

• 冒泡排序最差复杂度是O(n2)，即水泡在水底情况下。因为他要执行两次for循环，每次for的长度都是跟数组长度有关系
• 水泡有可能起初位置在水中间，那么将水泡移动到水面上，它可能不需要水深（即数组的长度）。但是因为没有上帝视角知道是循环次数不是已经够把水泡移动到水面上，而且我们要确保每层水深的水泡都最终上移到水面上，所以平均复杂度也是O(n2)。
• 最傻的情况就是中途整个数组都已经有序了，但是因为还没执行完循环次数，然后排序在继续执行循环空转。

二、例子

我们用代码来解释这个冒泡的一些过程。

例子1：数组[1,2,3,4,5,6,7,8,9,0]

这里除了0之外都是升序的，那么我用一个图解释这个这种气泡🫧0是怎么上浮到水面上（1之前）。

这个图的x坐标代表循环第几遍，y坐标代表整个数组的元素位置。

1. 操作1:这图里面第一遍，我们从最底下的0位置，因为它和隔壁上面的9位置进行交换，所以向上移动一个小格。但是其他元素都是有序的，所以不进行任何移动。
2. 循环执行操作1，这里会看到0的位置不断往上移，知道操作1 执行完9遍之后，0的位置在水面上。

例子2 数组[1,2,3,0,4,5,9,6,7,8]

这个例子我们看下两个元素的位置乱序，其他元素相对有序的情况。

元素0和元素9在数组中的位置都不对。这里看到现象是每次执行一层两两交换，元素0会向上移动一格，元素9会向下移动n格直到池底。元素9之所以会一下子移到最下面位置，是因为两两比较刚好是从上往下执行。9和6比较结果是交换位置变成6和9，接下来又触发9和7比较。所以9在第一遍循环就已经找到了最终的位置。但是这里要说明的是，这个元素要经过多少遍才能找到最终位置，这里 没有明确的答案。因为我们可能像元素0运气那么背要找n次（数组长度-1），也可能像元素9运气好找1遍，也可能 运气是介于中间状态。总之我们最多要执行n次才能执行完。

例子3 完全乱序

我们在看一个完全随机乱序的例子

三 完整的go代码

最后的最后，贴下这个golang实现的冒泡排序代码。这里对a数组进行排序，然后将排序好的数组打印出来。

package main
  
import "fmt"

func main() {
    a:=[]int{-44,3,2,1,55}
    BubbleSort(a)
    fmt.Println(a)
}

func BubbleSort(a []int) {
    for i :=0; i<len(a)-1; i++ {
        for j :=0; j<len(a)-1; j++ {
            if a[j]>a[j+1] {
                a[j],a[j+1]=a[j+1],a[j]
            }
        }
    }
}