冒泡排序

冒泡排序（Bubble Sort）是一种简单直观的排序算法，适合初学者理解排序的基本概念。它通过反复比较相邻元素并交换位置，使得较大的元素逐步“冒泡”到数组的末尾，从而实现排序。本文将详细讲解冒泡排序的原理、步骤，并提供C语言和Go语言的代码示例，帮助初学者快速上手。

原理

冒泡排序的核心思想是：

1. 遍历数组，比较相邻的两个元素，如果它们的顺序不符合要求（例如，升序时前者大于后者），则交换它们。
2. 每次遍历后，最大的元素会被“冒泡”到未排序部分的末尾。
3. 缩小未排序部分的范围，重复上述步骤，直到整个数组排序完成。

它的时间复杂度是 O(n²)，其中 n 是数组的长度。虽然在实际应用中效率不如快速排序或归并排序，但它的简单性使其成为学习算法的理想起点。

步骤

假设我们要对一个整数数组进行升序排序，以下是冒泡排序的详细步骤：

1. 初始化：从数组的第一个元素开始，比较相邻的两个元素。
2. 比较与交换：如果前一个元素大于后一个元素，交换它们的位置。
3. 完成一轮遍历：遍历整个未排序部分，将最大的元素“冒泡”到末尾。
4. 更新范围：将未排序部分的末尾向前移动一位（因为最大的元素已就位）。
5. 重复：对剩余的未排序部分重复步骤2-4，直到整个数组排序完成。

实现

C

下面是用C语言实现冒泡排序的代码，包含详细注释以帮助理解。

main.c

#include <stdio.h>

// 冒泡排序函数
void bubbleSort(int arr[], int n) {
    int i, j, temp;
    
    // 外层循环：控制遍历的轮数
    for (i = 0; i < n-1; i++) {
        // 内层循环：比较并交换相邻元素
        for (j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // 交换相邻元素
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

// 打印数组的辅助函数
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 主函数：测试冒泡排序
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("原始数组：");
    printArray(arr, n);
    
    bubbleSort(arr, n);
    
    printf("排序后的数组：");
    printArray(arr, n);
    
    return 0;
}

编译 & 运行

$ gcc -o bin/bubble-sort main.c
$ bin/bubble-sort 
原始数组：64 34 25 12 22 11 90 
排序后的数组：11 12 22 25 34 64 90 
$ 

Go

下面是用Go语言实现冒泡排序的代码，包含详细注释以帮助理解。

main.go

package main

import "fmt"

// bubbleSort 实现冒泡排序
func bubbleSort(arr []int) {
    n := len(arr)
    
    // 外层循环：控制遍历的轮数
    for i := 0; i < n-1; i++ {
        // 内层循环：比较并交换相邻元素
        for j := 0; j < n-i-1; j++ {
            if arr[j] > arr[j+1] {
                // 交换相邻元素
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
}

// printArray 打印数组内容
func printArray(arr []int) {
    for _, val := range arr {
        fmt.Printf("%d ", val)
    }
    fmt.Println()
}

func main() {
    // 示例数组
    arr := []int{64, 34, 25, 12, 22, 11, 90}
    
    fmt.Print("原始数组：")
    printArray(arr)
    
    bubbleSort(arr)
    
    fmt.Print("排序后的数组：")
    printArray(arr)
}

$ gsk build -v
create bubble-sort/bin/bubble-sort-linux-amd64
$ ./bin/bubble-sort-linux-amd64 
原始数组：64 34 25 12 22 11 90 
排序后的数组：11 12 22 25 34 64 90

总结

冒泡排序的核心是通过比较和交换相邻元素，将较大的元素逐步“冒泡”到未排序部分的末尾来实现排序。

---

版权声明：自由转载-非商用-非衍生-保持署名-保持来源

作者：afxcn

来源：https://zh.gostartkit.com/docs/algo/bubble-sort

发表日期：2025年6月26日