冒泡排序 - Hello Golang

冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法，其核心思想是通过多次遍历列表，逐步将最大（或最小）的元素“冒泡”到列表的末尾。尽管冒泡排序的时间复杂度较高，通常用作教学目的或处理小规模数据的简单排序。

1. 冒泡排序的基本概念

冒泡排序的过程如下：

遍历并比较:
- 从列表的起始位置开始，依次比较相邻的元素。
- 如果前一个元素大于后一个元素，则交换这两个元素。
调整排序范围:
- 每轮遍历结束后，最大的元素被放到列表的末尾。
- 随着排序的进行，未排序的范围逐渐缩小。
提前退出优化:
- 如果在某次遍历中没有发生任何交换，说明列表已经排序好，可以提前退出，避免不必要的遍历。

2. 冒泡排序的算法步骤

以下是冒泡排序的详细步骤：

外层循环: 从列表的起始位置到倒数第二个元素。
- 内层循环: 从列表的起始位置到倒数第 i 个元素，比较相邻元素。
- 如果前一个元素大于后一个元素，则交换它们。
提前退出:
- 如果在内层循环中没有发生交换，说明列表已经排序好，可以退出外层循环。

3. 冒泡排序的时间复杂度和空间复杂度

时间复杂度:
- 最坏情况: $O (n^{2})$ ，当数组完全逆序时，需要进行最多 $n (n - 1) /2$ 次比较和交换。
- 最佳情况: $O (n)$ ，当数组已经排序好时，仅需进行一次遍历且没有交换。
- 平均情况: $O (n^{2})$ ，对随机排序的数组进行排序时，平均时间复杂度为 $O (n^{2})$ 。
空间复杂度:
- 空间复杂度: $O (1)$ ，冒泡排序是就地排序算法，不需要额外的存储空间，除了用于临时交换的变量。

4. 冒泡排序的代码示例

以下是使用 Go 语言实现的冒泡排序算法：

package main

import "fmt"

// BubbleSort 对整数切片进行冒泡排序
func BubbleSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        swapped := false
        for j := 0; j < n-i-1; j++ {
            if arr[j] > arr[j+1] {
                // 交换元素
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = true
            }
        }
        // 如果没有交换，说明已排序好，提前退出
        if !swapped {
            break
        }
    }
}

func main() {
    arr := []int{64, 34, 25, 12, 22, 11, 90}
    fmt.Println("Original array:", arr)
    BubbleSort(arr)
    fmt.Println("Sorted array:", arr)
}

5. 冒泡排序的优缺点

优点:

实现简单，易于理解和编写。
适用于小规模数据集。

缺点:

对大规模数据集效率低，时间复杂度为 $O (n^{2})$ 。
不适合对性能要求较高的场景。

总结

冒泡排序是一种基础的排序算法，通过不断交换相邻逆序对，将元素逐步移动到正确位置。尽管它在大多数实际应用中效率较低，但其简洁的实现使其成为学习排序算法和理解排序基本概念的良好起点。