冒泡排序（Bubble Sort）
类型：交换排序时间复杂度（最坏）：O(n^2) 时间复杂度（最好）：O(n) 时间复杂度（平均）：O(n^2) 空间复杂度：O(1) 稳定性：稳定
冒泡排序通过依次比较两个相邻元素的值，将数值较大的元素移动至数列尾部，每一轮的比较都能将无序数列中的最大值元素选出并移动到队尾，循环执行便可将数列按由大到小的顺序排列出来。因值大于才会发生交换，故为稳定排序。
package main
import (
“fmt”
)
func main() {
var arr = []int{1, 6, 2, 4, 5, 3, 7, 9, 8}
BubbleSort(arr)
fmt.Print(“sorted: “, arr)
}
// 冒泡排序
func BubbleSort(arr []int) {
length := len(arr)
alreadyOrdered := true // 记录某次排序是否发生元素交换
// 最多需要 length-1 次外循环
for i := 0; i < length-1; i++ {
// length-i 为待排序数列的长度 i 为有序数列的长度
for j := 0; j < (length-i)-1; j++ {
if arr[j] > arr[j+1] {
alreadyOrdered = false
temp := arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
}
}
// 如果某次排序没有发生交换说明已有序
if alreadyOrdered {
break
}
}
}