介绍

冒泡排序（Bubble Sort）是一种简单的排序算法，它通过重复地交换相邻元素的位置来将一个序列按照升序或降序进行排序。

以下是冒泡排序的基本思想和实现步骤：

• 比较相邻元素：从序列的第一个元素开始，比较相邻的两个元素，如果它们的顺序不符合排序要求，则交换它们的位置。
• 重复进行比较和交换：持续进行相邻元素的比较和交换操作，直到整个序列都排好序。
• 重复多次：重复上述步骤，每次都会将未排序部分中最大（或最小）的元素冒泡到正确的位置。
• 完成排序：最终，整个序列按照升序（或降序）排列。

代码实现

前冒

也就是把最小的冒泡到正确的位置固定。

package main

import "fmt"
// 升序
func ascendingSort(a []int) {
    for i := 0; i < len(a)-1; i++ {
        for j := i + 1; j < len(a); j++ {
            if a[i] > a[j] {
                a[i], a[j] = a[j], a[i]
            }
        }
    }
    fmt.Println(a)
}
//降序
func descendingSort(a []int) {
    for i := 0; i < len(a)-1; i++ {
        for j := i + 1; j < len(a); j++ {
            if a[i] < a[j] {
                a[i], a[j] = a[j], a[i]
            }
        }
    }
    fmt.Println(a)
}

func main() {
    ascendingSort([]int{9, 6, 2, 1, 5})
    descendingSort([]int{9, 6, 2, 1, 5})
}

[1 2 5 6 9]
[9 6 5 2 1]

代码解释

前冒，升序中那就是每次循环都将最小的元素冒泡到开头。每次相邻两个数进行比较，如果后面的数比前面的数大，就交换位置。

所以第一次内层循环的时候a[i]=a[0]，a[j]=a[i+1]=a[1]，这样比较的时候就是前两个元素进行比较，下次内层循环就是a[i]=a[0]和a[j]=a[i+1]=a[2]进行比较，直到最后一个元素，即a[j]=a[len(a)-1]，所以内层循环的范围就是j < len(a)。

内层循环结束后，这时已经确定了第一个元素即a[i]=a[0]是最小的数字。开始第二次外层循环，用a[i]=a[1]和后面的元素a[j]=a[i+1]=a[2]...a[len(a)-1]依次进行比较。

因为在内层循环中最后一个元素是a[len(a)-1]，所以在外层中最后一个元素是a[len(a)-1-1]，这样外层循环的范围就是len(a)-1，可以避免自己与自己比较。

降序同理。

后冒

也就是把最大的冒泡到正确的位置固定。

package main

import "fmt"

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

func descendingBubbleSort(a []int) {
    for i := 0; i < len(a)-1; i++ {
        for j := 0; j < len(a)-i-1; j++ {
            if a[j] < a[j+1] {
                a[j], a[j+1] = a[j+1], a[j]
            }
        }
    }
    fmt.Println(a)
}

func main() {
    ascendingBubbleSort([]int{64 34 25 12 22 11 90})
    descendingBubbleSort([]int{64 34 25 12 22 11 90})
}

代码解释

每次比较相邻的两个元素，每一轮循环都会将当前未排序部分中的最大元素冒泡到末尾。随着每一轮循环的进行，已经排序好的元素会逐渐增加，未排序部分的长度会减少。

假设n=len(a)，外层循环变量i表示每次遍历时的轮数，内层循环变量j表示每次遍历中当前未排序部分的索引。

第一轮循环比较时，需要进行n-1次相邻元素的比较，并将最大的元素冒泡到末尾。此时，未排序部分的最后一个元素就是整个序列的最大元素。

第二轮循环比较时，我们已经知道最大的元素已经在上一轮循环中冒泡到了末尾，所以在内层循环中就不需要再考虑末尾的元素。因此，内层循环的范围是从0到n-2。

依次类推，第i轮循环时，已经有i个元素确定了它们的位置，所以内层循环的范围是从0到n-i-1。

循环结果如下：

初始状态：[64 34 25 12 22 11 90]

第1轮循环：
比较 64 和 34，交换位置：[34 64 25 12 22 11 90]
比较 64 和 25，交换位置：[34 25 64 12 22 11 90]
比较 64 和 12，交换位置：[34 25 12 64 22 11 90]
比较 64 和 22，交换位置：[34 25 12 22 64 11 90]
比较 64 和 11，交换位置：[34 25 12 22 11 64 90]
比较 64 和 90，不交换位置：[34 25 12 22 11 64 90]

第2轮循环：
比较 34 和 25，交换位置：[25 34 12 22 11 64 90]
比较 34 和 12，交换位置：[25 12 34 22 11 64 90]
比较 34 和 22，交换位置：[25 12 22 34 11 64 90]
比较 34 和 11，交换位置：[25 12 22 11 34 64 90]
比较 34 和 64，不交换位置：[25 12 22 11 34 64 90]

第3轮循环：
比较 25 和 12，交换位置：[12 25 22 11 34 64 90]
比较 25 和 22，交换位置：[12 22 25 11 34 64 90]
比较 25 和 11，交换位置：[12 22 11 25 34 64 90]
比较 25 和 34，不交换位置：[12 22 11 25 34 64 90]

第4轮循环：
比较 12 和 22，不交换位置：[12 22 11 25 34 64 90]
比较 22 和 11，交换位置：[12 11 22 25 34 64 90]
比较 22 和 25，不交换位置：[12 11 22 25 34 64 90]

第5轮循环：
比较 12 和 11，交换位置：[11 12 22 25 34 64 90]
比较 12 和 22，不交换位置：[11 12 22 25 34 64 90]

第6轮循环：
比较 11 和 12，不交换位置：[11 12 22 25 34 64 90]

复杂度

• 最佳情况时间复杂度：
  在最佳情况下，待排序序列已经是有序的，冒泡排序只需要进行一次完整的遍历来确认序列已经有序。因此，最佳情况时间复杂度为 O(n)，其中 n 是待排序序列的长度。

• 最坏情况时间复杂度：
  在最坏情况下，待排序序列是逆序的，每一趟遍历都需要进行元素的比较和交换。冒泡排序需要进行 n-1 趟遍历，每趟遍历需要比较和交换的次数为 n-i-1（其中 i 是当前趟数）。因此，最坏情况时间复杂度为 O(n^2)。

• 平均情况时间复杂度：
  冒泡排序的平均情况时间复杂度也是 O(n^2)。平均情况下，待排序序列的初始顺序是随机的，每一趟遍历需要比较和交换的次数的期望值仍然是 n/2。因此，平均情况时间复杂度为 O(n^2)。

空间复杂度为O(1)，因为它只需要少量的额外空间来存储临时变量。